遍历二叉树（国嵌学习笔记）

    单链表的遍历是指从第一个节点开始（下标为0的结点），按照某种次序依次访问每一个结点；而

二叉树的遍历是指从跟结点开始，按照某种次序依次访问二叉树中的所有结点。单链表的遍历方式有

正序遍历和逆序遍历两种方式，二叉树的遍历则包括以下三种方式：1、前序遍历，2、中序遍历，

3、后序遍历，4、层次遍历

1、前序遍历

算法思想：

    若二叉树为空：空操作返回；

    

    若二叉树不为空：1、访问跟结点中的数据，2、前序遍历左子树，3、前序遍历右子树

2、中序遍历

算法思想：

    若二叉树为空：空操作返回；

    若二叉树不为空：1、中序遍历左子树，2、访问跟结点中的数据，3、中序遍历右子树

3、后序遍历

算法思想：

    

    若二叉树为空：空操作返回；

    若二叉树不为空：1、后序遍历左子树，2、后序遍历右子树，3访问跟结点中的数据

4、层次遍历

算法思想：

    若二叉树为空：空操作返回；

    若二叉树不为空：1、访问跟结点中的数据，2、访问第二层所有结点树数据，3、访问第三层所有结点的数据。

/*
*二叉树的遍历，其中在层次遍历的时候借助了之前实
*现的队列
*/


#include <stdio.h>
#include <stdlib.h>
#include "BTree.h"
#include "LinkQueue.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

struct Node
{
    BTreeNode header;
    char v;
};

void printf_data(BTreeNode* node)
{
    if( node != NULL )
    {
        printf("%c", ((struct Node*)node)->v);
    }
}

void pre_order_traversal(BTreeNode* root)
{
    if( root != NULL )
    {
        printf("%c, ", ((struct Node*)root)->v);

        pre_order_traversal(root->left);
        pre_order_traversal(root->right);
    }
}

void middle_order_traversal(BTreeNode* root)
{
    if( root != NULL )
    {
        middle_order_traversal(root->left);

        printf("%c, ", ((struct Node*)root)->v);

        middle_order_traversal(root->right);
    }
}

void post_order_traversal(BTreeNode* root)
{
    if( root != NULL )
    {
        post_order_traversal(root->left);

        post_order_traversal(root->right);

        printf("%c, ", ((struct Node*)root)->v);
    }
}

void level_order_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("%c, ", node->v);

                LinkQueue_Append(queue, node->header.left);
                LinkQueue_Append(queue, node->header.right);
            }
       }

       LinkQueue_Destroy(queue);
    }
}


int main(int argc, char *argv[])
{
    BTree* tree = BTree_Create();

    struct Node n1 = {{NULL, NULL}, 'A'};
    struct Node n2 = {{NULL, NULL}, 'B'};
    struct Node n3 = {{NULL, NULL}, 'C'};
    struct Node n4 = {{NULL, NULL}, 'D'};
    struct Node n5 = {{NULL, NULL}, 'E'};
    struct Node n6 = {{NULL, NULL}, 'F'};

    BTree_Insert(tree, (BTreeNode*)&n1, 0, 0, 0);
    BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);
    BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);
    BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);
    BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);
    BTree_Insert(tree, (BTreeNode*)&n6, 0x02, 3, 0);

    printf("Full Tree: \n");

    BTree_Display(tree, printf_data, 4, '-');

    printf("Pre Order Traversal:\n");

    pre_order_traversal(BTree_Root(tree));

    printf("\n");

    printf("Middle Order Traversal:\n");

    middle_order_traversal(BTree_Root(tree));

    printf("\n");

    printf("Post Order Traversal:\n");

    post_order_traversal(BTree_Root(tree));

    printf("\n");

    printf("Level Order Traversal:\n");

    level_order_traversal(BTree_Root(tree));

    printf("\n");

    BTree_Destroy(tree);

    return 0;
}

递归定义的数据结构采用递归的算法进行遍历往往能够达到简单可靠的效果。