【数据结构】回顾二叉树

1.为什么会有树&＃xff1f;因为当有大量的输入数据时&＃xff0c;链表的线性访问时间就显得略长了。而树结构&＃xff0c;其大部分操作的运行时间平均为O(logN)。

2.树的实现并不难&＃xff0c;几行代码就搞定了。

struct TreeNode
{Object element;TreeNode *firstChild;TreeNode *nextSibling;
}

3.遍历形式&＃xff1a;

// 中序遍历二叉树
void inorder(tree_pointer ptr)
{if(ptr){inorder(ptr->left_child);printf("%d",ptr->data);inorder(ptr->right_child);}
}// 前序遍历二叉树
void preorder(tree_pointer ptr)
{if(ptr){printf("%d",ptr->data);preorder(ptr->left_child);preorder(ptr->right_child);}
}// 后序遍历二叉树
void postorder(tree_pointer ptr)
{if(ptr){postorder(ptr->left_child);postorder(ptr->right_child);printf("%d",ptr->data);}
}

4.迭代的中序遍历

void iter_inorder(tree_pointer node)
{int top&＃61;-1;tree_pointer stack[MAX_STACK_SIZE];for(;;){for(;node;node&＃61;node->left_child)add(&top,node);node&＃61;delete(&top);if(!node)break;printf("%d",node->data);node&＃61;node->right_child;}
}

5.二叉树的层序遍历

void level_order(tree_pointer ptr)
{int front&＃61;rear&＃61;0;tree_pointer queue[MAX_QUEUE_SIZE];if(!ptr)return;addq(front,&rear,ptr);for(;;){ptr&＃61;deleteq(&front,rear);if(ptr){printf("%d",ptr->data);if(ptr->left_child)addq(front,&rear,ptr->left_child);if(ptr->right_child)addq(front,&rear,ptr->right_child);}elsebreak;}
}

6.二叉树的复制

tree_pointer copy(tree_pointer original)
{tree_pointer temp;if(original){temp&＃61;(tree_pointer) malloc(sizeof(node));if(IS_FULL(temp)){fprintf(stderr,"The memory is full\n");exit(1);}temp->left_child&＃61;copy(original->left_child);tmep->right_child&＃61;copy(original->right_child);temp->data&＃61;original->data;return temp;}return NULL;
}

7.判断二叉树的等价性

int equal(tree_pointer first,tree_pointer second)
{
return ((!first&&!second)||(first && second && (first->data &＃61;&＃61; second->data) && equal(first->left_child,second->left_child) &&equal(first->right_child,second->right_child));
}

8.寻找结点的中序后继

threaded_pointer insucc(threaded_pointer tree)
{threaded_pointer temp;temp&＃61;tree->right_child;if(!tree->right_thread)while(!temp->left_thread)temp&＃61;temp->left_child;return temp;
}

9.线索二叉树的中序遍历

void tinorder(threaded_pointer tree)
{threaded_pointer temp&＃61;tree;for(;;){temp&＃61;insucc(temp);if(temp&＃61;&＃61;tree)break;printf("%3c",temp->data);}
}

10.线索二叉树的右插入操作

void insert_right(threaded_pointer parent,threaded_pointer child)
{threaded_pointer temp;child->right_child&＃61;parent->right_child;child->right_thread&＃61;parent->right_thread;child->left_child&＃61;parent;child->left_thread&＃61;TRUE;parent->right_child&＃61;child;parent->right_thread&＃61;FALSE;if(!child->right_thread){temp&＃61;insucc(child);temp->left_child&＃61;child;}
}

感谢您的访问&＃xff0c;希望对您有所帮助。

欢迎大家关注或收藏、评论或点赞。

为使本文得到斧正和提问&＃xff0c;转载请注明出处&＃xff1a;
http://blog.csdn.net/nomasp