大家好，我是weipyh，好久不见，上期我们讲了栈和队列，这期接下来讲树以及二叉树的相关内容。
之前学习的顺序表和链表，数据之间大多是一前一后的关系，而树结构中的数据具有层次关系。
1.为什么要学习树
在现实生活中，有很多数据并不是简单的一条线。
比如电脑中的文件夹，一个文件夹里面可以有多个文件，也可以有多个子文件夹，子文件夹下面还可以继续保存其他内容。
这种一层一层的关系，就比较适合使用树来表示。
树是一种非线性的数据结构，它由若干个结点组成，结点之间通过边连接起来。
树中有一个特殊的结点，称为根结点。根结点没有父结点，其他结点都通过父子关系连接起来。
例如：
A
/ \\
B C
/ \\
D E
在上面的树中：
- A是根结点
- B、C是A的子结点
- A是B、C的父结点
- D、E是叶子结点
- B、C互相称为兄弟结点
一个结点拥有的子结点数量，称为这个结点的度。
如果一个结点没有子结点，那么它的度就是0，这种结点叫做叶子结点。
2.二叉树是什么
二叉树是树结构中比较常见的一种结构。
二叉树中的每个结点最多只能有两个子结点，这两个子结点分别称为左孩子和右孩子。
需要注意的是，二叉树的左右是有区别的。
下面两棵树虽然结点数量相同，但是它们并不是同一棵二叉树：
1 1
/ \\ / \\
2 3 3 2
左边结点2在左边，结点3在右边；右边结点3在左边，结点2在右边。
所以二叉树的左右子树不能随意交换。
联系与思考
二叉树和链表有一个很明显的联系。
链表中的一个结点通常包含：
数据 + 一个指针
这个指针指向下一个结点。
而二叉树中的一个结点通常包含：
数据 + 左指针 + 右指针
左指针用来指向左子树，右指针用来指向右子树。
可以把二叉树看成是链表结构的一种扩展，只不过一个结点最多可以连接两个后继结点。
3.满二叉树和完全二叉树
3.1 满二叉树
如果一棵二叉树的每一层结点都达到最大数量，那么这棵树就是满二叉树。
例如：
1
/ \\
2 3
/ \\ / \\
4 5 6 7
如果根结点所在层数为第1层，树的高度为 h，那么满二叉树的结点总数为：
2^h – 1
3.2完全二叉树
完全二叉树的前面每一层都是满的，最后一层的结点从左到右连续排列。
例如：
1
/ \\
2 3
/ \\ /
4 5 6
这是一棵完全二叉树。
但是下面这种情况就不是完全二叉树：
1
/ \\
2 3
\\ /
5 6
因为最后一层出现了空缺，结点没有按照从左到右的顺序排列。
联系与思考
满二叉树和完全二叉树经常一起出现，但是两者并不相同。
可以把满二叉树理解为“每个位置都放满了”。
完全二叉树则允许最后一层不满，但是数据必须从左往右排列。
完全二叉树比较适合使用数组存储，因为结点之间的位置关系比较规整。
4.二叉树的链式结构
普通二叉树使用数组存储时，可能会浪费很多空间，所以一般使用链式结构。
typedef int BTDataType;
// 定义二叉树结点结构
typedef struct BTNode
{
BTDataType data; // 当前结点中存储的数据
struct BTNode* left; // 指向当前结点的左孩子
struct BTNode* right; // 指向当前结点的右孩子
}BTNode;
4.1 创建结点
BTNode* CreateNode(BTDataType x)
{
// 为新结点申请一块内存空间
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
// 判断内存是否申请成功
// 如果申请失败，输出错误信息并结束程序
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
// 将数据保存到新结点的数据域中
newnode->data = x;
// 新结点刚创建时没有左孩子
// 所以将左指针初始化为空指针
newnode->left = NULL;
// 新结点刚创建时没有右孩子
// 所以将右指针初始化为空指针
newnode->right = NULL;
// 返回创建好的结点
return newnode;
}
4.2 手动连接一棵二叉树
BTNode* MakeTree()
{
// 创建二叉树中的各个结点
BTNode* n1 = CreateNode(1);
BTNode* n2 = CreateNode(2);
BTNode* n3 = CreateNode(3);
BTNode* n4 = CreateNode(4);
BTNode* n5 = CreateNode(5);
BTNode* n6 = CreateNode(6);
// 将n2连接到n1的左边
n1->left = n2;
// 将n3连接到n1的右边
n1->right = n3;
// 将n4和n5连接到n2的左右两边
n2->left = n4;
n2->right = n5;
// 将n6连接到n3的左边
n3->left = n6;
// 返回整棵树的根结点
return n1;
}
创建完成后的结构如下：
1
/ \\
2 3
/ \\ /
4 5 6
这里的 n1 是根结点，只要保存根结点，就可以通过指针访问整棵二叉树。
联系与思考
链式二叉树中，空指针并不代表程序出错。
例如结点4没有左右孩子，那么：
n4->left == NULL
n4->right == NULL
这两个空指针表示结点4下面没有子树。
在链表中，最后一个结点的 next 指针为空，表示链表结束。
在二叉树中，一个结点的 left 或 right 指针为空，表示对应方向没有子树。
5.二叉树的遍历
二叉树的遍历，就是按照某种顺序访问树中的每一个结点。
常见的遍历方式有：
前三种遍历都是递归遍历。
5.1 前序遍历
前序遍历的顺序是：
根结点、左子树、右子树
void PreOrder(BTNode* root)
{
// 判断当前结点是否为空
// 如果为空，说明当前子树已经遍历结束
if (root == NULL)
{
return;
}
// 前序遍历首先访问根结点
printf("%d ", root->data);
// 再递归遍历左子树
PreOrder(root->left);
// 最后递归遍历右子树
PreOrder(root->right);
}
对于上面的二叉树，前序遍历结果为：
1 2 4 5 3 6
5.2 中序遍历
中序遍历的顺序是：
左子树、根结点、右子树
void InOrder(BTNode* root)
{
// 如果当前结点为空，说明当前子树没有数据
if (root == NULL)
{
return;
}
// 先递归遍历左子树
InOrder(root->left);
// 左子树遍历完成后访问根结点
printf("%d ", root->data);
// 最后递归遍历右子树
InOrder(root->right);
}
中序遍历结果为：
4 2 5 1 6 3
5.3 后序遍历
后序遍历的顺序是：
左子树、右子树、根结点
void PostOrder(BTNode* root)
{
// 判断当前结点是否为空
// 如果为空，说明当前子树已经遍历结束
if (root == NULL)
{
return;
}
// 先递归遍历左子树
PostOrder(root->left);
// 再递归遍历右子树
PostOrder(root->right);
// 左右子树都遍历完成后访问根结点
printf("%d ", root->data);
}
后序遍历结果为：
4 5 2 6 3 1
联系与思考
前序、中序和后序遍历的代码结构非常相似，主要区别只有一个：
printf("%d ", root->data);
这行代码放在哪里。
- 放在递归左子树之前，就是前序遍历。
- 放在递归左子树和右子树之间，就是中序遍历。
- 放在递归左右子树之后，就是后序遍历。
这说明三种遍历的核心区别并不是递归过程，而是访问根结点的时机不同。
5.4 遍历与递归的联系
二叉树的每一棵左子树和右子树，本身又是一棵二叉树。
所以我们可以使用同一个函数继续处理左子树和右子树。
这也是二叉树适合使用递归实现的原因。
递归函数的执行过程实际上会使用函数调用栈。
这和之前学习的栈有关系：
- 调用函数时，将函数信息压入栈中。
- 函数执行完成后，从栈顶退出。
- 递归结束后，程序按照栈的后进先出顺序返回。
6.统计二叉树的信息
6.1 计算结点个数
int CountNode(BTNode* root)
{
// 如果当前结点为空，说明当前子树没有结点
if (root == NULL)
{
return 0;
}
// 当前结点数量为1
// 再加上左子树和右子树的结点数量
return CountNode(root->left)
+ CountNode(root->right)
+ 1;
}
6.2 计算叶子结点个数
int CountLeaf(BTNode* root)
{
// 空树没有叶子结点
if (root == NULL)
{
return 0;
}
// 当前结点没有左右孩子
// 说明当前结点就是叶子结点
if (root->left == NULL && root->right == NULL)
{
return 1;
}
// 当前结点不是叶子结点
// 继续统计左右子树中的叶子结点
return CountLeaf(root->left)
+ CountLeaf(root->right);
}
6.3 计算二叉树高度
int TreeHeight(BTNode* root)
{
// 空树的高度为0
if (root == NULL)
{
return 0;
}
// 计算左子树的高度
int leftHeight = TreeHeight(root->left);
// 计算右子树的高度
int rightHeight = TreeHeight(root->right);
// 当前树的高度等于左右子树较大值加1
return leftHeight > rightHeight
? leftHeight + 1
: rightHeight + 1;
}
联系与思考
结点个数、叶子结点个数和树的高度，虽然作用不同，但是它们的代码结构很相似。
它们都可以拆分成三个部分：
当前结点
左子树
右子树
这就是树结构递归定义带来的好处。
我们不用一次性处理整棵复杂的树，只需要先解决当前结点，再分别处理左右子树。
7.层序遍历
前面的三种遍历都是从根结点开始递归访问。
层序遍历使用的是另一种思路：
先访问第一层，再访问第二层，最后访问第三层
同一层的结点按照从左到右的顺序访问。
层序遍历需要使用队列，因为队列具有先进先出的特点。
这里可以直接使用上一篇文章中实现的队列。
void LevelOrder(BTNode* root)
{
// 如果二叉树为空，不需要进行层序遍历
if (root == NULL)
{
return;
}
// 创建一个队列，用来保存还没有访问的结点
Queue q;
// 初始化队列
QueueInit(&q);
// 先将根结点放入队列
QueuePush(&q, root);
// 队列不为空时继续访问
while (!QueueEmpty(&q))
{
// 获取队头结点
BTNode* front = QueueFront(&q);
// 访问队头结点的数据
printf("%d ", front->data);
// 当前结点访问完成后，将它从队列中删除
QueuePop(&q);
// 将当前结点的左孩子放入队列
// 左孩子会在后面被访问
if (front->left != NULL)
{
QueuePush(&q, front->left);
}
// 将当前结点的右孩子放入队列
// 右孩子会在左孩子之后被访问
if (front->right != NULL)
{
QueuePush(&q, front->right);
}
}
// 遍历完成后销毁队列
QueueDestroy(&q);
}
上面这棵树的层序遍历结果为：
1 2 3 4 5 6
联系与思考
递归遍历和层序遍历使用了两种不同的数据结构思想：
- 前序、中序、后序遍历依靠函数调用栈。
- 层序遍历依靠队列。
这也是栈和队列在树结构中的一个实际应用。
如果希望按照“从上到下、从左到右”的顺序访问，就使用队列。
如果希望深入一条路径，直到处理完成后再返回，就可以使用递归或者栈。
8. 一些问题与思考
这篇的内容就到这里了，欢迎大家讨论，感谢观看。
