数据结构 —— 链式二叉树（C语言讲解）
目录
0.前言
1.链式存储的二叉树
2.二叉树的遍历
二叉树的前、中、后序遍历
前序遍历
中序遍历
后序遍历
二叉树的层序遍历
3.二叉树的其他操作
二叉树的结点个数
二叉树叶子结点个数
二叉树第k层结点个数
二叉树查找值为x的节点
二叉树的高度
判断二叉树是否是完全二叉树
0.前言
本篇文章主要讲解链式存储的二叉树，如果读者不清楚二叉树的基础知识，推荐阅读数据结构——树和二叉树简介。
对于二叉树这种数据结构的学习，重点不是增删改查，而是学习这种结构，所以，主要讲解一些链式二叉树的操作。
1.链式存储的二叉树
二叉树链式存储指的是用链表来存储二叉树。具体的做法是链表中每个结点由3个域组成，数据域和左右指针域，左右指针域分别用来存储左孩子的地址和右孩子的地址。
二叉树结点表示：
二叉树链式存储结构示意图：
2.二叉树的遍历
由于二叉树的结构比较复杂，遍历二叉树的时候不能像遍历数组、单链表那样直观的表达；二叉树的遍历是按照某种规则依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。
- 二叉树的遍历是二叉树最重要的操作之一，是在二叉树上进行其他操作的基础。
- 二叉树递归结构的遍历有前序遍历、中序遍历、后续遍历。
- 二叉树非递归结构的遍历有层序遍历。
二叉树的前、中、后序遍历
前序遍历
前序遍历的顺序为：根结点->左子树->右子树，对于每棵子树同样遵循该遍历顺序。
前序遍历递归代码：
void PrevOrder(BTNode* root) {
if (root == NULL) { // 访问空结点的时候返回
printf("NULL ");
return;
}
printf("%d ", root->val); // 访问根结点
PrevOrder(root->left); // 遍历左子树
PrevOrder(root->right); // 遍历右子树
}
前序遍历递归图解：
上图中数据走前序遍历结果为：1,2,3,4,5,6.
中序遍历
中序遍历的顺序为：左子树->根结点->右子树，对于每棵子树同样遵循该遍历顺序。
中序遍历递归代码：
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL "); // 访问空结点的时候返回
return;
}
InOrder(root->left); // 遍历左子树
printf("%d ", root->val); // 访问根结点
InOrder(root->right); // 遍历右子树
}后序遍历
后序遍历的顺序为：左子树->根结点->右子树，对于每棵子树同样遵循该遍历顺序。
后续遍历递归代码：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL "); // 访问空结点的时候返回
return;
}
PostOrder(root->left); // 遍历左子树
PostOrder(root->right); // 遍历右子树
printf("%d ", root->val); // 访问根结点
}二叉树的层序遍历
二叉树除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
- 层序遍历需要借助队列来完成。
- 层序遍历的思想是上一层把下一层带入队列。
层序遍历代码：
void LevelOrder(BTNode* root)
{
Que q; // Que是一个自定义的队列类型
QueueInit(&q);
if (root)
QueuePush(&q, root); // 先往队列中放入一个结点
while (!QueueEmpty(&q)) // 只要队列不为空就进入循环
{
BTNode* front = QueueFront(&q); // 取队头元素，并访问
printf("%d ", front->val);
if (front->left) // 当前节点左孩子不为空，将左孩子入队列
QueuePush(&q, front->left);
if (front->right) // 当前节点右孩子不为空，将右孩子入队列
QueuePush(&q, front->right);
QueuePop(&q); // 从队列中删除访问过的元素
}
printf("\n");
QueueDestroy(&q);
}
3.二叉树的其他操作
二叉树的结点个数
要求二叉树的结点个数，可以根据二叉树的递归结构来求：二叉树的结点个数 = 左子树的节点个数+右子树的结点个数+1。左子树和右子树同样需要满足上述规则。
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);
}二叉树第k层结点个数
二叉树第k层的结点个数 = 左子树第k-1层的结点个数+右子树第k-1层的结点个数。左子树和右子树同样需要满足上述规则。
int TreeKLevel(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
{
return 1;
}
return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}二叉树查找值为x的节点
查找一个值为x的结点，我们采用前序遍历，先访问根，再遍历左子树和右子树。
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;
if (root->val == x) //访问当前结点
return root;
BTNode* ret = NULL;
ret = TreeFind(root->left, x); // 去左子树中找
if (ret)
return ret;
ret = TreeFind(root->right, x);// 去右子树中找
if (ret)
return ret;
return NULL;
}二叉树的高度
二叉树的高度 = 左右子树高度大的那个 + 1。左右子树同时满足该规则。
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = TreeHeight(root->left); // 求出左子树的高度
int rightHeight = TreeHeight(root->right); // 求出右子树的高度
// 二叉树的高度 = 左右子树高度大的那个 + 1
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
判断二叉树是否是完全二叉树
判断二叉树是否是完全二叉树，主要借助层序遍历的思想 ——上一层带下一层，以及完全二叉树的特点 —— 所有结点之间不会出现空。
当第一个循环结束之后，判断队列中是否还有非空结点，如果有，这棵二叉树就不是完全二叉树；如果没有，这棵二叉树就是完全二叉树。
// 判断二叉树是否是完全二叉树
int TreeComplete(BTNode* root)
{
Que q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
QueuePop(&q);
}
// 已经遇到空节点，如果队列中后面的节点还有非空，就不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}