大家好，又见面了，我是你们的朋友全栈君。
二叉树层次遍历
层次遍历基础需要了解二叉树、队列。
二叉树基本运算：https://blog.csdn.net/weixin_42109012/article/details/92000919
顺序队基本运算：https://blog.csdn.net/weixin_42109012/article/details/92104948
1. 算法思想
用一个队列保存被访问的当前节点的左右孩子以实现层次遍历。
在进行层次遍历的时候，设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：
- 访问该元素所指向的节点
- 若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。
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);
}
}
4. 结果展示
创建二叉树是以 “#” 为结束符NULL。
例子就是最上面的图：ABDH###E##CF##G##
结果应该为：ABCDEFGH
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/135126.html原文链接：https://javaforall.net
