二叉树的存储、遍历及应用
1 存储
1.1 顺序存储
设二叉树深度为h，那么我们就按照深度为h的满二叉树的结点个数（2^h-1）创建对应元素个数的数组，然后按照自上而下，从左到右的顺序，依次将树中结点存入数组即可。
例如下图所示：
待存储的二叉树
我们需要存储一个深度为4的二叉树，所以先在脑海里构建如下相同深度的满二叉树，并且编号（对应数组下标，我这里从1开始，看官请自便）。
深度为4的满二叉树
由于待存储二叉树的最后一个结点 h 对应满二叉树编号为 12 的结点，并且编号（即数组下标）是从1开始的，因此，我们创建一个长度为(12+1)的数组node[13]，具体如下：
| Index | Value |
|---|---|
| 0 | 0 |
| 1 | a |
| 2 | b |
| 3 | c |
| 4 | d |
| 5 | e |
| 6 | f |
| 7 | 0 |
| 8 | 0 |
| 9 | g |
| 10 | 0 |
| 11 | 0 |
| 12 | h |
至此，我们就完成了树的顺序存储，代码实现简单不做赘述。
我们同时也能发现，长度为13的数组还有5个元素只是打了个酱油，这就是顺序存储的特点，也是缺点：它只适合存储满二叉树或者完全二叉树，否则就会存在空间浪费。
那么，我们来看看下面的重点内容。
1.2 链式存储
其实，很简单，就是创建链表存储二叉树各结点，直接上个结构体定义帮助理解，如下：
// 二叉树结点结构体定义
struct node {
char data; //结点值
node *left; //指向左子树的结点指针
node *right; //指向右子树的结点指针
};
紧接着，我们如何创建链表存储上述的二叉树呢，给大家个葫芦，自己照着画葫芦好吧。
// 链式存储二叉树
node root; // 创建根结点
root.data = a;
root.left = new node; // 创建左结点
memset(root.left, 0, sizeof(node)); // 初始化内存
root.left->data = b;
root.right = new node; // 创建右结点
memset(root.right, 0, sizeof(node));
root.right->data = c;
完全是翻译操作，毫无技术可言，难点在于真正面临问题给出数据时该怎么快捷实现二叉树存储。
2 遍历
2.1 先序、中序和后序
对于先序、中序和后序三种遍历来说，它们实际遍历路径完全相同，先、中、后只是在强调何时访问结点而已。
举个栗子～还是它吧！
在这里插入图片描述
三种遍历路径实际都是酱紫的，自己跟着编号走一遍：
graph TD
a((a))--1-->b((b))
b((b))--2-->d((d))
d((d))--3-->dl((NULL))
dl((NULL))--4-->d((d))
d((d))--5-->g((g))
g((g))--6-->gl((NULL))
gl((NULL))--7-->g((g))
g((g))--8-->gr((NULL))
gr((NULL))--9-->g((g))
g((g))--10-->d((d))
d((d))--11-->b((b))
b((b))--12-->e((e))
e((e))--13-->el((NULL))
el((NULL))--14-->e((e))
e((e))--15-->er((NULL))
er((NULL))--16-->e((e))
e((e))--17-->b((b))
b((b))--18-->a((a))
a((a))--19-->c((c))
c((c))--20-->f((f))
f((f))--21-->h((h))
h((h))--22-->hl((NULL))
hl((NULL))--23-->h((h))
h((h))--24-->hr((NULL))
hr((NULL))--25-->h((h))
h((h))--26-->f((f))
f((f))--27-->fr((NULL))
fr((NULL))--28-->f((f))
f((f))--29-->c((c))
c((c))--30-->cr((NULL))
cr((NULL))--31-->c((c))
c((c))--32-->a((a))
这就相当清楚明了了，我们可以看到每个存在的结点都会遍历三次，是吧？掰手指头数数指向或被指向箭头的个数就知道啦！
不会有人站出来喷我不对吧？
老师坏坏，老师骗人，根结点只有两次！
根结点谁去访问的，别忘了，你和根结点之间还串根遍历路径呢！
综上所述，可得：
- 先序：第一次遍历到就访问。
该二叉树对应先序序列为：abdgecfh - 中序：第二次遍历到再访问。
该二叉树对应中序序列为：dgbeahfc - 后序：第三次遍历到才访问。
该二叉树对应后序序列为：gdebhfca
2.2 层序
层序：自上而下，从左到右遍历并访问二叉树各结点。
该二叉树对应层序序列为：abcdefgh
3 应用
好了，最后搞个例题爽一把～
现给出若干个各不相同的整数用以构建二叉树，规则如下：
1、以第一个数为根结点；
2、后续整数依序与根结点数值比较后决定其位置：
（1）若大于根结点值，则将该数往根结点的右子结点移动，若此右子结点为空，则将该数存入，否则就重复比较直到找到合适的空结点；
（2）若小于或等于根结点值，则将该数往根结点的左子结点移动，若此左子结点为空，则将该数存入，否则就重复比较直到找到合适的空结点。
分别以层序、先序、中序、后序输出所有整数。
输入：仅一行，若干个不相同的整数，以空格隔开。
输出：共四行，分别以层序、先序、中序和后序输出，各整数以空格隔开。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct tree {
int num;
struct tree * l;
struct tree * r;
};
// 后序遍历
void back_sort(tree * node) {
if (!node)
{
return ;
}
back_sort(node->l);
back_sort(node->r);
cout << node->num << ' '; // 左右子树遍历后，此次为第三次到达该结点，则输出
}
// 中序遍历
void mid_sort(tree * node) {
if (!node)
{
return ;
}
mid_sort(node->l);
cout << node->num << ' '; // 左子树遍历后，此次为第二次到达该结点，则输出
mid_sort(node->r);
}
// 先序遍历
void front_sort(tree * node) {
if (!node)
{
return ;
}
cout << node->num << ' '; // 第一次到达该结点，输出
front_sort(node->l);
front_sort(node->r);
}
// 层序遍历
void level_sort(tree * root) {
queue<tree *> q; // 队列使用
if (!root)
{
return ;
}
// 从根结点开始，层序方式入队存储结点，则出队也必然是层序
// 队列特性：先入先出（FIFO）
q.push(root);
while (!q.empty())
{
tree * tmp = q.front();
cout << tmp->num << ' ';
if (tmp->l)
{
q.push(tmp->l);
}
if (tmp->r)
{
q.push(tmp->r);
}
q.pop();
}
}
// 构建二叉树
tree * push_tree(tree * node, int num) {
if (node)
{
if (num <= node->num)
{
// 新存入结点权值小于等于当前结点权值，则向左子树存储
node->l = push_tree(node->l, num);
} else
{
// 新存入结点权值大于当前结点权值，则向右子树存储
node->r = push_tree(node->r, num);
}
} else
{
node = new tree;
// 不使用memset那就辛苦点，一个个初始化结构体各数据成员
memset(node, 0, sizeof(tree));
//node->num = 0;
//node->l = NULL;
//node->r = NULL;
node->num = num;
}
return node;
}
int main() {
int value, count;
// 使用容器可以按需存储结点，比上来定义一个长度超大的数组要有逼格些
vector<int> a;
tree * root = NULL;
cin >> value;
a.push_back(value);
while(cin.get() != '\n')
{
cin >> value;
a.push_back(value);
}
// 每次从根结点开始创建，旨在进行权值判断，从而明确二叉树中各结点位置
count = a.size();
for (int i = 0; i < count; i++)
{
root = push_tree(root, a[i]);
}
level_sort(root); // 层序
cout << endl;
front_sort(root); // 先序
cout << endl;
mid_sort(root); // 中序
cout << endl;
back_sort(root); // 后序
cout << endl;
return 0;
}
为了我可爱而勇猛的学生们，码一下午字也值了～
奥利给～妙啊～
