6-9二叉树的遍历

题目描述

求给定二叉树的4种遍历(前、中、后、层次)

要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

题目地址为:https://pintia.cn/problem-sets/15/problems/732

BinTree结构定义 

1
2
3
4
5
6
7
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

前序遍历

思考

前序遍历是指先遍历根结点，然后再遍历左右子树，利用递归就完事，为NULL就不遍历了

遍历子树的过程就是重复上面的步骤

具体代码

1
2
3
4
5
6
7
8
void PreorderTraversal( BinTree BT ) {
    if (!BT) {
        return ;
    }
    printf(" %c",BT->Data);
    PreorderTraversal(BT->Left);
    PreorderTraversal(BT->Right);
}

中序遍历

思考

中序遍历是指先遍历左子树，然后再遍历根结点，最后是右子树，利用递归就完事，为NULL就不遍历了

遍历子树的过程就是重复上面的步骤

具体代码

1
2
3
4
5
6
7
8
void InorderTraversal( BinTree BT ) {
    if (!BT) {
        return ;
    }
    InorderTraversal(BT->Left);
    printf(" %c",BT->Data);
    InorderTraversal(BT->Right);
}

后序遍历

思考

后序遍历是指先遍历左右子树，然后再遍历根结点，利用递归就完事，为NULL就不遍历了

遍历子树的过程就是重复上面的步骤

具体代码

1
2
3
4
5
6
7
8
void PostorderTraversal( BinTree BT ) {
    if (!BT) {
        return ;
    }
    PostorderTraversal(BT->Left);
    PostorderTraversal(BT->Right);
    printf(" %c",BT->Data);
}

层序遍历

思考

层序遍历指的是一层一层遍历树，从以往所学的知识来看需要建立一个队列。

出队一个元素就输出他的左右子树，然后把左右子树入队直到队列为空。

那么第一步就是写一个简易的队列。带有两个名为front和rear的指针的数组。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void LevelorderTraversal( BinTree BT ) {
    BinTree node_queue[100];
    BinTree node;
    int rear ,front = 0;
    if (!BT) {
        return ;
    }

    node_queue[front] = BT;
    rear++;
    
    while(front != rear) {
        node = node_queue[front];
        front++;
        printf(" %c",node->Data);
        if(node->Left) {
            node_queue[rear++] = node->Left;
        }
        if(node->Right) {
            node_queue[rear++] = node->Right;
        }
    }
}