数据结构修炼——树？二叉树？堆？从入门到代码实现，第二弹！！！
目录
- 一、二叉树的链式结构与实现
- 1.1 二叉树的创建与销毁
- 1.1.1 前序、中序、后序遍历
- 1.1.2 创建与销毁
- 1.2 结点个数
- 1.2.1 二叉树结点个数
- 1.2.2 二叉树叶子结点个数
- 1.2.3 第k层结点个数
- 1.3 求二叉树的深度
- 1.4 二叉树查找值
- 1.5 前序/中序/后序遍历
- 1.6 层序遍历
- 1.7 判断完全二叉树
- 二、OJ练习
- 2.1 单值二叉树
- 2.2 相同的树
- 2.3 对称二叉树
- 2.4 二叉树的前序遍历
- 2.5 二叉树的中序遍历
- 2.6 二叉树的后序遍历
- 2.7 另一棵树的子树
- 三、树、二叉树、堆基础知识选择题
在上一篇，我们学习了树、二叉树与堆的相关基础知识，同时实现了堆与完成了堆的一些简单应用。我们知道，二叉树的存储结构有顺序结构与链式结构，堆实现的是特殊完全二叉树的顺序结构，本篇，我们实现的是二叉树的链式结构。
一、二叉树的链式结构与实现
上一篇提到，链式结构又分为二叉链和三叉链，所谓“二叉”，“三叉”是指链表结点指向的结点的个数。例如：
typedef int DataType;
struct Node
{struct Node* firstChild1;// 第一个孩子结点struct Node* pNextBrother;// 下一个兄弟结点（一般从左至右）DataType data;// 当前结点存储的值
};示例为孩子兄弟法表示的链式结构，即为二叉链。
本篇二叉树的链式结构的实现将采取孩子表示法，如下。
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;// 数据域struct BinaryTreeNode* left;// 左孩子结点struct BinaryTreeNode* right;// 右孩子结点
}BTNode;
二叉树的链式结构的基本实现需要完成二叉树的构建与销毁，二叉树的前序、中序、后序、层序遍历以及求结点个数等操作。同时树里有一个深度的概念，所以还需要实现求二叉树深度的操作。
给出头文件以及具体实现如下：
#pragma
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 通过前序遍历构建二叉树
BTNode* BTCreate(BTDataType* arr, int size, int* pi);
// 二叉树销毁
void BTDestroy(BTNode* root);
// 二叉树节点个数
int BTSize(BTNode* root);
// 二叉树叶子节点个数
int BTLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BTLevelKSize(BTNode* root, int k);
// 二叉树深度
int BTHeight(BTNode* root);
// 二叉树查找值为x的节点
BTNode* BTFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BTPrevOrder(BTNode* root);
// 二叉树中序遍历
void BTInOrder(BTNode* root);
// 二叉树后序遍历
void BTPostOrder(BTNode* root);
// 层序遍历
void BTLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BTComplete(BTNode* root);
1.1 二叉树的创建与销毁
1.1.1 前序、中序、后序遍历
在开始之前，我们需要关注一个问题——如何去解读树？
堆是顺序结构存储的特殊完全二叉树，堆本质上就是一个数组，所以在实现堆时，我们直接按从上到下，从左到右的顺序解读二叉树并获取数据依次放入数组存储即可。但链式结构不同，链式结构的存储结构并不是线性的，而数据文本却是连串的字符，我们如何将数据依次放入结点构建成二叉树呢？
我们来看下面的两张图，这是第一部分开篇的两张图。
对于下面的几颗树，我们想要将类似图形结构转换成文本数据，就需要选择某种规则依次遍历树的各个结点读取数据。这种规则就是树的遍历。
树的遍历分为两种规则——深度优先遍历与广度优先遍历。
- 深度优先遍历：深度优先是指先遍历完一条完整的路径（从根到叶子的完整路径），再折返回到最上层，遍历下一个路径；
- 广度优先遍历：广度优先是指把下一步所有可能位置全部遍历完，才会进行更深层次的遍历。即从顶部到底部按层次遍历二叉树，每一层按照从左到右的顺序访问结点。
其中深度优先遍历有前序遍历，中序遍历，后序遍历，广度优先遍历有层序遍历。
- 前序遍历：按照根——左子树——右子树的顺序遍历；
- 中序遍历：按照左子树——根——右子树的顺序遍历；
- 后序遍历：按照左子树——右子树——根的顺序遍历；
- 层序遍历：按层次，即从上到下，从左到右依次遍历。
所谓的前/中/后序遍历其实就是按照根的遍历次序来划分，很好记忆。
那具体如何运用遍历规则遍历二叉树呢？
以下为前序遍历遍历二叉树：
前序遍历先遍历根得到数据1，再遍历结点1的左子树
左子树也是树，仍按前序遍历先遍历根，得到2，再遍历结点2的左子树
遍历结点2的左子树得到根——4，结点4的左子树为空，再遍历结点4的右子树得到
遍历结点4的右子树的根，得到6，结点6的左子树为空，结点6的右子树为空，结点2的左子树遍历完成，遍历结点2的右子树
遍历结点2的右子树得到根——5，再遍历结点5的左右子树，空空，遍历完1的左子树，遍历1的右子树
结点1的根——3，左子树——空，右子树——空。
所以上述二叉树的图形结构通过前序遍历得到的文本数据为124653，实际完整的遍历过程为124#6##5##3##（以#代替空）。
中序、后序遍历与前序遍历大体相同，大家可以像我一样不断分解根，左子树与右子树并画图分析理解一下，再尝试完成中序遍历与后序遍历，这里就不过多繁琐介绍了，后面代码部分还可以继续加深理解。
中序遍历的结果为#4#6#2#5#1#3#，后序遍历结果为###64##52##31。
1.1.2 创建与销毁
通常，我们可以得到类似文本数据如：124#6##5##3##。我们需要按照任一遍历规则来创建二叉树。
代码示例如下：
// 通过前序遍历构建二叉树
BTNode* BTCreate(BTDataType* arr, int size, int* pi)
{assert(arr && pi);if (arr[*pi] == '#'){(*pi)++;return NULL;}BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (!node){perror("BinaryTreeCreat::malloc fail!");exit(1);}node->data = arr[(*pi)++];node->left = BTCreate(arr, size, pi);node->right = BTCreate(arr, size, pi);return node;
}
代码是以递归的方式实现的。其中，参数arr是数组，参数size是数据长度，参数pi是指向数组下标的指针。*pi初始值是0，也就是指向第一个数组元素，每当一个数据放入树中就执行一次(*pi)++找到下一个下标。
而整体的递归逻辑就是前序遍历的逻辑，先创建根结点node并放入数据node->data = arr[(*pi)++];，再递归创建根结点的左子树node->left = BTCreate(arr, size, pi);，再递归创建根结点的右子树node->right = BTCreate(arr, size, pi);，最后返回当前根结点。这里面可能存在为空的情况，为空就不需要创建根结点，提前return NULL即可。
下面给出序列12#6##5##，通过前序遍历构建二叉树时函数的递归过程如下：
链表结构如下：
那么如何通过中序遍历或者后序遍历构建二叉树呢？其实只需要调整根结点的创建，左子树的创建和右子树的创建的位置关系即可。
// 中序-先左再根再右
node->left = BTCreate(arr, size, pi);
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (!node)
{perror("BinaryTreeCreat::malloc fail!");exit(1);
}
node->data = arr[(*pi)++];
node->right = BTCreate(arr, size, pi);
// 后序-先左再右再根
node->left = BTCreate(arr, size, pi);
node->right = BTCreate(arr, size, pi);
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (!node)
{perror("BinaryTreeCreat::malloc fail!");exit(1);
}
node->data = arr[(*pi)++];
理解了这个思想销毁就很简单了。二叉树的销毁只能采用后序遍历，因为如果是前序或中序那么上面结点就被销毁了，下面的结点就找不到了，递归也就无从谈起，因此用后序遍历销毁二叉树更方便。
// 二叉树的销毁
void BTDestroy(BTNode* root)
{if (!root){return;}BTDestroy(root->left);BTDestroy(root->right);free(root);
}
1.2 结点个数
1.2.1 二叉树结点个数
对于任一二叉树我们该如何对整颗树求结点个数呢？和构建二叉树类似，我们可以利用递归的思想将其分解为单个的子问题——即根个数+左子树结点个数+右子树结点个数。
代码示例如下：
// 二叉树节点个数
int BTSize(BTNode* root)
{return root == NULL ? 0 :BTSize(root->left) + BTSize(root->right) + 1;
}
代码逻辑：根为空则返回0，根不为空则返回1加左子树的结点个数加右子树的结点个数。
1.2.2 二叉树叶子结点个数
同样利用递归的思想，我们将大问题分解为子问题——左子树叶子结点个数+右子树叶子结点个数。
代码示例如下：
// 二叉树叶子节点个数
int BTLeafSize(BTNode* root)
{if (!root){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BTLeafSize(root->left) + BTLeafSize(root->right);
}
代码逻辑：当前结点为空，不是叶子结点，返回0；当前结点不为空，但左右孩子都为空，是叶子结点，返回1；当前结点不为空，且左右孩子不都为空，则求当前结点左子树中的叶子结点个数加右子树的叶子结点个数。
1.2.3 第k层结点个数
// 二叉树第k层节点个数
int BTLevelKSize(BTNode* root, int k)
{if (!root){return 0;}if (k == 1){return 1;}return BTLevelKSize(root->left, k - 1)+ BTLevelKSize(root->right, k - 1);
}
代码逻辑：类似地，求第k层结点个数可以拆解成子问题——求左子树中第k-1层结点个数加右子树中第k-1层结点个数。
当前结点为空，则返回0；当前结点不为空，且k=1，则当前结点为第k层结点，返回1；当前结点不为空，且k>1，则继续往更下一层的左/右子树找符合条件的结点。
1.3 求二叉树的深度
子问题——求左子树的深度与右子树的深度，比较取最大值。。
代码示例如下：
// 二叉树深度
int BTHeight(BTNode* root)
{if (!root){return 0;}return BTHeight(root->left) > BTHeight(root->right) ?BTHeight(root->left) + 1 : BTHeight(root->right) + 1;
}
这段代码有些坑需要注意，逻辑上貌似正确，求左子树深度，再求右子树深度，一个三目操作符比较判断一下，如果左子树深度更深则取左子树的深度并加1，如果右子树深度更深则取右子树的深度并加1。但最致命的问题在于递归的重复调用，短短一个return不止调用了4次函数，至少分别遍历了两遍当前根结点的左右子树，其实再分下去左、右子树还有子树，这种子树的划分和套娃一样是呈倍数增长的，消耗的资源过于恐怖，子树可能不止遍历一两次。
所以在使用递归时，如果有返回值，且需要多次用到这个返回值时一定要确保返回值先保存下来。正确示例如下：
// 二叉树深度
int BTHeight(BTNode* root)
{if (!root){return 0;}// 先保存返回值再比较int Left = BTHeight(root->left);int right = BTHeight(root->right);return Left > right ? Left + 1 : right + 1;
}
1.4 二叉树查找值
如何在二叉树中查找到所需要的数据值呢？也很简单，分解成子问题——检查当前根结点，若不是则继续查找左、右子树。
代码示例如下：
// 二叉树查找值为x的节点
BTNode* BTFind(BTNode* root, BTDataType x)
{if (!root){return NULL;}if (root->data == x){return root;}BTNode* ret = BTFind(root->left, x);if (ret){return ret;}return BTFind(root->right, x);
}
代码逻辑：根为空，没有数据，直接返回空；根不为空，先判断是否是查找值，有则返回，没有则先查找左子树。如果左子树查找到了，返回值不为空直接返回所需结点。如果没有查找到，那返回值为空，继续查找右子树，最后直接返回右子树的查找结果。
1.5 前序/中序/后序遍历
前面我们已经介绍过了前序/中序/后序遍历的概念以及如何运用它们解读二叉树。但现在我们需要使用对应规则来遍历打印二叉树中的数据，该怎么操作呢？
代码示例如下：
// 二叉树前序遍历
void BTPrevOrder(BTNode* root)
{if (!root){printf("N ");// 结点为空就打印Nreturn;}printf("%c ", root->data);// 结点不为空就打印数据BTPrevOrder(root->left);BTPrevOrder(root->right);
}
// 二叉树中序遍历
void BTInOrder(BTNode* root)
{if (!root){printf("N ");return;}BTInOrder(root->left);printf("%c ", root->data);BTInOrder(root->right);
}
// 二叉树后序遍历
void BTPostOrder(BTNode* root)
{if (!root){printf("N ");return;}BTPostOrder(root->left);BTPostOrder(root->right);printf("%c ", root->data);
}
1.6 层序遍历
层序遍历的规则好像很简单，那我们该如何实现呢？
实际上，我们需要用到队列来解决。按照层序遍历的规则将结点先后入队，上一层结点带下一层结点。
直接来看代码示例与分析。
// 层序遍历：借助队列先进先出上一层带下一层入队
void BTLevelOrder(BTNode* root)
{Queue q;// 创建队列qQueueInit(&q);// 队列初始化操作// 开始对二叉树进行判断if (root){QueuePush(&q, root);// 根结点不为空，入队}while (!QueueEmpty(&q))// 队列为空时循环停止{QDataType front = QueueFront(&q);// 获取队头，即前一个结点QueuePop(&q);// 队头，即前一个结点出队printf("%c ", front->data);// 前一个结点出队，该结点的左右孩子入队（需要不为空）if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);// 遍历完成，销毁队列
}
假设有如下二叉树：
- 我们先创建一个队列，根结点1先入队（此时队列：1）；
- 遍历开始，队头1先出，出去时该结点的左孩子2，右孩子3依次入队（此时队列：2，3）；
- 新队头2再出，左孩子4，右孩子5依次入队（此时队列：3，4，5）；
- 新队头3出队，左右孩子为空不需要入队（此时队列：4，5）；
- 新队头4出队，右孩子6入队（此时队列：5，6）；
- 新队头5出队，左右孩子为空不入队（此时队列：6）；
- 新队头6出队，左右孩子为空不入队，此时队列为空，代表二叉树遍历完成，结束。
这套逻辑很好理解，层序遍历的结果为：123456。
1.7 判断完全二叉树
我们知道，完全二叉树是特殊的二叉树，我们如何利用代码去判断一棵二叉树是否是完全二叉树呢？
我们同样可以利用队列来判断。可以发现，完全二叉树只有最后一层存在空。如果我们借助队列上一层结点带下一层结点的话，那么从根结点开始，有效结点一定是连续的，中间不存在空，空都在后面而且不再存在有效结点存在。所以我们可以利用按上面的层序遍历先遍历二叉树找到第一个空结点，再从空结点向后检查是否连续为空，连续为空就说明是完全二叉树，否则不是。
来看示例代码：
// 判断二叉树是否是完全二叉树
bool BTComplete(BTNode* root)
{Queue q;// 创建队列QueueInit(&q);// 初始化队列QueuePush(&q, root);// 根结点入队// 先遍历二叉树找到第一个空结点while (!QueueEmpty(&q)){QDataType front = QueueFront(&q);QueuePop(&q);if (!front){break;// 找到空结点，停止查找空结点，跳出循环}QueuePush(&q, front->left);QueuePush(&q, front->right);}// 检查第一个空结点后面是否都为空while (!QueueEmpty(&q)){QDataType front = QueueFront(&q);QueuePop(&q);if (front){// 空结点之后不连续为空，还存在有效结点QueueDestroy(&q);// 销毁队列return false;// 不是完全二叉树，返回false}}// 循环结束，没有提前返回，说明后面连续为空，符合条件QueueDestroy(&q);return true;// 是完全二叉树，返回true
}
二、OJ练习
下面推荐几道OJ练习用于回顾二叉树的知识。
2.1 单值二叉树
力扣 965.单值二叉树
这道题目需要我们检查二叉树所有有效结点中的数据是否相同。这里仍沿用前面递归的思想，拆分出子问题——根结点和它的左右孩子的值是否相同。整体逻辑则是，先检查根结点，再检查根结点的左子树，最后检查根结点的右子树。需要注意的是，空结点没有值，不需要判断，所以遇到空我们算作true，不影响最终结果，而一旦遍历时某一棵子树的根结点与它的左/右孩子不匹配就返回false，最终所有结果“与”在一起即为false。
来看示例代码：
bool isUnivalTree(struct TreeNode* root)
{if (!root) return true;if (root->left && root->left->val != root->val)return false;if (root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) &&isUnivalTree(root->right);
}
2.2 相同的树
力扣 100.相同的树
这道题目需要我们判断两棵二叉树是否完全相同。同样是一道典型的可以用递归思想轻松解决的题目。拆分成子问题——区分三种情况：p，q当前结点都为空；其中之一为空；都不为空。其中之一为空则一定不相同，都为空符合条件，都不为空需要检查值是否匹配。整体逻辑上，我们需要左对左、右对右同步遍历p，q两棵树的所有对应结点
来看代码示例：
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (!p && !q) return true;if (!p || !q) return false;if (p->val != q->val) return false;return isSameTree(p->left, q->left) &&isSameTree(p->right, q->right);
}
代码逻辑：若p，q同时为空，匹配，返回true；若p，q其中之一为空，另一不为空，不匹配，返回false；若p，q都不为空，检查两结点的值是否相等，不相等返回false；若p，q都不为空且值相等，还需要确定其后结点是否都匹配，继续遍历。
2.3 对称二叉树
力扣 101.对称二叉树
这道题其实就是上一题的改版，我们将上一题递归调用中传递的形参从左子树匹配左子树，右子树匹配右子树改成左子树匹配右子树，右子树匹配左子树即可。
来看示例代码：
bool _isSymmetric(struct TreeNode* l, struct TreeNode* r)
{if (!l && !r) return true;if (!l || !r) return false;if (l->val != r->val) return false;return _isSymmetric(l->left, r->right) &&_isSymmetric(l->right, r->left);
}
bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root->left, root->right);
}
2.4 二叉树的前序遍历
力扣 144.二叉树的前序遍历
分享这道题旨在巩固大家对于前序遍历的知识。这道题稍微不一样的是，我们前序遍历二叉树时不是打印数据，而是将数据依次存储进数组中并返回，同时有一形参returnSize需要在函数内部时刻记录数组长度。
代码示例如下：
int TreeNodeNums(struct TreeNode* root)// 获取二叉树总结点数
{if (!root) return 0;return TreeNodeNums(root->left) +TreeNodeNums(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* retArr, int* retSize)// 前序遍历
{if (!root) return;retArr[(*retSize)++] = root->val;PreOrder(root->left, retArr, retSize);PreOrder(root->right, retArr, retSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{// 先遍历二叉树获取结点个数size，即为数组最终大小int size = TreeNodeNums(root);// 创建size大小的数组retArr用于存储各结点数据，作为最终返回值int* retArr = (int*)malloc(size * sizeof(int));// 不直接赋值，先将returnSize置为0作为下标，存储一个数据就加1*returnSize = 0;// 准备工作完成，开始前序遍历PreOrder(root, retArr, returnSize);// 返回存储了遍历结果的数组retArrreturn retArr;
}
这题稍微麻烦一点的就是开始的准备工作，需要我们单独申请一个数组存储遍历结果，而获取二叉树结点个数与前序遍历我们早已实现过，非常简单。
2.5 二叉树的中序遍历
力扣 94.二叉树的中序遍历
这题要求和前序遍历的完全一致，但遍历方式需要改成中序遍历。
直接来看代码示例：
int TreeNodeNums(struct TreeNode* root)
{if (!root) return 0;return TreeNodeNums(root->left) +TreeNodeNums(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* retArr, int* retSize)
{if (!root) return;PreOrder(root->left, retArr, retSize);retArr[(*retSize)++] = root->val;PreOrder(root->right, retArr, retSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{int size = TreeNodeNums(root);int* retArr = (int*)malloc(size * sizeof(int));*returnSize = 0;PreOrder(root, retArr, returnSize);return retArr;
}
完全一致，非常简单。
2.6 二叉树的后序遍历
力扣 145.二叉树的后序遍历
这道题同样与前面的前序/中序遍历一致，只是需要改成后序遍历。
来看代码示例：
int TreeNodeNums(struct TreeNode* root)
{if (!root) return 0;return TreeNodeNums(root->left) +TreeNodeNums(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* retArr, int* retSize)
{if (!root) return;PreOrder(root->left, retArr, retSize);PreOrder(root->right, retArr, retSize);retArr[(*retSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{int size = TreeNodeNums(root);int* retArr = (int*)malloc(size * sizeof(int));*returnSize = 0;PreOrder(root, retArr, returnSize);return retArr;
}
2.7 另一棵树的子树
力扣 572.另一棵树的子树
这道题会有两棵树，一棵树可能是另一棵树的子树，我们需要进行判断。如何去判断呢？其实就是判断是否相同的问题，使用前面的判断两棵树是否相同的函数即可，直接遍历root这棵树的所有子树用相同树函数与subRoot进行匹配即可。
来看代码示例：
bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot)
{if (!root && !subRoot) return true;if (!root || !subRoot) return false;if (root->val != subRoot->val) return false;return isSameTree(root->left, subRoot->left) &&isSameTree(root->right, subRoot->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{// 判断是否root，subRoot其中之一为空，是则不匹配，返回falseif (!root && subRoot) return false;// 判断root与subRoot的值是否相等，若相等则进一步判断树root是否与树subroot相同if (root->val == subRoot->val){if (isSameTree(root, subRoot)) return true;}// 遍历root的左子树继续判断if (isSubtree(root->left, subRoot)) return true;// 遍历root的右子树继续判断if (isSubtree(root->right, subRoot)) return true;// 判断完，都不相同，返回falsereturn false;
}
题目中规定root与subRoot两树的结点个数都大于等于1，因此参数subRoot一定不为空，而树root由于需要递归遍历它的所有子树，所以形参root可能为空，需要先排除root结点存在空的情况，若为空，子树都不存在自然不需要匹配，直接返回false；若root不为空，则需要进一步判断root的值是否与subRoot的值相等，若相等则进一步判断树root是否与树subRoot相同，相同则说明subRoot是root的子树，返回true；若root的值与subRoot的值不相等，或者subRoot不是root的子树，则遍历root的下一棵子树。
还有力扣 110.平衡二叉树与力扣 226.翻转二叉树两道题可以推荐给大家练习一下巩固二叉树的知识，这里不做过多讲解，大家自行练习。AC代码示例如下。
// 平衡二叉树
// 求二叉树深度
int BTHeight(struct TreeNode* root)
{if (!root){return 0;}int Left = BTHeight(root->left);int right = BTHeight(root->right);return Left > right ? Left + 1 : right + 1;
}
bool isBalanced(struct TreeNode* root)
{if (!root) return true;// 求出当前结点左右子树的深度int leftHeight = BTHeight(root->left);int rightHeight = BTHeight(root->right);// 计算左、右子树深度之差的绝对值int sub = abs(leftHeight-rightHeight);// 如果深度差大于1说明不是平衡二叉树if (sub > 1) return false;// 深度差不超过1，则进入左、右子树继续判断return isBalanced(root->left) && isBalanced(root->right);
}
// 翻转二叉树
// 这里是用的队列来解决
typedef struct TreeNode* QDataType;
// 链式结构：表示队列
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;
// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->front = pq->rear = NULL;pq->size = 0;
}
// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (!newnode){perror("QueuePush::malloc fail!");return;}newnode->next = NULL;newnode->data = data;if (!pq->front){pq->front = pq->rear = newnode;}else{pq->rear->next = newnode;pq->rear = newnode;}pq->size++;
}
// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size > 0);if (!pq->front->next){//一个结点free(pq->front);pq->front = pq->rear = NULL;}else{//多个结点QNode* next = pq->front->next;free(pq->front);pq->front = next;}pq->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->front);return pq->front->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->rear);return pq->rear->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);while (pq->front){QNode* pop = pq->front;pq->front = pq->front->next;pq->size--;free(pop);}pq->front = pq->rear = NULL;
}
// 这里是题目所需完善的函数
struct TreeNode* invertTree(struct TreeNode* root)
{// 当前结点为空，无需翻转，直接返回空if (!root) return NULL;Queue q;// 创建队列QueueInit(&q);// 初始化队列QueuePush(&q, root);// 根结点入队while (!QueueEmpty(&q))// 队列为空结束循环{struct TreeNode* front = QueueFront(&q);// 取队头QueuePop(&q);// 删队头if (front->left) QueuePush(&q, front->left);// front的左孩子结点入队if (front->right) QueuePush(&q, front->right);// front的右孩子结点入队// 交换front的左右孩子结点struct TreeNode* tmp = front->left;front->left = front->right;front->right = tmp;}return root;// 翻转完成，返回当前根节点
}
三、树、二叉树、堆基础知识选择题
-
设某二叉树有如下特点：每个结点要么是叶子结点，要么有2棵子树。假如一棵这样的二叉树中有m（m>0）个叶子结点，那么该二叉树上的结点总数为（ ）。
A.2m+1 B.2(m-1) C.2m-1 D.2m解析：根据二叉树的性质，n0 = n2 + 1，即任意二叉树中，度为0的结点比度为2的结点多1。现在叶子结点——度为0的结点有m个，则度为2的结点为m-1个。题目说该二叉树中只有度为2和度为0的结点 ，因此总结点数就为2m-1各，故选择C。
-
如果一颗二叉树的前序遍历结果是ABCD，则满足条件的不同的二叉树有（ ）种。
A.13 B.14 C.15 D.16解析：首先这棵二叉树的高度一定在3~4层之间。
三层：
A(B(C，D),空(空，空))，A(空(空，空),B(C，D))，
A(B(C，空),D(空，空))，A(B(空，C)，D(空，空))，
A(B(空，空)，C(D，空))，A(B(空，空)，C(空，D))。
四层：
如果为四层，就是单边树，每一层只有一个节点，除根节点，其他节点都有左/右两种选择，所以有23种。
共计14种。 -
二叉树的( )遍历相当于广度优先遍历，( )遍历相当于深度优先遍历。
A.前序 中序 B.中序 前序 C.前序 层序 D.层序 前序解析：看上文。选D。
-
对任意一颗二叉树，设N0、N1、N2分别是度为0、1、2的结点数，则下列式子中一定正确的是（ ）。
A.N0 = N2 + 1 B.N1 = N0 + 1 C.N2 = N0 + 1 D.N2 = N1 + 1解析：看上文。选A。
-
根结点处深度为1，则拥有n个结点的二叉树的深度一定在（ ）区间内。
A.[log(n + 1)，n]
B.[logn，n]
C.[log(n + 1)，n - 1]
D.[log(n + 1)，n + 1]解析：
最大深度——树的每一层只经过一个结点，可以经过的最大结点个数；
最小深度——如果是完全二叉树，根据二叉树的性质，完全二叉树深度与结点的关系为：h = log(n+1) 向上取整。
当为单边树时，n为结点个数，也为层数，取得最大深度n；当为完全二叉树时取得最小深度，根据公式深度为h = log(n+1) 向上取整。故选择A。 -
在用树表示的目录结构中，从根目录到任何数据文件，有（ ）通道。
A.唯一一条 B.两条 C.三条 D.不一定解析：树的特点是不相交，所以不可能有多个路径同时到达一个点。故只有唯一一条。
-
一棵非空二叉树的前序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.至多只有一个结点解析：
前序遍历：根 左 右
后序遍历：左 右 根
从二叉树前序和后序遍历规则中可以看出，如果树中每个节点只有一个孩子时，遍历结果肯定是反的。取任意单边树1,2,3,4,5（非单边树也可以，左右孩子位置可以任意，每层确保只有一个结点即可）。前序序列为12345，后序序列为54321。当只有一个叶子结点时符合条件，故选C。 -
已知某二叉树的前序遍历序列为ABDEC，中序遍历序列为BDEAC，则该二叉树（ ）。
A.是满二叉树
B.是完全二叉树，不是满二叉树
C.不是完全二叉树
D.是所有的结点都没有右子树的二叉树解析：前序确定根，中序确定根的左右子树。根据A为前序序列第一个，确定为根结点，再看中序序列，BDE在A的左边，因此为左子树的结点，C在A的右边，因此为右子树的结点；根据B为前序序列第二个，确定为A的左孩子，再看中序序列，确定DE都为B的右孩子；根据D、E分别为前序序列的第三、四个，且E在D的右边，可以确定D是B的右孩子而E不是，E是D的右孩子。
最后还原二叉树为
即不是满二叉树，也不是完全二叉树，故选C。 -
已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）。A.
ABDGHJKCEFILMB.ABDGJHKCEILMFC.ABDHKGJCEILMFD.ABDGJHKCEIMLF解析：由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，根据中序遍历确定子树的左右区间。
以下分析建议跟着一个结点一个结点的画图理解（分析过程有点类似递归的感觉，先按深度优先，逐层往下，再回到上层，可以仔细体会）。- 后序：第十三个，即最后一个为A，根为A
- 中序：A的左子树JGDHKB；A的右子树ELIMCF
- 后序：第十二个C，A的右孩子为C
- 中序：C的左子树ELIM；C的右孩子F
- C的右子树排完回到C的左子树
- 后序：第十个E，E为C的左孩子
- 中序：E的左子树为空；E的右子树LIM
- 后序：第九个I，I为E的右孩子
- 中序：I的左孩子为L；I的右孩子为M
- A的右子树排完回到A的左子树
- 后序：第六个B，B为A的左孩子
- 中序：B的左子树JGDHK；B的右子树为空
- 后序：第五个D，D为B的左孩子
- 中序：D的左子树JG；D的右子树HK
- 后序：第四个H，H为D的右孩子
- 中序：H的左子树为空；H的右孩子为K
- D的右子树排完回到D的左子树
- 后序：第二个G，G为D的左孩子
- 中序：G的左孩子为J；G的右子树为空
最终为
前序遍历序列：A B D G J H K C E I L M F，故选B。
-
已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（ ）。
A.4257691 B.4275691 C.4761295 D.4729561解析：通过前序遍历找到子树的根，在中序遍历中找到根的位置，然后确定根左右子树的区间，即根的左侧为左子树中所有节点，根的右侧为右子树中所有节点。结果为
则后序序列为：4 7 6 1 2 9 5，故选C。 -
下列关于二叉树的叙述错误的是（ ）。
A.二叉树指的是深度为 2 的树
B.一个 n 个结点的二叉树将拥有 n-1 条边
C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点（根结点深度为1）
D.二叉树有二叉链和三叉链两种表示方式解析：
A错误: 二叉树指孩子最大个数为2，即树的度为二的树。深度描述的是树具有的层数。
B正确: 对于任意的树都满足，边的条数比节点个数少1，因为每个结点都有双亲结点，只有根结点没有。
C正确: 正确，详见上一篇的二叉树部分。
D正确: 二叉链一般指孩子表示法，三叉链一般指孩子双亲表示法，这两种方式是二叉树最常见的表示方式，虽然还有孩子兄弟表示法等，但该种表示方式本质也是二叉链。
故选A。 -
一颗拥有1000个结点的树的度为4，则它的最小深度是（ ）。
A.5 B.6 C.7 D.8解析：如果这棵树每一层都是满的，则它的深度最小，因此可以假设它为一棵四叉树，各结点的度最大值刚好为4，令高度为h，则这棵树的结点个数为(4h - 1) / 3，当h = 5时最大结点数为341，当h = 6时最大节点数为1365，所以最小深度应该为6。故选B。
-
在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个。
A.4 B.5 C.6 D.7解析：假设该树总共有n个节点，则n = n0 + n1 + n2 + n3。
有n个节点的树，总边数为n-1条。
1度即1个孩子结点，也就是一条边，所以总边数与度之间的关系为：
n - 1 = 0 x n0 + 1 x n1 + 2 x n2 + 3 x n3。
联立两个方程可以得到n0 = n2 + 2n3 + 1。
由n2 = 1，n3 = 2，得叶子结点即n0 = 6。故选C。 -
下列关于堆的叙述错误的是（ ）。
A.堆是一种完全二叉树
B.堆通常使用顺序表存储
C.小堆指的是左右孩子结点都比根结点小的堆
D.堆的删除是将尾部结点放到队顶后执行向下调整算法解析：
A正确：堆是在完全二叉树的基础上进行了条件的限制，即：每个节点都比其孩子结点大，则为大堆；每个节点都比其孩子节点小则为小堆。
B正确：完全二叉树比较适合使用顺序结构存储。
C错误：详见A。
D正确：堆删除，删的是堆顶元素，常见的操作是将堆顶元素与堆中最后一个元素交换，然后堆中元素个数减少一个，重新将堆顶元素往下调整。
故选C。 -
下列关键字序列中，序列（ ）是堆。
A.{16，72，31，23，94，53}
B.{94，23，31，72，16，53}
C.{16，53，23，94，31，72}
D.{16，23，53，31，94，72}解析：根据堆的定义去推即可。选D。
-
下列关于向下调整算法的说法正确的是（ ）。
A.构建堆的时候要对每个结点都执行一次
B.删除操作时要执行一次
C.插入操作时要执行一次
D.以上说法都不正确解析：
A错误：建堆时，从非叶子节点开始，倒着向上一直到根节点，只有非叶子结点都要执行一次向下调整算法。
B正确：删除元素时，首先交换堆顶元素与堆中最后一个元素，堆中有效元素个数减1，即删除了堆中最后一个元素，最后将堆顶元素向下调整，一次即可。
C错误：插入操作执行的是向上调整算法。
故选B。 -
在一个堆中，根节点从0开始编号，下标为i（i > 0）的结点的左右孩子结点及父结点的下标分别是（ ）。
A.2i、2i+1、i/2
B.2i、2i+1、(i-1)/2
C.2i+1、2i+2、(i-1)/2
D.2i+1、2i+2、i/2-1解析：堆中任意非根结点的结点，下标为i，其双亲为(i-1)/2，左孩子为2i+1，右孩子为2i+2。故选C。
-
将一个顺序表/数组利用向下调整的方式整理成堆的时间复杂度为（ ）。
A.O(nlogn)
B.O(logn)
C.O(1)
D.O(n)解析：题目说了是利用向下调整的方式建堆，即从最后一个非叶子结点开始，倒推向上一直到根结点，每一个非叶子结点都进行一次向下调整算法。我们需要估算出各个结点向下调整的交换次数并求和。
证明方法如下（注意时间复杂度按最坏情况看，且复杂度大致估算出数量级即可）：- 具有n个元素的完全二叉树，树高h = ㏒n。
- 最下层非叶子结点的元素（即第h-1层），只需向下一层，而这一层具有2(h-2)个结点，这一层所需时间为2(h-2) x 1。
- 由于是bottom-top建立堆，因此在调整上层元素的时候，下层已经调整好，所以并不需要同下层所有元素做比较，只需要同其中之一分支作比较并交换，交换次数则是树的高度减去当前节点的高度。因此，第k层的交换次数为2k-1 x (h - k)。
- 以上公式其实就是高中学过的数列的通项公式，可由此得出求和公式，因此构造树高为h的堆时间复杂度为：
S = 2(h-2) x 1 + 2(h-3) x 2 + …… + 20 x (h-1) ① - 通过观察公式①可知，该求和公式为等差数列和等比数列的乘积，因此用错位相减法求解，给公式左右两侧同时乘以2，可得：
2S = 2(h-1) x 1 + 2(h-2) x 2 + …… + 21 x (h-1) ②
用②减去①可得： S = 2(h-1) + 2(h-2) + 2(h-3) + …… + 21 - h + 1 ③
将③化简可得：S = 2h - h - 1 ④
公式④为总交换次数与树高h的关系式，需要的是总交换次数与树中结点个数的关系式，将h = ㏒n 带入④，得出如下结论：
S = n - ㏒n - 1。则向下调整建堆的时间复杂度为O(n)。
树的介绍告一段落。本篇主要实现了二叉树的链式结构，包括二叉树的创建与销毁，二叉树的前序、中序、后序、层序遍历，求二叉树的结点个数，求二叉树深度，在二叉树中查找值等。接着分享了单值二叉树，相同树，对称树，另一棵树的子树等OJ题作为练习。最后列出了一系列选择题作为树相关基础知识的总结与巩固。