二叉树遍历
二叉树的遍历方式
对于一棵二叉树，可以将其分成根节点、左子树、右子树三部分。根据对这三部分的访问顺序，可以将遍历的方式分成前序遍历（或者先序遍历），中序遍历，后序遍历以及层序遍历。
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
层序遍历：根节点（深度为0）->深度为1的所以节点（从左到右）->…
容易看出前面三种方式就是以根节点在访问顺序中的位置命名的。其中在遍历左右两个序列时，也要按照相同的顺序递归遍历，这样对于一棵确定的二叉树，按照同一个遍历方法可以得到一个唯一确定的序列。
但是需要注意的是，对于给出的一个某种遍历下得到的序列，可能有许多二叉树与之对应，可以举出显然的例子。
表达式树
对于一个所有运算符都是二元运算符的表达式，可以构造这样一颗树：
将某个运算符的两个操作数作为它的子节点，然后按照优先级将所有运算符构成的子树结合在一起，形成一棵表达式树，这样如果将某两个操作数按照它们父节点的运算符计算后的结果取代父节点，一层层计算上去就可以得到最终的结果。
对于这样的表达式树，相应的前、中、后序遍历得到就就是前、中、后缀表达式。其中中缀表达式也就是日常所使用的表达式，可能含有括号。
抑制表达式树，求对应表达式是容易的。已知中缀表达式，可以找到最后计算的运算符递归构造。这里由于确定了运算符作为子树的根节点，加上运算符的优先级和结合性，所以可以由表达式唯一确定表达式树。
由遍历求二叉树
前面提到给出一个某种遍历下的序列不能确定一个二叉树，但是给出一棵树的（前+中）或者（后加中）遍历，就可以唯一确定这棵树。这是因为：
- 已知前/后序遍历序列，可以确定二叉树的根节点
- 已知中序遍历和根节点，可以确定左右子树的中序遍历序列
- 在前/后序遍历中，左右子树的序列相邻且独立，因此可以根据上一步得到的长度分离得到左右子树的前/后序遍历
- 对左右子树递归进行上述过程，直到只有一个节点为止
这样就根据给出的遍历确定了一棵二叉树。
上代码：（以后序和中序遍历为例）
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<stdio.h>
#include<stdlib.h>
#define maxn 33
#define L -1
#define R 1
int n;
int last[maxn],mid[maxn];//存放后序和中序遍历
int id[maxn];//存放层序遍历的树（节点下标乘二是左耳子），id[i]是在后序遍历中的位置
void input()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;++i)
scanf("%d",&last[i]);
for(i=1;i<=n;++i)
scanf("%d",&mid[i]);
}
void maketree(int ll,int rl,int lm,int rm,int fa,int which)
{//ll和rl是后序遍历的区间，lm/rm同理，fa是以后序遍历的位置表示的父节点，which表示是哪个儿子
if(ll>rl||lm>rm)return;
//printf("%d\n",last[rl]);
if(ll==rl)
{
id[ll]=id[fa]*2;
if(which==R)
++id[ll];
return;
}
int root=rl;
id[root]=id[fa]*2;
if(which==R)
++id[root];
int i;
for(i=lm;i<=rm&&mid[i]!=last[root];++i);
int lenl=i-1-lm+1,lenr=rm-i;
maketree(ll,ll+lenl-1,lm,i-1,root,L);
maketree(ll+lenl,rl-1,i+1,rm,root,R);
}
void print()
{//这里直接暴力n^2输出了，可以有更好的方法
int i,j,cnt=0;
for(i=1;cnt!=n;++i)
{
for(j=1;j<=n;++j)
{
if(id[j]==i)
{
++cnt;
printf("%d",last[j]);
if(cnt!=n)putchar(' ');
}
}
}
}
int main()
{
input();
maketree(1,n,1,n,0,R);
print();
return 0;
}
|
