二叉树层次遍历算法——C/C++_c++二叉树的层序遍历

二叉树层次遍历

层次遍历基础需要了解二叉树、队列。
二叉树基本运算：https://blog.csdn.net/weixin_42109012/article/details/92000919
顺序队基本运算：https://blog.csdn.net/weixin_42109012/article/details/92104948

1. 算法思想

用一个队列保存被访问的当前节点的左右孩子以实现层次遍历。
在进行层次遍历的时候，设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

1. 访问该元素所指向的节点
2. 若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。

2. 原理解释

2.1. 二叉树图

一个二叉树，层次遍历就是每一行每一行的取出数据。
这个图的结果就是 ABCDEFGH

2.2. 层次遍历过程图

就是先父节点进入队列，然后循环，出队时带入下一组子节点进队，没有就没有进入队列的，当队列为空时结束循环。

3. 代码实现

3.1 实现步骤

1、首先将二叉树的根节点进入队列中，判断队列不为NULL。
2、打印输出该节点存储的元素。
3、判断节点如果有孩子（左孩子、右孩子），就将孩子进入队列中。
4、循环以上操作，直到 BT->lchild == NULL、BT->rchild=NULL。

3.2 全部代码

#define _CRT_SECURE_NO_WARNINGS // VS忽略警告，其它应该不需要

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

#define MAX_SIZE 128
#define STR_SIZE 1024

typedef struct Node {    // 定义二叉链
    char         data;   // 数据元素
    struct Node* lchild; // 指向左孩子节点
    struct Node* rchild; // 指向右孩子节点
} BTNode;                // struct Node 的别名

typedef struct Quene {      // 定义顺序队
    int     front;          // 队头指针
    int     rear;           // 队尾指针
    BTNode* data[MAX_SIZE]; // 存放队中元素
} SqQueue;                  // struct Queue 的别名

/**
 * 队列函数
 */
void initQueue(SqQueue** q);             // 初始化队列
bool emptyQueue(SqQueue* q);             // 判断队列空
bool enQueue(SqQueue* q, BTNode* node);  // 入队
bool deQueue(SqQueue* q, BTNode** node); // 出队

/**
 * 二叉树函数
 */
// void createBTNode2(BTNode** BT);                  // 创建二叉树
int  createBTNode(BTNode** BT, char* str, int n); // 创建二叉树
void preOrder(BTNode* BT);                        // 前序遍历
void inOrder(BTNode* BT);                         // 中序遍历
void postOrder(BTNode* BT);                       // 后序遍历
void levelOrder(BTNode* BT);                      // 层次遍历

/**
 * 画树函数
 */
void draw_level(BTNode* node, bool left, char* str); // 画分支
void draw(BTNode* root);                             // 画根节点

/***************************************************************************
 * @date    2019/12/08
 * @brief   层次遍历二叉树
 * @param   BT  二叉树根节点
 ***************************************************************************/
void levelOrder(BTNode* BT) {
    SqQueue* q;       // 定义队列
    initQueue(&q);    // 初始化队列
    if (BT != NULL) { // 根节点指针进队列
        enQueue(q, BT);
    }
    // 一层一层的把节点存入队列，当没有孩子节点时就不再循环
    while (!emptyQueue(q)) {      // 队不为空循环
        deQueue(q, &BT);          // 出队时的节点
        printf("%c", BT->data);   // 输出节点存储的值
        if (BT->lchild != NULL) { // 有左孩子时将该节点进队列
            enQueue(q, BT->lchild);
        }
        if (BT->rchild != NULL) { // 有右孩子时将该节点进队列
            enQueue(q, BT->rchild);
        }
    }
}

int main() {
    // 例子：ABDH###E##CF##G##
    BTNode* BT;
    printf("请输入字符串：");
    char* str = (char*)malloc(sizeof(char) * STR_SIZE);
    scanf("%s", str);
    if (strlen(str) == createBTNode(&BT, str, 0)) {
        printf("二叉树建立成功\n");
    }
    // printf("请输入字符串：");
    // createBTNode2(&BT);
    // draw(BT);

    printf("\n先序遍历结果：");
    preOrder(BT);

    printf("\n中序遍历结果：");
    inOrder(BT);

    printf("\n后序遍历结果：");
    postOrder(BT);

    printf("\n层序遍历结果：");
    levelOrder(BT);

    return 0;
}

// 初始化队列
void initQueue(SqQueue** q) {
    if (!((*q) = (SqQueue*)malloc(sizeof(SqQueue)))) {
        printf("内存分配失败！");
        exit(-1);
    }
    (*q)->front = (*q)->rear = -1; // 置 -1
}

// 判断队列是否为空
bool emptyQueue(SqQueue* q) {
    // 首指针和尾指针相等，说明为空。空-返回真，不空-返回假
    if (q->front == q->rear) {
        return true;
    }
    return false;
}

// 进队列
bool enQueue(SqQueue* q, BTNode* node) {
    // 判断队列是否满了。满（插入失败）-返回假，不满（插入成功）-返回真
    if (q->rear == MAX_SIZE - 1) {
        return false;
    }
    q->rear++;               // 头指针加 1
    q->data[q->rear] = node; // 传值
    return true;
}

// 出队列
bool deQueue(SqQueue* q, BTNode** node) {
    // 判断是否空了。空（取出失败）-返回假，不空（取出成功）-返回真
    if (q->front == q->rear) {
        return false;
    }
    q->front++;                // 尾指针加 1
    *node = q->data[q->front]; // 取值
    return true;
}

// 创建二叉树
int createBTNode(BTNode** BT, char* str, int n) {
    char ch = str[n++];  // 把第 n 个字符赋给ch,方便后面判断，字符下标后移
    if (ch != '\0') {    // 如果 ch 不等于结束符就继续创建，否则就结束
        if (ch == '#') { // 以 # 号代表 NULL，下面没有了
            *BT = NULL;
        } else {
            if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
                printf("内存分配失败！");
                exit(-1);
            } else {
                (*BT)->data = ch;
                n           = createBTNode(&((*BT)->lchild), str, n); // 左递归创建
                n           = createBTNode(&((*BT)->rchild), str, n); // 右递归创建
            }
        }
    }
    // 返回 n，记录字符串使用到哪里了
    return n;
}
// 创建二叉树
// void createBTNode2(BTNode** BT) {
//     char ch;
//     ch = getchar();
//     if (ch == '#') {
//         *BT = NULL;
//     } else {
//         if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
//             printf("内存分配失败！");
//             return;
//         } else {
//             (*BT)->data = ch;
//             createBTNode2(&((*BT)->lchild)); // 分配成功则接着建立左子树和右子树
//             createBTNode2(&((*BT)->rchild));
//         }
//     }
// }

// 先序遍历
void preOrder(BTNode* BT) {
    if (BT != NULL) {           // 判断不为空
        printf("%c", BT->data); // 访问根节点
        preOrder(BT->lchild);   // 递归，先序遍历左子树
        preOrder(BT->rchild);   // 递归，先序遍历右子树
    }
}

// 中序遍历
void inOrder(BTNode* BT) {
    if (BT != NULL) {
        inOrder(BT->lchild);
        printf("%c", BT->data);
        inOrder(BT->rchild);
    }
}

// 后序遍历
void postOrder(BTNode* BT) {
    if (BT != NULL) {
        postOrder(BT->lchild);
        postOrder(BT->rchild);
        printf("%c", BT->data);
    }
}

/*****************************************************************************
* @date   2020/4/19
* @brief  水平画树
* @param  node	二叉树节点
* @param  left	判断左右
* @param  str 	可变字符串
*****************************************************************************/
void draw_level(BTNode* node, bool left, char* str) {
    if (node->rchild) {
        draw_level(node->rchild, false, strcat(str, (left ? "|     " : "      ")));
    }

    printf("%s", str);
    printf("%c", (left ? '\\' : '/'));
    printf("-----");
    printf("%c\n", node->data);

    if (node->lchild) {
        draw_level(node->lchild, true, strcat(str, (left ? "      " : "|     ")));
    }
    //  "      " : "|     " 长度为 6
    str[strlen(str) - 6] = '\0';
}

/*****************************************************************************
* @date   2020/4/19
* @brief  根节点画树
* @param  root	二叉树根节点
*****************************************************************************/
void draw(BTNode* root) {
    char str[STR_SIZE];
    memset(str, '\0', STR_SIZE);

    /**
     * 1. 在 windows 下，下面是可执行的
     * 2. 在 Linux   下，执行会报 Segmentation fault
     *      需要使用中间变量
     */
    if (root->rchild) {
        draw_level(root->rchild, false, str);
    }
    printf("%c\n", root->data);
    if (root->lchild) {
        draw_level(root->lchild, true, str);
    }
}
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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249

4. 结果展示

创建二叉树是以 “#” 为结束符NULL。
例子就是最上面的图：ABDH###E##CF##G##
结果应该为：ABCDEFGH