1.层序遍历
前面我们在二叉树的遍历里提到过层序遍历（Level Traversal）
设二叉树的根节点所在的层数为1的情况下，从二叉树的根节点出发，首先访问第1层的树根节点，
然后再从左到右访问第2层上的节点。接着是第3层的节点……以此类推，
上面这棵树的层序遍历就是3 9 20 15 7
该如何实现层序遍历呢？
后面我们学C++有现成的队列，现在我们可以使用以前写的队列来实现
Queue.h：
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> 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_node pQ->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 char 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，（存指针比存结构体好，所以这里存BTNode*）
我们需要修改一下 Queue.h 的 QueueDataType，typedef 的好处，这里就显现出来了。
我们只需要把 int 改成 BTNode* 就可以了，不需要改很多地方。
新Queue.h：
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> 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);//返回队列大小
它说，缺少 " { " ，这明显是胡说八道的，这里产生问题的原因是什么呢？
编译器原则：编译器认识 int，因为 int 是一个内置类型。但是 BTNode* 编译器并不认识，
就需要 "往上面" 去找这个类型。这里显然往上找，是找不到它的定义的，所以编译器会报错。
如果你要用这个类型，你就需要先定义这个类型。test.c文件中 #include "Queue.h" ，
相当于把这里的代码拷贝过去了。这时，由于BTNode*会在上面展开，导致找不到 BTNode* 。
把 #include 移到 定义类型的代码 的后面，可以解决问题吗？
可以！遗憾的是只能解决这里Queue.h 的问题，
但Queue.c 里怎么也找不到树的声明，那我们该怎么做，能彻底解决呢？
解决方案：前置声明。 这样就不会带来问题了，满足了先声明后使用。
（注意：前置声明不能用typedef后的声明，要用原生的声明（和编译器有关））
最终Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> // 前置声明 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我们模仿以前写的二叉树前中后序遍历写就行了。
最终层序遍历test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" typedef char 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; // A nodeA->right = nodeC; // B C nodeB->left = nodeD; // D E F nodeC->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
给你一颗树，怎么判断这棵树是不是完全二叉树？
思路：采用层序遍历的思想，但是空结点也入队列，空结点出队列后不能再有非空结点出队列，
否则返回false（第一个空结点后全是空结点就返回trul）
(把40行的nodeC改成nodeB，即F链到B的右孩子，就会打印1)
#include"Queue.h" typedef char 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; // A nodeA->right = nodeC; // B C nodeB->left = nodeD; // D E F nodeC->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前销毁队列，否则会导致内存泄漏 return false; } } QueueDestroy(&pQ); return true;//全为空就是完全二叉树 } int main() { BTNode* root = CreateBinaryTree(); //BinaryTreeLevelOrder(root); printf("%d\n", BinaryTreeComplete(root)); return 0; }
3.所有实现过的二叉树的接口函数
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" typedef char 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; // A nodeA->right = nodeC; // B C nodeB->left = nodeD; // D E F nodeC->left = nodeE; nodeC->right = nodeF; return nodeA; } //二叉树前序遍历 void PreOrder(BTNode* root) { //首先判断根是否为空，为空就返回 if (root == NULL) { printf("NULL "); // 暂时打印出来，便于观察 return; } //走到这里说明不为空，根据前序遍历，先访问根节点 printf("%c ", root->data); //然后遍历左子树（利用递归） PreOrder(root->left); //最后遍历右子树（利用递归） PreOrder(root->right); // A // B C // D E F 前序： 根 左 右 //执行输出： A B D NULL NULL NULL C E NULL NULL F NULL NULL } //二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); // A // B C // D E F 中序：左 根 右 //执行输出：NULL D NULL B NULL A NULL E NULL C NULL F NULL } //二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); // A // B C // D E F 后序：左 右 根 //执行输出：NULL NULL D NULL B NULL NULL E NULL NULL F C A } int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } int TreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return TreeLeafSize(root->left) + TreeLeafSize(root->right); } int TreeKLevelSize(BTNode* root, int k) { assert(k > 0); if (root == NULL) { return 0; } if (k == 1) { return 1; } return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1); } // 查找树里面值为x的那个节点 BTNode* TreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* lret = TreeFind(root->left, x); if (lret) { return lret; } BTNode* rret = TreeFind(root->right, x); if (rret) { return rret; } return NULL; } // 一般，如果选择一级指针，存在野指针问题，调用BinaryTreeDestory的人，把指针置空 // 这样保持接口的一致性 void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); //printf("%p %c\n", root, root->data); free(root); root = NULL; } 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); // 销毁队列 } 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前销毁队列，否则会导致内存泄漏 return false; } } QueueDestroy(&pQ); return true;//全为空就是完全二叉树 } int main() { BTNode* root = CreateBinaryTree(); PreOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); printf("TreeSize:%d\n", TreeSize(root)); printf("TreeLeafSize:%d\n", TreeLeafSize(root)); printf("TreeKLevelSize:%d\n", TreeKLevelSize(root, 3)); printf("TreeFind:%p\n", TreeFind(root, 'E')); printf("TreeFind:%p\n", TreeFind(root, 'F')); printf("TreeFind:%p\n", TreeFind(root, 'X'));//打印0 ：找不到 BinaryTreeLevelOrder(root); printf("\n"); printf("%d", BinaryTreeComplete(root)); BinaryTreeDestory(root); root = NULL; return 0; }
4.二叉树遍历_牛客题霸_牛客网 (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 <stdio.h> 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<stdio.h> #include<stdlib.h> typedef 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; }
