已知前序中序求後序

​

網上看到的一篇關于前序中序求後續的文章，利用遞歸的方法，内容很不錯，值得收藏。

題目描述：

輸入某二叉樹的前序周遊和中序周遊的結果，

請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。

例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并輸出它的後序周遊序列。

思路

根據前序周遊的數組，arr[0]為根節點，在中序周遊中找到值等于arr[0]的位置index，則index的左邊為此節點的左子樹，右邊為此節點的右子樹。于是遞歸建構該節點的左右子樹。

測試用例：

8

1, 2, 4, 7, 3, 5, 6, 8

4, 7, 2, 1, 5, 3, 8, 6

----------------------------------------

5

1, 2, 3, 4, 5

5, 4, 3, 2, 1

----------------------------------------

5

1, 2, 3, 4, 5

1, 2, 3, 4, 5

----------------------------------------

1

1

1

----------------------------------------

7

1, 2, 4, 5, 3, 6, 7

4, 2, 5, 1, 6, 3, 7

----------------------------------------

7

1, 2, 4, 5, 3, 6, 7

4, 2, 8, 1, 6, 3, 7

//問題描述：已知一個二叉樹的前序周遊和中序周遊，求改二叉樹的後序周遊，

//二叉樹中沒有相同的元素，資料為整型。

//例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，

//則重建二叉樹并輸出它的後序周遊序列。

//思路

//根據前序周遊的數組，arr[0]為根節點，在中序周遊中找到值等于arr[0]的位置index，

//則index的左邊為此節點的左子樹，右邊為此節點的右子樹。于是遞歸建構該節點的左右子樹。

/*

輸入：

輸入可能包含多個測試樣例，對于每個測試案例，

輸入的第一行為一個整數n(1<=n<=1000)：代表二叉樹的節點個數。

輸入的第二行包括n個整數(其中每個元素a的範圍為(1<=a<=1000))：代表二叉樹的前序周遊序列。

輸入的第三行包括n個整數(其中每個元素a的範圍為(1<=a<=1000))：代表二叉樹的中序周遊序列。

輸出：

對應每個測試案例，輸出一行：

如果題目中所給的前序和中序周遊序列能構成一棵二叉樹，則輸出n個整數，代表二叉樹的後序周遊序列，每個元素後面都有空格。

如果題目中所給的前序和中序周遊序列不能構成一棵二叉樹，則輸出”No”。

樣例輸入輸出：

8

1 2 4 7 3 5 6 8

4 7 2 1 5 3 8 6

7 4 2 5 8 6 3 1

8

1 2 4 7 3 5 6 8

4 1 2 7 5 3 8 6

No

*/

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define true 1
 4 #define false 0
 5 typedef int bool1;
 6 
 7 typedef struct BiTreeNode
 8 {
 9 int data;
10 struct BiTreeNode *lchild;
11 struct BiTreeNode *rchild;
12 }BiTreeNode,*BiTree;
13 
14 bool1 CanConstruct;
15 
16 void RebuildTree(BiTree *root,int len,int *PreTraverse,int *InTraverse)
17 {
18 if (PreTraverse == NULL || InTraverse == NULL)
19 {
20 CanConstruct = false;
21 return;
22 }
23 if (len < 1)
24 return;
25 //在中序周遊中找到前序周遊的頭結點的左右子結點
26 int index = -1;
27 for (int i = 0; i < len; i++)
28 {
29 if (PreTraverse[0] == InTraverse[i])
30 {
31 index = i;
32 break;
33 }
34 }
35 if(index==-1)//這種情況就是沒有找到目前根結點在中序周遊的位置。是以不能重構
36 {
37 CanConstruct = false;
38 return;
39 }
40 //找到了之後就開始建構此結點
41 //為目前結點配置設定空間
42 *root = (BiTree)malloc(sizeof(BiTreeNode));
43 (*root)->data = PreTraverse[0];
44 (*root)->lchild = NULL;
45 (*root)->rchild = NULL;
46 //接下來開始建構該結點的左右子樹。
47 RebuildTree(&(*root)->lchild, index, PreTraverse + 1, InTraverse);
48 RebuildTree(&(*root)->rchild, len - index - 1, PreTraverse + index + 1, InTraverse + index + 1);
49 }
50 
51 
52 void PostOrderTree(BiTree root)
53 {
54 if (!root)
55 return;
56 PostOrderTree(root->lchild);
57 PostOrderTree(root->rchild);
58 printf("%d ", root->data);
59 }
60 
61 
62 int main(void)
63 {
64 int n;
65 while (scanf("%d", &n) && n > 0)
66 {
67 int *PreTraverse = (int *)malloc(sizeof(int)*n);
68 if (!PreTraverse)
69 exit(EXIT_FAILURE);
70 int *InTraverse = (int *)malloc(sizeof(int)*n);
71 if (!InTraverse)
72 exit(EXIT_FAILURE);
73 for (int i = 0; i < n; i++)
74 {
75 
76 cin >>PreTraverse[i];
77 }
78 for (int i = 0; i < n; i++)
79 {
80 
81 cin >> InTraverse[i];
82 }
83 BiTree root;
84 CanConstruct = true;
85 RebuildTree(&root, n, PreTraverse, InTraverse);
86 if (CanConstruct)
87 {
88 PostOrderTree(root);
89 printf("\n");
90 }
91 else
92 {
93 printf("No\n");
94 }
95 }
96 return 0;
97 }