访问 $k$ 的左儿子就是 k*2 或 k<<1，访问右儿子就是 k*2+1 或 k<<1|1。
但是有时这种存储空间复杂度为 $O(2^n)$，浪费空间，根节点不一定为一，而且要存储其他东西。因此我们还有另外一种存储方法。

3-2. 链式存储

定义一个结构体，里面有 $l$（左儿子编号）、$r$（右儿子编号）、$d$（所存储的值，有时会用到）。

struct node{
	int l,r,d;
}tree[N];
1
2
3

和上面的例子一样，如果输入顺序正确，存下来后是这样：

空间复杂度降到了 $O(n)$。
在解决简单二叉树一类的题目时，通常使用链式存储。

4. 二叉树的遍历

4-1. 先/前序(根)遍历

遍历顺序为根→左子树→右子树。
示例代码（输出二叉树的先序遍历）：

void pre(int p)//p 为当前节点编号
{
	if(p==-1) return;
	cout<<p<<' ';
	pre(tree[p].l);
	pre(tree[p].r);
}
1
2
3
4
5
6
7

输出为：1 2 4 3 5 7 8 6。

4-2. 中序(根)遍历

遍历顺序为左子树→根→右子树。
示例代码（输出二叉树的中序遍历）：

void in(int p)//p 为当前节点编号
{
	if(p==-1) return;
	pre(tree[p].l);
	cout<<p<<' ';
	pre(tree[p].r);
}
1
2
3
4
5
6
7

输出为：4 2 1 7 5 8 3 6。

4-3. 后序(根)遍历

遍历顺序为左子树→右子树→根。
示例代码（输出二叉树的后序遍历）：

void post(int p)//p 为当前节点编号
{
	if(p==-1) return;
	pre(tree[p].l);
	pre(tree[p].r);
	cout<<p<<' ';
}
1
2
3
4
5
6
7

输出为：4 2 7 8 5 6 3 1。

4-4. 层次遍历

和 bfs 一样。
示例代码（输出二叉树的层次遍历）：

queue<int>q;
void bfs()
{
	q.push(root);//root 为根节点编号
	while(!q.empty())
	{
		int x=q.front();
		cout<<x<<' ';
		q.pop();
		if(tree[x].l!=-1) q.push(tree[x].l);
		if(tree[x].r!=-1) q.push(tree[x].r);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5. 例题详解

5-1. 洛谷 P4913 【深基16.例3】二叉树深度

求其深度，我们可以使用 dfs 或 bfs 的方法。
对于 dfs，我们多加一个参数 $dep$，其表示当前节点的深度。

#include
using namespace std;

struct node{
	int l,r;
}tree[1000005];
int n,ans;

void dfs(int p,int dep)//dep 表示编号为 p 的节点的深度
{
	if(!p) return;
	ans=max(ans,dep);//不断地存答案
	dfs(tree[p].l,dep+1);
	dfs(tree[p].r,dep+1);
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>tree[i].l>>tree[i].r;
	}
	dfs(1,1);
	cout<<ans;
 	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

对于 bfs，我们在队列里多加一个数，表示当前节点的深度。

#include
using namespace std;

struct node{
	int l,r;
}tree[1000005];
queue<pair<int,int>>q;//pair 的第一项为编号，第二项为深度
int n,ans;

void bfs()
{
	q.push({1,1});
	while(!q.empty())
	{
		int x=q.front().first;
		ans=max(ans,q.front().second);//记答案
		q.pop();
		if(tree[x].l) q.push(tree[x].l);
		if(tree[x].r) q.push(tree[x].r);
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>tree[i].l>>tree[i].r;
	}
	bfs(1,1);
	cout<<ans;
 	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

5-2. 洛谷 P4913 加强版

这一次，我们不知道根节点是谁，需要你自己去求根节点。
那我们要如何求呢？
我们可以利用树的性质：一棵树有且仅有一个根节点。
也就是说，输入中左右儿子中没有提到的编号，就是根节点。

bool f[1919810];//f[i] 表示是否不是根节点
for(int i=1;i<=n;i++)
{
	cin>>tree[i].l>>tree[i].r;
	f[tree[i].l]=f[tree[i].r]=1;//标记
}
int root;
for(int i=1;i<=n;i++)
{
	if(!f[i])
	{
		root=i;//存下根节点
		break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5-3. 洛谷 P1030 [NOIP2001 普及组] 求先序排列

我们知道，中序遍历顺序为左子树→根→右子树，后序遍历顺序为左子树→右子树→根。这意味着，我们可以通过后序遍历找到根，通过根由中序遍历分割左右子树，然后递归下去。
以样例 BADC BDCA 为例。

• 由后序得知根节点为 A，输出。
• 在中序中找到 A，分割出左右子树。
  • 递归左子树（中序 B，后序 B），由后序得知根节点为 B，输出。
  • 在中序中找到 B，分割出左右子树。
    • 递归左子树，字符串为空，回溯。
    • 递归右子树，字符串为空，回溯。
  • 递归右子树（中序 DC，后序 DC），由后序得知根节点为 C，输出。
  • 在中序中找到 C，分割出左右子树。
    • 递归左子树（中序 D，后序 D），由后序得知根节点为 D，输出。
    • 在中序中找到 D，分割出左右子树。
      • 递归左子树，字符串为空，回溯。
      • 递归右子树，字符串为空，回溯。
    • 递归右子树，字符串为空，回溯。

代码实现：

#include
using namespace std;

void f(string a,string b)//a 为中序，b 为后序
{
	if(a=="") return;
	cout<<b[b.size()-1];//根节点
	int t=a.find(b[b.size()-1]);//中序中找根节点
	f(a.substr(0,t),b.substr(0,t));
	f(a.substr(t+1),b.substr(t,a.size()-t-1));
}

int main()
{
	string a,b;
	cin>>a>>b;
	f(a,b);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6. 练习

加*的表示选做。

• 根据先序、中序遍历求后序遍历。
• 思考：根据先序、后序遍历能否求出中序遍历？
• *根据先序、中序遍历求层次遍历。
• *洛谷 P5018 [NOIP2018 普及组] 对称二叉树。
• *洛谷 P1040 [NOIP2003 提高组] 加分二叉树。