C++ 二叉树的层次建树及其遍历_二叉树 层序遍历 c++

总结归纳

1. 先序遍历：根左右；中序遍历：左根右；后序遍历：左右根。
2. 若选取层次建树，则需要一个链式队列辅助实现 (规定，不必问为什么) 。若选取层次遍历，也需要一个链式队列辅助实现。
3. 该辅助队列的具体操作流程（重点理解）： 队列结点的数据域 p 存放的是树结点的地址 ( BiTNode *p 类型 ) ，头指针 phead 指向该队列头部，尾指针 ptail 指向该队列尾部，队列指针 pCur 始终指向当前操作位置，当前操作位置指的是：有新结点加入二叉树时，新结点作为队列指针 pCur 所指向的树结点（队列结点的数据域）的子孩子。此时，若 pCur 所指向树结点的左孩子为空，将新结点置为该树结点的左孩子，并通过尾插法加入队列，更新队尾指针；若此时右孩子为空，将新结点置为该树结点的右孩子，更新队尾指针，因为此时 pCur 指针所指向的树结点左右孩子皆满，使得 pCur 指针右移，下次新结点入队时，pCur 指针指向的树结点的左孩子就又为空。
4. 层次遍历的具体流程（重点理解）： 首先使根结点入队，循环判断队列是否为空，若队列不为空，让队头出队，并使该队头结点指向的树结点的左右孩子入队（没有则不做处理），然后继续循环判断。根据队列先进先出的特性，每个头结点出队后，该头结点所指向的树结点的左右孩子立即入队，在逻辑上左右孩子紧邻头结点，符合层次遍历的要求。
5. 层次建树的难点在于，较为复杂且难以理解，最后再总结一下：定义树结点，定义链式队列结点，队列结点的数据域为树结点的地址（BiTNode *p 类型）。树结点入树时，首先将队列结点通过尾插法入队，并通过 pCur 指针指向的队列结点的数据域拿到对应树结点的地址，再对左右孩子进行判空，然后入树。
6. 在该代码中，pCur 是每次建树时重新定义的，所以在建树最后，要释放并置为 NULL ，如果不这么做，可以将 pCur 置为全局变量。也可以将头尾指针定义在队列内部，可以使得建树函数 BuildBinaryTree() 少传些参数，总之方法很多，均能实现。
7. 该代码中所有函数均位于一个文件，弊端就在于：对于 EnQueue( ) 、DeQueue( ) 等函数需要根据树结点的定义特殊处理，我使用的 VS Code，只能出此下策。更好的办法是，利用 VS Studio 引用头文件的功能，直接引用封装好的队列代码，只需修改 typedef 对 ElemType 的重命名即可代替所有的特殊处理。

代码实践

#include <iostream>

#define MaxSize 10 // 栈中元素的最大个数

using namespace std;

typedef char ElemType;

// 树
struct BiTNode {
    ElemType data;            // 数据域
    BiTNode *lchild, *rchild; // 左孩子，右孩子
};

// 辅助队列结点，不带头结点，通过头指针 phead 访问
struct LinkNode {
    BiTNode *p; // 树中对应结点的地址
    LinkNode *pNext;
};

// 链式队列，辅助层次遍历
struct LinkQueue {
    LinkNode *front, *rear; // 队头指针，队尾指针
};

typedef BiTNode *BiTree; // 代指二叉树

// 树的初始化
bool InitTree(BiTree &T) {
    T = NULL;
    return true;
}

//层次建树
void BuildBinaryTree(BiTree &T, LinkNode *&phead, LinkNode *&ptail,
                     ElemType val) {
    // 此处申请空间，不能使用new，会进入死循环，我也不知道为啥
    BiTNode *pTreeNew =
        (BiTNode *)calloc(1, sizeof(BiTNode)); // 为树结点申请空间
    LinkNode *pQueueNew =
        (LinkNode *)calloc(1, sizeof(LinkNode)); // 为队列结点申请空间
    LinkNode *pCur = phead; // 始终指向当前操作位置

    pTreeNew->data = val;    // 树结点的赋值
    pQueueNew->p = pTreeNew; // 队列新结点的数据域为树的新结点

    if (T == NULL) { // 空树时，新结点置为树根
        T = pTreeNew;
        phead = pQueueNew;
        ptail = pQueueNew;
    } else {
        ptail->pNext = pQueueNew; //尾插法
        ptail = pQueueNew;        // 更新尾指针

        if (pCur->p->lchild == NULL) { // 左孩子为空
            pCur->p->lchild = pTreeNew;
        } else if (pCur->p->rchild == NULL) { // 右孩子为空
            pCur->p->rchild = pTreeNew;
            phead = pCur->pNext; //该结点左右孩子已满，队头指针后移
            free(pCur);          // 该代码中，PCur
                        // 是每次建树时重新定义的，所以在建树最后，要释放并置为
                        // NULL
            pCur = NULL;
        }
    }
}

//前序遍历（深度优先遍历）：根左右
void PreOrder(BiTNode *p) {
    if (p != NULL) {
        putchar(p->data);
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

// 中序遍历：左根右
void InOrder(BiTNode *p) {
    if (p != NULL) {
        InOrder(p->lchild);
        putchar(p->data);
        InOrder(p->rchild);
    }
}

// 后序遍历：左右根
void PostOrder(BiTNode *p) {
    if (p != NULL) {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->data);
    }
}

// 初始化队列
bool InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = new LinkNode; // 为队列申请一个结点作为头结点
    Q.front->pNext = NULL;
    return true;
}

// 队列判空
bool QueueEmpty(LinkQueue &Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}

// 入队
bool EnQueue(LinkQueue &Q, BiTNode *x) {
    LinkNode *p = new LinkNode;
    p->p = x;
    p->pNext = NULL;
    Q.rear->pNext = p; // 入队
    Q.rear = p;        // 更新队尾
    return true;
}

// 出队
bool DeQueue(LinkQueue &Q, BiTNode *&x) {
    if (Q.rear == Q.front) {
        return false;
    } else {
        LinkNode *p = Q.front->pNext; // 指向队头元素
        x = p->p;
        Q.front->pNext = p->pNext;
        if (Q.rear == p) { // 即队列中只剩一个元素
            Q.front = Q.rear;
        }
        delete p;
        return true;
    }
}

// 层序遍历，广度优先遍历
void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitQueue(Q);
    BiTNode *p;
    EnQueue(Q, T); // 树根入队
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p); // p为引用，此时p为对应的树结点
        putchar(p->data);
        if (p->lchild != NULL) {
            EnQueue(Q, p->lchild);
        }
        if (p->rchild != NULL) {
            EnQueue(Q, p->rchild); // 立即使p的左右孩子入队，保证层序遍历
        }
    }
}

int main() {
    ElemType val;
    BiTree T;
    InitTree(T);

    LinkNode *phead = NULL;
    LinkNode *ptail = NULL; // 头指针，尾指针
    while (scanf("%c", &val) != EOF) {
        if (val == '\n') {
            break;
        } else {
            BuildBinaryTree(T, phead, ptail, val);
        }
    }

    cout << "-----前序遍历-----" << endl;
    PreOrder(T);
    cout << endl;

    cout << "-----中序遍历-----" << endl;
    InOrder(T);
    cout << endl;

    cout << "-----后序遍历-----" << endl;
    PostOrder(T);
    cout << endl;

    cout << "-----层序遍历-----" << endl;
    LevelOrder(T);
    cout << endl;

    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
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187