二叉树详解
一、二叉树的概念
1.二叉树的定义
二叉树是一种特殊的树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树是有序树，其子树有左右之分，次序不能任意颠倒。二
叉的意思是这种树的每一个结点最多只有两个孩子结点。注意这里是最多有两个孩子， 也可能没有孩子或者是只有一个孩子。
注意：二叉树结点的两个孩子，一个被称为左孩子， 一个被称为右孩子。其顺序是固定的，就像我们的左手和右手， 不能颠倒混淆。
2.
特殊的二叉树
（1）满二叉树
一棵二叉树的所有非叶子节点都存在左右孩子并且所有叶子节点都在同一层上，那么这棵树就称为满二叉树。
（2）完全二叉树
对一棵树有n个结点的二叉树按层序编号，所有的结点的编号从1~n 。如果这棵树所有结点和同样深度的满二叉树的编号为从1~n的结点位置相同，则这棵二叉树为完全二叉树。说白了，就是在满二叉树的基础上，在最后一层的叶子结点上，从右往左依次删除若干个结点，所有的叶子结点都在最左边，剩下的就是一棵完全二叉树。
除了上述两种二叉树，还有堆、二叉排序树、平衡二叉树、红黑树等在这儿暂时不讨论。
二、二
叉树的存储
有关树的存储，在之前的博客中已经说明过了。二叉树也是树，也是可以用vector数组或者链式前向星来存储。仅需在存储的过程中标记谁是左孩子，谁是右孩子即可。比
如用 vector 数组存储时，可以先尾插左孩子，再尾插右孩子；用链式前向星存储时，可以先头插左孩子，再头插右孩子。只不过这样存储下来，遍历孩子的时候先遇到的是右孩子，这点需要注意。但是，由于二叉树结构的特殊性，我们除了用上述两种方式来存储，还可以用符合二叉树结构特性的方式：分别是顺序存储和链式存储。
1.
顺序存储
顺序结构存储就是使用数组来存储。
在完全二叉树以及满二叉树的性质那里，我们了解到：如果从根节点出发，按照层序遍历的顺序，由1开始编号，那么父子之间的编号是可以计算出来的。那么在存储完全二叉树的时候，就按照编号，依次放在数组对应下标的位置上，然后通过计算找到左右孩子和父亲。
结点下标为
i
：
（1）
如果父存在，父下标为
i
/2
；
（2）如果左孩子存在，左孩子下标为
i
× 2
；
（3）如果右孩子存在，右孩子下标为
i
× 2 + 1
。
当然，如果不是完全二叉树，也是可以用顺序存储。但是首先要先把这棵二叉树补成完全二叉树，然后再去编号。不然就无法通过计算找到左右孩子和父亲的编号。我们还可以发现当该二叉树不为满二叉树时，创建的数组是有空间浪费的。尤其在一些极端的情况更是如此。
所以顺序存储结构一般只用于完全二叉树或满二叉
树。
在这儿先不过多讨论用这种方法来存储。
2.链式存储
链式存储类比链表的存储，都有静态实现和动态实现的方式。
我们这里依旧只讲静态实现，也就是用数组模拟。算法竞赛中给定的树结构一般都是有编号的，参考之前所说给的树结构。因此我们可以创建两个数组 l[N]
，r[N] ，其中
l[i]
表示结点号为i的结点的左孩子编号，
r[i]
表示结点号为i的结点的右孩子编号。这样就可以把二叉树存储起来了。接下来我们就借着一个题干来完成二叉树的链式存储吧。
题目描述：
有一个
n
(
n ≤ 10 ^ 6)
个结点的二叉树。给出每个结点的两个子结点编号（均不超过
n
），建立一棵
二叉树（根节点的编号为 1），如果是叶子结点，则输入 0 0。
输入描述：
第一行一个整数
n
，表示结点数。
之后 n行，第 i行两个整数 l、r ，分别表示结点 i的左右子结点编号。若 l=0则表示无左子结点， r=0同理。
#include <iostream>
using namespace std;
const int N=1e6+10;
int l[N],r[N];
int n;
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> l[i] >> r[i];
}
return 0;
}3.二叉树的遍历
（1）
深度优先遍历
不同于常规树的深度优先遍历，二叉树因其独特的性质可以划分成三种深度优先遍历：先序遍历，中序遍历，和后序遍历。其中，三种遍历方式的不同在于处理根节点的时机。对于一棵二叉树而言，整体可以划分成三部分：根节点 + 左子树 + 右子树：
先序遍历的顺序为：根 + 左 + 右；
中序遍历的顺序为：左 + 根 + 右；
后序遍历的顺序为：左 + 右 + 根。
#include <iostream>
using namespace std;
const int N=1e6+10;
int l[N],r[N];
int n;
//先序遍历
void dfs1(int u)
{
if(u==0)return;
cout << u << " ";
dfs1(l[u]);
dfs1(r[u]);
}
//中序遍历
void dfs2(int u)
{
if(u==0)return;
dfs2(l[u]);
cout << u << " ";
dfs2(r[u]);
}
//后序遍历
void dfs3(int u)
{
if(u==0)return;
dfs3(l[u]);
dfs3(r[u]);
cout << u << " ";
}
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;
}（2）宽度优先遍历
这个就和常规的树的遍历方式一样，直接用队列帮助层序遍历即可。
#include <iostream>
#include <queue>
using namespace std;
const int N=1e6+10;
int l[N],r[N];
int n;
queue<int> q;
//先序遍历
void dfs1(int u)
{
if(u==0)return;
cout << u << " ";
dfs1(l[u]);
dfs1(r[u]);
}
//中序遍历
void dfs2(int u)
{
if(u==0)return;
dfs2(l[u]);
cout << u << " ";
dfs2(r[u]);
}
//后序遍历
void dfs3(int u)
{
if(u==0)return;
dfs3(l[u]);
dfs3(r[u]);
cout << u << " ";
}
//宽度优先遍历
void bfs()
{
q.push(1);
while(q.size())
{
int u=q.front();
cout << u << " ";
q.pop();
if(!l[u])q.push(l[u]);
if(!r[u])q.push(r[u]);
}
}
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;
bfs();cout << endl;
return 0;
}四、相关的算法题
1.
#include <iostream>
using namespace std;
const int N=300;
char l[N],r[N];
int n;
char root;
void dfs(char root)
{
if(root=='*')return;
cout << root;
dfs(l[root]);
dfs(r[root]);
}
int main()
{
cin >> n >> root;
cin >> l[root] >> r[root];
for(int i=2;i<=n;i++)
{
char t;cin >> t;
cin >> l[t] >> r[t];
}
dfs(root);
return 0;
}
因为这题中的结点是字符，所以我们可以直接用
ASCII
码值当做下标来使用。比如
'a'
直接映射成97 ，l[97]里面就存着 'a'
的左儿子，r[97]里面就存着
'a'
的右儿子，以此类推，建立二叉树。在创建二叉树示和之前的演示有些许区别，因为在这里头结点是不确定的，所以我们需要单独将其标记出来。
2.
#include <iostream>
using namespace std;
const int N=1e6+10;
int l[N],r[N];
int n;
int dfs(int u)
{
if(u==0)return 0;
return max(dfs(l[u]),dfs(r[u]))+1;
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> l[i] >> r[i];
}
cout << dfs(1) << endl;
return 0;
}
本题求的是二叉树的高度。二叉树的高度 = 1 + max(左子树的高度， 右子树的高度)；因此，我们可以使用递归思想来解决，递归终点为叶子结点后并不存在的“后继节点”，这时返回0。
3.
#include <iostream>
#include <string>
using namespace std;
string a,b;
void dfs(int l1,int r1,int l2,int r2)
{
if(l1>r1)return;// 当区间不合法时，返回
cout << b[r2];//找到根结点并输出
int p=l1;
while(a[p]!=b[r2])p++;//找到中序排列的根结点
dfs(l1, p - 1, l2, l2 + p - l1 - 1); // 递归处理左子树
dfs(p + 1, r1, l2 + p - l1, r2 - 1); // 递归处理右子树
}
int main()
{
cin >> a >> b;
dfs(0,a.size()-1,0,b.size()-1);
return 0;
}其实就是通过后序排列先找到头结点，再找到中序排列中头结点的位置，就能将中序排列分为左子树和右子树，在通过区间的长度得出每个区间的范围下标就可以了。当然这种题肯定不止一种，但我们需要确保有中序排列，因为有了它我们才可以通过头结点来分区。
4.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=110;
vector<int> t[N];
int n,u,v;
queue<int> q;
int fa[N],dist[N];
int Dist;
int dfs(int x)
{
//方法一
if(!t[x].size())return 1;
if(t[x].size()==1)return dfs(t[x][0])+1;
return max(dfs(t[x][0]),dfs(t[x][1]))+1;
//方法二
int ret=0;
for(auto i:t[x])
{
ret=max(ret,dfs(i));
}
return ret+1;
}
int bfs()
{
int ret=0;
q.push(1);
while(q.size())
{
int sz=q.size();
ret=max(ret,sz);
while(sz--)
{
int m=q.front();
q.pop();
for(auto i:t[m])
{
q.push(i);
}
}
}
return ret;
}
int main()
{
cin >> n;
for(int i=1;i<n;i++)
{
cin >> u >> v;
t[u].push_back(v);
fa[v]=u;
}
cout << dfs(1) << endl;
cout << bfs() << endl;
int a,b;
cin >> a >> b;
while(a!=1)
{
// dist[fa[a]]=dist[a]+1;
// a=fa[a];
Dist++;a=fa[a];
dist[a]=Dist;
}
Dist=0;
while(!dist[b]&&b!=1)
{
b=fa[b];
Dist++;
}
cout << dist[b]*2+Dist << endl;
return 0;
}本题由三部分组成。第一部分是求二叉树的深度，和之前的思路是一样的，就是拆解为子树的深度再加1。方法一就是将所有情况分成三种进行操作，分别是有两个孩子，有一个孩子或者是没有孩子，进行递归。方法二就是设置一个变量ret，通过max找出子树中的最大深度再加上1，进行递归。第二部分的思路和宽度优先遍历差不多，通过队列来实现，通过q.size()得出每一行的宽度，这个宽度还有一个作用，就是进行n次操作从而使当前行的元素全部取出，并使下一行的元素进入队列。这样循环往复，我们就能使ret和size进行取大，找出最大的宽度。第三部分就是通过向上不断找父结点，再之前记录每个结点的父结点，再用一个数组来记录到这个结点的距离。我们再从第二个点开始找，第一个重叠的位置，就是两者的最近公共祖先。