PTA 二叉树的遍历（实验）_pta二叉树的遍历

本题要求给定二叉树的 4 种遍历。

函数接口定义：

void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
1
2
3
4

其中 BinTree 结构定义如下：

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

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

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );

int main()
{
    BinTree BT = CreatBinTree();
    printf("Inorder:");    InorderTraversal(BT);    printf("\n");
    printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
    printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
    printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

输出样例（对于图中给出的树）：

Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H
1
2
3
4

解题

二叉树的先序遍历

先序遍历就是对树中任意结点，

1. 先访问本身
2. 再遍历其左子树
3. 最后遍历其右子树

代码采用递归方式实现。

二叉树的中序遍历

中序遍历就是对树中任意结点，

1. 先遍历其左子树
2. 再访问本身
3. 最后遍历其右子树

代码采用递归方式实现。

二叉树的后序遍历

后序遍历就是对树中任意结点，

1. 先遍历其左子树
2. 再遍历其右子树
3. 最后访问本身

代码采用递归方式实现。

二叉树的层次遍历

层次遍历，按树的层次，从根结点往下逐层访问每个结点，对于每一层的结点，先访问其左孩子，再访问右孩子。遇到的结点先访问，这和队列的出队入队的特性符合，所以用队列实现。

算法实现：

1. 初始化队列，将根结点入队，定义指针p指向出队元素
2. 从队列出队元素，p指向出队元素
3. 如果p的左孩子不为空，把左孩子入队
4. 如果p的右孩子不为空，把右孩子入队
5. 依次指向2，3，4步操作，直到队空，取不出元素

完整代码

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode {
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal(BinTree BT);

void PreorderTraversal(BinTree BT);

void PostorderTraversal(BinTree BT);

void LevelorderTraversal(BinTree BT);

void CreateBinaryTree(BinTree BT);


int main() {
    BinTree BT = CreatBinTree();
    printf("Inorder:");
    InorderTraversal(BT);
    printf("\n");
    printf("Preorder:");
    PreorderTraversal(BT);
    printf("\n");
    printf("Postorder:");
    PostorderTraversal(BT);
    printf("\n");
    printf("Levelorder:");
    LevelorderTraversal(BT);
    printf("\n");
    return 0;
}

/**
 * 前序遍历
 * @param BT 树结点
 */
void PreorderTraversal(BinTree BT) {
    //结点为空就返回
    if (BT == NULL) return;
    //打印结点元素
    printf(" %c", BT->Data);
    //往左子树递归
    PreorderTraversal(BT->Left);
    //往右子树递归
    PreorderTraversal(BT->Right);
}

/**
 * 中序遍历
 * @param BT 树结点
 */
void InorderTraversal(BinTree BT) {
    //结点为空就返回
    if (BT == NULL) return;
    //往左子树递归
    InorderTraversal(BT->Left);
    //打印结点元素
    printf(" %c", BT->Data);
    //往右子树递归
    InorderTraversal(BT->Right);
}


/**
 * 后序遍历
 * @param BT 树结点
 */
void PostorderTraversal(BinTree BT) {
    //结点为空就返回
    if (BT == NULL) return;
    //往左子树递归
    PostorderTraversal(BT->Left);
    //往右子树递归
    PostorderTraversal(BT->Right);
    //打印结点元素
    printf(" %c", BT->Data);
}

/**
 * 层次遍历
 * @param T 树结点
 */
void LevelorderTraversal(BinTree BT) {
    int rear = 0, front = 0;
    //模拟队列
    BinTree ptr[100] = {NULL}, p = NULL;
    if (BT != NULL) {
        //队列第一个元素是根结点
        ptr[rear] = BT;
        rear++;
        //队列不为空
        while (rear > front) {
            //访问队列结点，模拟出队
            p = ptr[front];
            front++;
            printf(" %c", p->Data);
            if (p->Left != NULL) {
                //左孩子入队
                ptr[rear] = p->Left;
                rear++;
            }
            if (p->Right != NULL) {
                //右孩子入队
                ptr[rear] = p->Right;
                rear++;
            }
        }
    }
}

BinTree CreatBinTree() {
    char c;
    scanf("%c", &c);
    //判空
    if (c == '#') return NULL;
    BinTree T = (BinTree) malloc(sizeof(struct TNode));
    //先序递归构建
    T->Data = c;
    T->Left = CreatBinTree();
    T->Right = CreatBinTree();
    return T;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

按照先序遍历的方式构建二叉树：