算法：
1 如果输入序列长度小于等于0，结束
2 输入的前序序列的第一个节点是后序遍历的最后一个节点，将这个节点保存到output变量中
3 把输入的两个序列拆成4部分，output节点的左子树的前序和中序序列，output节点右子树的前序和中序序列
4 用3中的结果先左后右递归调用该算法
5 输出output
代码如下
1 void LastTree::ShowLast(const char *po, const char *mo, int n)
2 {
3 //递归结束条件
4 if(n <= 0)
5 {
6 return;
7 }
8
9 //输出值
10 char output = *po;
11
12 //output节点的左子树中序序列
13 int i = 0;
14 char *lmct = (char*)malloc(n*sizeof(char));
15 memset(lmct, 0, n);
16 while(*(mo + i) != output)
17 *(lmct + i) = *(mo + i++);
18 int lnum = i;
19 i++;
20
21 //output节点的右子树中序序列
22 int j = 0;
23 char *rmct = (char*)malloc(n*sizeof(char));
24 memset(rmct, 0, n);
25 while(*(mo + i) != NULL)
26 {
27 *(rmct + j++) = *(mo + i++);
28 }
29
30 //output节点的左子树前序序列
31 char *lpct = (char*)malloc(n*sizeof(char));
32 memset(lpct, 0, n);
33 int k = 0;
34
35 for(int a = 0; *(po + a); a++)
36 {
37 for(int b = 0; *(lmct + b); b++)
38 {
39 if(*(po + a) == *(lmct + b))
40 {
41 *(lpct + k++) = *(po + a);
42 break;
43 }
44
45 }
46 }
47
48 //output节点的右子树前序序列
49 char *rpct = (char*)malloc(n*sizeof(char));
50 memset(rpct, 0, n);
51 k = 0;
52
53 for(int a = 0; *(po + a); a++)
54 {
55 for(int b = 0; *(rmct + b); b++)
56 {
57 if(*(po + a) == *(rmct + b))
58 {
59 *(rpct + k++) = *(po + a);
60 break;
61 }
62
63 }
64 }
65
66 //先左后右递归
67 ShowLast(lpct, lmct, lnum);
68 ShowLast(rpct, rmct, n - lnum - 1);
69
70 //输出当前节点
71 std::cout<<output;
72
73 free(lmct);
74 free(rmct);
75 free(lpct);
76 free(rpct);
77 lpct = NULL;
78 rpct = NULL;
79 lmct = NULL;
80 rmct = NULL;
81 return;
82 }
测试用例：
1 void main()
2 {
3 LastTree lt;
4 const char *po = "ABCDEFG";
5 const char *mo = "CBDAEGF";
6
7 lt.ShowLast(po, mo, 7);
8
9 _getch();
10 }
|
输出结果为：CDBGFEA