By：https://blog.csdn.net/lsmrsun/article/details/52149962
<1>已知二叉樹的前序序列和中序序列，求解樹。
1、確定樹的根節(jié)點(diǎn)。樹根是當(dāng)前樹中所有元素在前序遍歷中最先出現(xiàn)的元素。
2、求解樹的子樹。找出根節(jié)點(diǎn)在中序遍歷中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節(jié)點(diǎn)左邊或右邊為空，則該方向子樹為空；若根節(jié)點(diǎn)
邊和右邊都為空，則根節(jié)點(diǎn)已經(jīng)為葉子節(jié)點(diǎn)。
3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重復(fù)1、2、3步，直到所有的節(jié)點(diǎn)完成定位。
<2>、已知二叉樹的后序序列和中序序列，求解樹。
1、確定樹的根。樹根是當(dāng)前樹中所有元素在后序遍歷中最后出現(xiàn)的元素。
2、求解樹的子樹。找出根節(jié)點(diǎn)在中序遍歷中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節(jié)點(diǎn)左邊或右邊為空，則該方向子樹為空；若根節(jié)點(diǎn)
邊和右邊都為空，則根節(jié)點(diǎn)已經(jīng)為葉子節(jié)點(diǎn)。
3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重復(fù)1、2、3步，直到所有的節(jié)點(diǎn)完成定位。
image
1. #include<bits/stdc++.h>
2. using namespace std;
3. typedef struct node
4. {
5. char data;
6. struct node *lchild,*rchild;
7. }BiTNode,*BiTree;
9. void pro_mid_createBiTree(BiTree &T,char *last,char *mid,int len)//后序中序還原建立二叉樹
10. {
11. if(len==0)
12. {
13. T=NULL;
14. return ;
15. }
16. char ch = last[len-1]; //取得后序遍歷順序中最后一個結(jié)點(diǎn)
17. int index = 0;//在中序序列中進(jìn)行查找根結(jié)點(diǎn)，并用index記錄其在序列中的索引
18. while(mid[index]!=ch)//在中序中找到的所有結(jié)點(diǎn)的左邊為該結(jié)點(diǎn)的左子樹，右邊為右子樹
19. {
20. index++;
21. }
22. T=(BiTNode *)malloc(sizeof(BiTNode ));
23. T->data = ch;
24. pro_mid_createBiTree(T->lchild,last,mid,index);//建立左子樹
25. pro_mid_createBiTree(T->rchild,last+index,mid+index+1,len-index-1);//建立右子樹
26. }
28. void pre_mid_createBiTree(BiTree &T,char *prim,char *mid,int len) //前序中序還原建立二叉樹
29. {
30. if(len==0)
31. {
32. T=NULL;
33. return ;
34. }
35. char ch = prim[0]; //找到先序中的第一個結(jié)點(diǎn)
36. int index =0;
37. while(mid[index]!=ch)//在中序中找到的所有結(jié)點(diǎn)的左邊為該結(jié)點(diǎn)的左子樹，右邊為右子樹
38. {
39. index++;
40. }
41. T=(BiTNode *)malloc(sizeof(BiTNode ));
42. T->data = ch;
43. pre_mid_createBiTree(T->lchild,prim+1,mid,index);//建立左子樹
44. pre_mid_createBiTree(T->rchild,prim+index+1,mid+index+1,len-index-1);//建立右子樹
45. }
46. void pre_order(BiTree T)//前序遞歸遍歷二叉樹
47. {
48. if(T)
49. {
50. cout<<T->data;
51. pre_order(T->lchild);
52. pre_order(T->rchild);
53. }
54. }
56. void pro_order(BiTree T)//后序遞歸遍歷二叉樹
57. {
58. if(T)
59. {
60. pro_order(T->lchild);
61. pro_order(T->rchild);
62. cout<<T->data;
63. }
64. }
65. int main()
66. {
67. BiTree T;
68. int n;
69. char prim[100],mid[100],last[100];
70. while(cin>>n)
71. {
72. cout<<"前序中序建立二叉樹后序輸出:"<<endl;
73. for(int i =0 ;i<n;i++)
74. {
75. cin>>prim[i];
76. }
77. for(int i =0 ;i<n;i++)
78. {
79. cin>>mid[i];
80. }
81. pre_mid_createBiTree(T,prim,mid,n);
82. pro_order(T);
83. cout<<endl;
85. cout<<"后序中序建立二叉樹前序輸出:"<<endl;
86. for(int i =0 ;i<n;i++)
87. {
88. cin>>last[i];
89. }
90. for(int i =0 ;i<n;i++)
91. {
92. cin>>mid[i];
93. }
94. pro_mid_createBiTree(T,last,mid,n);
95. pre_order(T);
96. cout<<endl;
97. }
98. return 0;
99. }
