文明之精神，野蛮之体魄。
全部博文（64）
分类： C/C++
2013-10-11 22:05:59
一、 前序遍历
1. 算法思想
a) 若二叉树为空：空操作返回
b) 若二叉树不为空：
访问根结点中的数据
前序遍历左子树
前序遍历右子树
二、 中序遍历
1. 算法思想
a) 若二叉树为空：空操作返回
b）若二叉树不为空：
中序遍历左子树
访问根结点中的数据
中序遍历右子树
三、 后序遍历
1. 算法思想
a) 若二叉树为空：空操作返回
b) 若二叉树不为空：
后序遍历左子树
后序遍历右子树
访问根结点中的数据
四、 层次遍历
1. 算法思想
a) 若二叉树为空：空操作返回
b) 若二叉树不为空：
访问根结点中的数据
访问第二次所有结点的数据
访问第三层所有结点的数据
………
五、 算法实现
1. 前序遍历
void pre_traversal(BTreeNode* root)
{
if(root != NULL){
printf("%3c",((struct Node*)root)->v);
pre_traversal(root->left);
pre_traversal(root->right);
}
}
2. 中序遍历
void mid_traversal(BTreeNode* root)
{
if(root != NULL){
mid_traversal(root->left);
printf("%3c",((struct Node*)root)->v);
mid_traversal(root->right);
}
}
3. 后序遍历
void post_traversal(BTreeNode* root)
{
if(root != NULL){
post_traversal(root->left);
post_traversal(root->right);
printf("%3c",((struct Node*)root)->v);
}
}
4. 层次遍历
void level_traversal(BTreeNode* root)
{
if(root != NULL){
LinkQueue* queue = LinkQueue_Create();
if(queue != NULL){
LinkQueue_Append(queue,root);
while(LinkQueue_Length(queue) > 0){
struct Node* node = (struct Node*)LinkQueue_Retrieve(queue);
printf("%3c",node->v);
LinkQueue_Append(queue,node->header.left);
LinkQueue_Append(queue,node->header.right);
}
}
LinkQueue_Destroy(queue);
}
}
六、 小结
二叉树仅仅比单链表多了一个指针域，但其遍历算法的种类却增加了很多。
