Algorithm - Problem - 二叉树之中序后序求先序

给出一棵二叉树的中序与后序遍历,求出它的先序遍历,用不同的大写字母表示二叉树的结点.

分析

XX 为一个结点,LL 为其左孩,RR 为其右孩,IN(X)\mathrm{IN}(X)XX 结点的中序遍历,POST(X)\mathrm{POST}(X)XX 结点的后序遍历。
则中序遍历 IN(X)=IN(L)XIN(R)\mathrm{IN}(X) = \mathrm{IN}(L)X\mathrm{IN}(R)
且后序遍历 POST(X)=POST(L)POST(R)X\mathrm{POST}(X) = \mathrm{POST}(L)\mathrm{POST}(R)X.
考虑到所有待处理的字符串都应为这一形式,自然而然地使用递归.

观察后序遍历 POST(X)\mathrm{POST}(X),我们发现最后一个字符为 XX,因此对于待处理的字符串,可以在中序遍历中查找后序遍历的最后一个字符,将中序遍历 IN(X)\mathrm{IN}(X) 自然而然地分为两部分,且显然有 IN(L)\mathrm{IN}(L)POST(L)\mathrm{POST}(L) 长度相等,IN(R)\mathrm{IN}(R)POST(R)\mathrm{POST}(R) 长度相等,可分离出左孩子和右孩子各自的中序遍历和后序遍历,递归调用即可.

代码

使用方法 pre(instr, poststr, 0, n - 1, 0, n - 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
void pre(char* in, char* post, int lp, int rp, int li, int ri)
{
// Root
if(lp > rp || li > ri) return;
char root = post[rp];
std::cout << root;
if(lp == rp || li == ri) return;
int m = -1;
for(int i = li; i <= ri; i++)
{
if(in[i] == root)
{
m = i;
break;
}
}
if(m != -1)
{
// Left
if(m > li) pre(in, post, lp, lp + (m - li - 1), li, m - 1);
// Right
if(m < ri) pre(in, post, rp - (ri - m), rp - 1, m + 1, ri);
}
}