1.层序遍历

前面我们在二叉树的遍历里提到过层序遍历（Level Traversal）

链接：比特数据结构与算法（第四章_下）二叉树的遍历_GR C的博客-CSDN博客

设二叉树的根节点所在的层数为1的情况下，从二叉树的根节点出发，首先访问第1层的树根节点，

然后再从左到右访问第2层上的节点。接着是第3层的节点……以此类推，

上面这棵树的层序遍历就是3 9 20 15 7

该如何实现层序遍历呢？

我们可以之前用以前写的队列来实现

链接：比特数据结构与算法（第三章_下）队列的概念和实现（力扣：225+232+622）_GR C的博客-CSDN博客

Queue.h：

#pragma once#include 
#include 
#include 
#include typedef int QueueDataType;   //队列类型typedef struct QueueNode 
{struct QueueNode* next;  //指向下一个节点QueueDataType data;      //数据
} QueueNode;typedef struct Queue//如果不设置成结构体就需要传二级指针，还要传两个参数
{QueueNode* pHead;QueueNode* pTail;
} Queue;void QueueInit(Queue* pQ);//初始化队列
void QueueDestroy(Queue* pQ);//销毁队列
bool QueueEmpty(Queue* pQ);//判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);//入队
void QueuePop(Queue* pQ);//出队
QueueDataType QueueFront(Queue* pQ);//返回队头数据
QueueDataType QueueBack(Queue* pQ);//返回队尾数据
int QueueSize(Queue* pQ);//返回队列大小

Queue.c：

#include "Queue.h"void QueueInit(Queue* pQ) 
{assert(pQ);pQ->pHead = pQ->pTail = NULL;
}void QueueDestroy(Queue* pQ) 
{assert(pQ); QueueNode* cur = pQ->pHead;while (cur != NULL) {QueueNode* curNext = cur->next;  //防止释放cur后找不到其下一个节点free(cur);                     cur = curNext;                   }pQ->pHead = pQ->pTail = NULL; 
}bool QueueEmpty(Queue* pQ) 
{assert(pQ); return pQ->pHead == NULL;//如果成立则为True，不成立则为False
}//入队：队尾入数据，队头出(删)数据。如果是第一个入队的(队列为空)则既要当头又当尾
void QueuePush(Queue* pQ, QueueDataType x) 
{assert(pQ);QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));if (new_node == NULL){printf("malloc failed!\n");exit(-1);}new_node->data = x;     //待插入的数据new_node->next = NULL;  //新的数据指向空if (pQ->pHead == NULL)//情况1: 队列为空{           pQ->pHead = pQ->pTail = new_node;}else //情况2: 队列不为空   队尾入数据{                              pQ->pTail->next = new_node;  //在现有尾的后一个节点放置new_nodepQ->pTail = new_node;        //更新pTail，使它指向新的尾}
}void QueuePop(Queue* pQ) // 出队：队尾入数据，队头出(删)数据
{assert(pQ);                          assert(!QueueEmpty(pQ));  QueueNode* headNext = pQ->pHead->next; //队头出数据，防止释放pHead后找不到其下一个节点free(pQ->pHead);pQ->pHead = headNext;                  //更新头 if (pQ->pHead == NULL)//删完之后 pHead == NULL 了 pTail 还是野指针{pQ->pTail = NULL;//处理一下尾指针，将尾指针置空}
}QueueDataType QueueFront(Queue* pQ) //返回队头数据
{assert(pQ);                           assert(!QueueEmpty(pQ));    return pQ->pHead->data;
}QueueDataType QueueBack(Queue* pQ) //返回队尾数据
{assert(pQ);assert(!QueueEmpty(pQ));return pQ->pTail->data;
}int QueueSize(Queue* pQ) //返回队列大小
{assert(pQ);int count = 0;QueueNode* cur = pQ->pHead;while (cur != NULL) {count++;cur = cur->next;}return count;
}

test.c

#include "Queue.h"typedef int BTDataType;typedef struct BinaryTreeNode 
{struct BinaryTreeNode* left;       // 记录左节点struct BinaryTreeNode* right;      // 记录右节点BTDataType data;                   // 存储数据
} BTNode;//创建新节点
BTNode* CreateNode(BTDataType x) 
{BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));if (new_node == NULL){printf("malloc failed!\n");exit(-1);}new_node->data = x;new_node->left = new_node->right = NULL;return new_node;
}

由于是我们的数据类型是 BTNode，我们需要修改一下 Queue.h 的 QueueDataType，我们之前一直强调的 typedef 的好处，这里就显现出来了。我们只需要把 int 改成 BTNode 就可以了，而不需要改很多地方。

新Queue.h：

#pragma once#include 
#include 
#include 
#include typedef BTNode* QueueDataType;   //队列类型typedef struct QueueNode 
{struct QueueNode* next;  //指向下一个节点QueueDataType data;      //数据
} QueueNode;typedef struct Queue//如果不设置成结构体就需要传二级指针，还要传两个参数
{QueueNode* pHead;QueueNode* pTail;
} Queue;void QueueInit(Queue* pQ);//初始化队列
void QueueDestroy(Queue* pQ);//销毁队列
bool QueueEmpty(Queue* pQ);//判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);//入队
void QueuePop(Queue* pQ);//出队
QueueDataType QueueFront(Queue* pQ);//返回队头数据
QueueDataType QueueBack(Queue* pQ);//返回队尾数据
int QueueSize(Queue* pQ);//返回队列大小

它说，缺少 " { " ，这明显是胡说八道的，咱编译器也没有那么智能，毕竟是也不是VS2077。

这里产生问题的原因是什么呢？

编译器原则：编译器认识 int，因为 int 是一个内置类型。但是 BTNode* 编译器并不认识，就需要 "往上面" 去找这个类型。这里显然往上找，是找不到它的定义的，所以编译器会报错。

如果你要用这个类型，你就需要先定义这个类型。test.c文件中 #include "Queue.h" ，相当于把这里的代码拷贝过去了。这时，由于BTNode*会在上面展开，导致找不到 BTNode* 。

把 #include 移到 定义类型的代码 的后面，可以解决问题吗？

可以！遗憾的是只能解决这里 typedef BTNode* 的问题，还有 Queue.c 里的问题……

那我们该怎么做，能彻底解决呢？

解决方案：前置声明。 这样就不会带来问题了，满足了先声明后使用。

最终Queue.h

#pragma once#include 
#include 
#include 
#include // 前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QueueDataType;typedef struct QueueNode 
{struct QueueNode* next;  //指向下一个节点QueueDataType data;      //数据
} QueueNode;typedef struct Queue//如果不设置成结构体就需要传二级指针，还要传两个参数
{QueueNode* pHead;QueueNode* pTail;
} Queue;void QueueInit(Queue* pQ);//初始化队列
void QueueDestroy(Queue* pQ);//销毁队列
bool QueueEmpty(Queue* pQ);//判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);//入队
void QueuePop(Queue* pQ);//出队
QueueDataType QueueFront(Queue* pQ);//返回队头数据
QueueDataType QueueBack(Queue* pQ);//返回队尾数据
int QueueSize(Queue* pQ);//返回队列大小

弄完上面的终于可以写层序遍历了

思路如下：

① 让根节点先入队。

② 记录当前队头后打印，并让队头出队，然后检测，如过孩子不为空就把孩子带进去。

（上一层节点出队时带入下一层节点入队）

③ 只要队列不为空就说明还没完。如果队列为空，说明下面最后一层没有节点，遍历结束。

test.c我们模仿以前写的二叉树前中后序遍历写就行了。

链接：(1条消息) 比特数据结构与算法（第四章_下）二叉树的遍历_GR C的博客-CSDN博客

最终test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"
typedef int BTDataType;typedef struct BinaryTreeNode 
{struct BinaryTreeNode* left;       // 记录左节点struct BinaryTreeNode* right;      // 记录右节点BTDataType data;                   // 存储数据
} BTNode;//创建新节点
BTNode* CreateNode(BTDataType x) 
{BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));if (new_node == NULL){printf("malloc failed!\n");exit(-1);}new_node->data = x;new_node->left = new_node->right = NULL;return new_node;
}
//手动创建二叉树 
BTNode* CreateBinaryTree()
{BTNode* nodeA = CreateNode('A');BTNode* nodeB = CreateNode('B');BTNode* nodeC = CreateNode('C');BTNode* nodeD = CreateNode('D');BTNode* nodeE = CreateNode('E');BTNode* nodeF = CreateNode('F');nodeA->left = nodeB;         //           AnodeA->right = nodeC;        //       B        CnodeB->left = nodeD;         //    D        E    FnodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}
void BinaryTreeLevelOrder(BTNode* root) 
{if (root == NULL) {        // 判断根是否为空return;}Queue pQ;            // 建立队列QueueInit(&pQ);        // 初始化队列QueuePush(&pQ, root);    // 先让根进入队列while (!QueueEmpty(&pQ)) {    // 只要队列内还有元素，就进入循环BTNode* front = QueueFront(&pQ);    // 记录当前队头数据printf("%c ", front->data);  // 打印队头数据QueuePop(&pQ);     // 当队头出队if (front->left != NULL) {        // 如果队头元素的左子树不为空QueuePush(&pQ, front->left);    // 让左子树进入队列}if (front->right != NULL) {        // 如果队头元素的右子树不为空QueuePush(&pQ, front->right);    // 让右子树进入队列}}QueueDestroy(&pQ);     // 销毁队列
}
int main()
{BTNode* root = CreateBinaryTree();BinaryTreeLevelOrder(root);return 0;
}

2.判断是否是完全二叉树test.c

把40行的nodeC改成nodeB就会打印1

#include"Queue.h"
typedef int BTDataType;typedef struct BinaryTreeNode 
{struct BinaryTreeNode* left;       // 记录左节点struct BinaryTreeNode* right;      // 记录右节点BTDataType data;                   // 存储数据
} BTNode;//创建新节点
BTNode* CreateNode(BTDataType x) 
{BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));if (new_node == NULL){printf("malloc failed!\n");exit(-1);}new_node->data = x;new_node->left = new_node->right = NULL;return new_node;
}//手动创建二叉树 
BTNode* CreateBinaryTree()
{BTNode* nodeA = CreateNode('A');BTNode* nodeB = CreateNode('B');BTNode* nodeC = CreateNode('C');BTNode* nodeD = CreateNode('D');BTNode* nodeE = CreateNode('E');BTNode* nodeF = CreateNode('F');nodeA->left = nodeB;         //           AnodeA->right = nodeC;        //       B        CnodeB->left = nodeD;         //    D        E    FnodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}
bool BinaryTreeComplete(BTNode* root)
{Queue pQ;            // 建立队列QueueInit(&pQ);        // 初始化队列QueuePush(&pQ, root);    // 先让根进入队列while (!QueueEmpty(&pQ)){    // 只要队列内还有元素，就进入循环BTNode* front = QueueFront(&pQ);    // 记录当前队头数据QueuePop(&pQ);     //队头出队if (front == NULL){break;// 如果队头元素为空就跳出}else{QueuePush(&pQ, front->left);QueuePush(&pQ, front->right);}}//遇到空之后，检查队列剩下节点，while (!QueueEmpty(&pQ)){BTNode* front = QueueFront(&pQ);    // 记录当前队头数据QueuePop(&pQ);     //队头出队if (front)//只要一个不为空就不是完全二叉树{QueueDestroy(&pQ);return false;}}QueueDestroy(&pQ);return true;//全为空就是完全二叉树
}int main()
{BTNode* root = CreateBinaryTree();//BinaryTreeLevelOrder(root);printf("%d\n", BinaryTreeComplete(root));return 0;
}

3.二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

较难 通过率：34.75% 时间限制：1秒 空间限制：64M

知识点： 树 搜索

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树

（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F###

其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，

再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，

每个字符后面都有一个空格。 每个输出结果占一行。

示例1

输入：

abc##de#g##f###

输出：

c b e g d f a

#include int main() {int a, b;while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case// 64 位输出请用 printf("%lld") to printf("%d\n", a + b);}return 0;
}

代码解析：

#include
#includetypedef struct TreeNode
{struct TreeNode* left;struct TreeNode* right;char val;
}TreeNode;TreeNode* CreateTree(char* str, int* pi)
{if (str[*pi] == '#'){(*pi)++;return NULL;}//不是# 构造根TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = str[*pi];(*pi)++;root->left = CreateTree(str, pi);//递归构建左子树root->right = CreateTree(str, pi);//递归构建右子树return root;
}void Inorder(TreeNode* root)
{if (root == NULL){return;}Inorder(root->left);printf("%c ", root->val);Inorder(root->right);
}int main()
{char str[100] = { 0 };scanf("%s", str);int i = 0;TreeNode* root = CreateTree(str, &i);Inorder(root);printf("\n");return 0;
}

本篇完。

第四章二叉树算是暂时结束了，先提前学学C++把蓝桥杯过了再更博客。

下一章第五章讲讲八大排序算法，数据结构初阶就结束了。然后开始更C++了。