前+中 中+后创建二叉树
2018-03-22 本文已影响0人
laochonger
By：https://blog.csdn.net/lsmrsun/article/details/52149962
<1>已知二叉树的前序序列和中序序列，求解树。
1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点
边和右边都为空，则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。
<2>、已知二叉树的后序序列和中序序列，求解树。
1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。
2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点
边和右边都为空，则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。
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]; //取得后序遍历顺序中最后一个结点
17. int index = 0;//在中序序列中进行查找根结点，并用index记录其在序列中的索引
18. while(mid[index]!=ch)//在中序中找到的所有结点的左边为该结点的左子树，右边为右子树
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]; //找到先序中的第一个结点
36. int index =0;
37. while(mid[index]!=ch)//在中序中找到的所有结点的左边为该结点的左子树，右边为右子树
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. }
