数据结构 二叉树

一、⼆叉树的定义

⼆叉树是⼀种特殊的树型结构，它的特点是每个结点⾄多只有2棵⼦树（即⼆叉树中不存在度⼤于2的结点），并且⼆叉树的⼦树有左右之分，其次序不能任意颠倒。
⼆叉的意思是这种树的每⼀个结点最多只有两个孩⼦结点。注意这⾥是最多有两个孩⼦，也可能没有孩⼦或者是只有⼀个孩⼦。
注意：⼆叉树结点的两个孩⼦，⼀个被称为左孩⼦，⼀个被称为右孩⼦。其顺序是固定的，就像⼈的左⼿和右⼿，不能颠倒混淆。

满⼆叉树
⼀棵⼆叉树的所有⾮叶⼦节点都存在左右孩⼦并且所有叶⼦节点都在同⼀层上，那么这棵树就称为满⼆叉树。

完全⼆叉树
对⼀棵树有n 个结点的⼆叉树按层序编号，所有的结点的编号从1 ∼ n。如果这棵树所有结点和同
样深度的满⼆叉树的编号为从1 ∼ n 的结点位置相同，则这棵⼆叉树为完全⼆叉树。说⽩了，就是在满⼆叉树的基础上，在最后⼀层的叶⼦结点上，从右往左依次删除若⼲个结点，剩下的就是⼀棵完全⼆叉树。

二、⼆叉树的存储

在《树》的章节中，已经学过树的存储，⼆叉树也是树，也是可以⽤vector数组或者链式前向星来存储。仅需在存储的过程中标记谁是左孩⼦，谁是右孩⼦即可。
• ⽐如⽤vector数组存储时，可以先尾插左孩⼦，再尾插右孩⼦；
• ⽤链式前向星存储时，可以先头插左孩⼦，再头插右孩⼦。只不过这样存储下来，遍历孩⼦的时候先遇到的是右孩⼦，这点需要注意。
但是，由于⼆叉树结构的特殊性，我们除了⽤上述两种⽅式来存储，还可以⽤符合⼆叉树结构特性的⽅式：分别是顺序存储和链式存储。

主要讲一下链式存储

因此我们可以创建两个数组l[N]，r[N] ，其中l[i] 表⽰结点号为 的结点的左孩⼦编号， r[i] 表⽰结点号为 的结点的右孩⼦编号。这样就可以把⼆叉树存储起来。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int l[N], r[N];
int main()
{cin >> n;for(int i = 1; i <= n; i++){// 存下 i 号结点的左右孩⼦ cin >> l[i] >> r[i];}return 0;
}

三、⼆叉树的遍历

深度优先遍历

不同于常规树的深度优先遍历，⼆叉树因其独特的性质可以划分成三种深度优先遍历：先序遍历，中
序遍历，和后序遍历。其中，三种遍历⽅式的不同在于处理根节点的时机。
对于⼀棵⼆叉树⽽⾔，整体可以划分成三部分：根节点+左⼦树+右⼦树：
• 先序遍历的顺序为：根+左+右；
• 中序遍历的顺序为：左+根+右；
• 后序遍历的顺序为：左+右+根。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int l[N], r[N];
void dfs1(int p)
{if(p == 0) return;// 先处理根节点 cout << p << " ";// 左⼦树 dfs1(l[p]);// 右⼦树 dfs1(r[p]);
}
void dfs2(int p)
{if(p == 0) return;dfs2(l[p]);cout << p << " ";dfs2(r[p]);
}
void dfs3(int p)
{if(p == 0) return;dfs3(l[p]);dfs3(r[p]);cout << p << " ";
}
int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> l[i] >> r[i];}dfs1(1); // 先序遍历 cout << endl;dfs2(1); // 中序遍历 cout << endl;dfs3(1); // 后序遍历 cout << endl;return 0;
}

宽度优先遍历

#include <iostream>
#include <queue>
using namespace std;
const int N = 300;
int n;
int l[N], r[N];
void bfs()
{queue<int> q;q.push(1);while(q.size()){auto p = q.front(); q.pop();cout << p << " ";// 左右孩⼦⼊队 if(l[p]) q.push(l[p]);if(r[p]) q.push(r[p]);}cout << endl;
}
int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> l[i] >> r[i];}bfs();return 0;
}