- 浏览: 361635 次
- 性别:
- 来自: 成都
文章分类
最新评论
-
tuspark:
关于javadoc这里讲解的更全面:《javadoc设置》。
Eclipse中生成javadoc【Z】 -
yuexiang1007:
帮我解决了问题,谢谢!!!
java.math.BigInteger使用心得总结 -
netwelfare:
个人感觉,文章对HashMap的遍历分析的有点浅,不如这里的介 ...
HashMap遍历的两种方式【Z】 -
memoryisking:
关于java.math.BigInteger讲解在这里可以看到 ...
java.math.BigInteger使用心得总结 -
巴尾的兔兔帅:
divide应该是除吧?不是减。dividepublic Bi ...
java.math.BigInteger使用心得总结
二叉树遍历及C语言实现
已知中序和前序序列,或者已知中序和后序序列,都能够构造一棵二叉树。在本例中,本人用C语言写程序解答了下面两个算法题:
(1)给出一棵二叉树的中序与后序遍历序列,求出它的先序遍历序列。
(2)给出一棵二叉树的中序与先序遍历序列,求出它的后序遍历序列。
知识点扼要回顾:
所谓二叉树的遍历,是指按一定的顺序对二叉树中的每个结点均访问一次,且仅访问一。按照根结点访问位置的不同,通常把二叉树的遍历分为六种:
TLR(根左右), TRL(根右左), LTR(左根右)
RTL(右根左), LRT(左右根), RLT(右左根)
其中,TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树,这与人们先左后右的习惯不同,因此,往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。
前序遍历的规律是:输出根结点,输出左子树,输出右子树;
中序遍历的规律是:输出左子树,输出根结点,输出右子树;
后序遍历的规律是:输出左子树,输出右子树,输出根结点;
不多说了,看代码吧:)
1. #include <iostream>
2. #include <string>
3.
4. using namespace std;
5.
6. //存储节点数据,为简便起见,这里选用字符
7. typedef char DATA_TYPE;
8.
9. typedef struct tagBINARY_TREE_NODE BINARY_TREE_NODE, *LPBINARY_TREE_NODE;
10.
11. struct tagBINARY_TREE_NODE
12. {
13. DATA_TYPE data; //节点数据
14. LPBINARY_TREE_NODE pLeftChild; //左孩子指针
15. LPBINARY_TREE_NODE pRightChild; //右孩子指针
16. };
17.
18. //
19. //函数名称:TreeFromMidPost
20. //函数功能:给出一棵二叉树的中序与后序序列,构造这棵二叉树。
21. //输入参数:LPBINARY_TREE_NODE & lpNode:二叉树的结点
22. // string mid:存储了二叉树的中序序列的字符串
23. // string post:存储了二叉树的后序序列的字符串
24. // int lm, int rm:二叉树的中序序列在数组mid中的左右边界
25. // int lp, int rp:二叉树的后序序列在数组post中的左右边界
26. //
27. void TreeFromMidPost(LPBINARY_TREE_NODE & lpNode, string mid, string post, int lm, int rm, int lp, int rp)
28. {
29. //构造二叉树结点
30. lpNode = new BINARY_TREE_NODE;
31. lpNode->data = post[rp];
32. lpNode->pLeftChild = NULL;
33. lpNode->pRightChild = NULL;
34.
35. int pos = lm;
36.
37. while (mid[pos] != post[rp])
38. {
39. pos++;
40. }
41. int iLeftChildLen = pos - lm;
42.
43. if (pos > lm)//有左孩子,递归构造左子树
44. {
45. TreeFromMidPost(lpNode->pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1);
46. }
47.
48. if (pos < rm)//有右孩子,递归构造右子树
49. {
50. TreeFromMidPost(lpNode->pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1);
51. }
52. }
53.
54. //
55. //函数名称:TreeFromMidPre
56. //函数功能:给出一棵二叉树的先序与中序序列,构造这棵二叉树。
57. //输入参数: BINARY_TREE_NODE & lpNode:二叉树的结点
58. // string mid:存储了二叉树的中序序列的字符串
59. // string pre:存储了二叉树的先序序列的字符串
60. // int lm, int rm:二叉树的中序序列在数组mid中的左右边界
61. // int lp, int rp:二叉树的先序序列在数组pre中的左右边界
62. //
63. void TreeFromMidPre(LPBINARY_TREE_NODE & lpNode, string mid, string pre, int lm, int rm, int lp, int rp)
64. {
65. //构造二叉树结点
66. lpNode = new BINARY_TREE_NODE;
67. lpNode->data = pre[lp];
68. lpNode->pLeftChild = NULL;
69. lpNode->pRightChild = NULL;
70.
71. int pos = lm;
72.
73. while (mid[pos] != pre[lp])
74. {
75. pos++;
76. }
77. int iLeftChildLen = pos - lm;
78.
79. if (pos > lm)//有左孩子,递归构造左子树
80. {
81. TreeFromMidPre(lpNode->pLeftChild, mid, pre, lm, pos - 1, lp + 1, lp + iLeftChildLen);
82. }
83.
84. if (pos < rm)//有右孩子,递归构造右子树
85. {
86. TreeFromMidPre(lpNode->pRightChild, mid, pre, pos + 1, rm, lp + iLeftChildLen + 1, rp);
87. }
88. }
89.
90. //先序遍历
91. void PreOrder(LPBINARY_TREE_NODE p)
92. {
93. if(p != NULL)
94. {
95. cout << p->data; //输出该结点
96. PreOrder(p->pLeftChild); //遍历左子树
97. PreOrder(p->pRightChild); //遍历右子树
98. }
99. }
100.
101. //中序遍历
102. void MidOrder(LPBINARY_TREE_NODE p)
103. {
104. if(p != NULL)
105. {
106. MidOrder(p->pLeftChild); //遍历左子树
107. cout << p->data; //输出该结点
108. MidOrder(p->pRightChild); //遍历右子树
109. }
110. }
111.
112. //后序遍历
113. void PostOrder(LPBINARY_TREE_NODE p)
114. {
115. if(p != NULL)
116. {
117. PostOrder(p->pLeftChild); //遍历左子树
118. PostOrder(p->pRightChild); //遍历右子树
119. cout << p->data; //输出该结点
120. }
121. }
122.
123. //释放二叉树
124. void Release(LPBINARY_TREE_NODE lpNode)
125. {
126. if(lpNode != NULL)
127. {
128. Release(lpNode->pLeftChild);
129. Release(lpNode->pRightChild);
130. delete lpNode;
131. lpNode = NULL;
132. }
133. }
134.
135.
136. int main(int argc, char* argv[])
137. {
138. string pre; //存储先序序列
139. string mid; //存储中序序列
140. string post; //存储后序序列
141.
142. LPBINARY_TREE_NODE lpRoot; //二叉树根节点指针
143.
144.
145. cout<<"程序1已知二叉树的中序与后序序列,求先序序列"<<endl;
146. cout<<"请先输入中序序列,回车后输入后序序列:"<<endl;
147.
148. cin >> mid;
149. cin >> post;
150.
151. TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1);
152. cout<<"先序遍历结果:";
153. PreOrder(lpRoot);
154. cout<<endl;
155.
156. cout<<"中序遍历结果:";
157. MidOrder(lpRoot);
158. cout<<endl;
159.
160. cout<<"后序遍历结果:";
161. PostOrder(lpRoot);
162. cout<<endl;
163. Release(lpRoot);
164. cout<<endl;
165.
166. cout<<"程序2已知二叉树的中序与先序序列,求后序序列"<<endl;
167. cout<<"请先输入先序序列,回车后输入中序序列:"<<endl;
168. cin >> pre;
169. cin >> mid;
170.
171. TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1);
172. cout<<"先序遍历结果:";
173. PreOrder(lpRoot);
174. cout<<endl;
175.
176. cout<<"中序遍历结果:";
177. MidOrder(lpRoot);
178. cout<<endl;
179.
180. cout<<"后序遍历结果:";
181. PostOrder(lpRoot);
182. cout<<endl;
183. Release(lpRoot);
184. cout<<endl;
185.
186.
187. system("pause");
188. return 0;
189. }
#include <iostream> #include <string> using namespace std; //存储节点数据,为简便起见,这里选用字符 typedef char DATA_TYPE; typedef struct tagBINARY_TREE_NODE BINARY_TREE_NODE, *LPBINARY_TREE_NODE; struct tagBINARY_TREE_NODE { DATA_TYPE data; //节点数据 LPBINARY_TREE_NODE pLeftChild; //左孩子指针 LPBINARY_TREE_NODE pRightChild; //右孩子指针 }; // //函数名称:TreeFromMidPost //函数功能:给出一棵二叉树的中序与后序序列,构造这棵二叉树。 //输入参数:LPBINARY_TREE_NODE & lpNode:二叉树的结点 // string mid:存储了二叉树的中序序列的字符串 // string post:存储了二叉树的后序序列的字符串 // int lm, int rm:二叉树的中序序列在数组mid中的左右边界 // int lp, int rp:二叉树的后序序列在数组post中的左右边界 // void TreeFromMidPost(LPBINARY_TREE_NODE & lpNode, string mid, string post, int lm, int rm, int lp, int rp) { //构造二叉树结点 lpNode = new BINARY_TREE_NODE; lpNode->data = post[rp]; lpNode->pLeftChild = NULL; lpNode->pRightChild = NULL; int pos = lm; while (mid[pos] != post[rp]) { pos++; } int iLeftChildLen = pos - lm; if (pos > lm)//有左孩子,递归构造左子树 { TreeFromMidPost(lpNode->pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1); } if (pos < rm)//有右孩子,递归构造右子树 { TreeFromMidPost(lpNode->pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1); } } // //函数名称:TreeFromMidPre //函数功能:给出一棵二叉树的先序与中序序列,构造这棵二叉树。 //输入参数: BINARY_TREE_NODE & lpNode:二叉树的结点 // string mid:存储了二叉树的中序序列的字符串 // string pre:存储了二叉树的先序序列的字符串 // int lm, int rm:二叉树的中序序列在数组mid中的左右边界 // int lp, int rp:二叉树的先序序列在数组pre中的左右边界 // void TreeFromMidPre(LPBINARY_TREE_NODE & lpNode, string mid, string pre, int lm, int rm, int lp, int rp) { //构造二叉树结点 lpNode = new BINARY_TREE_NODE; lpNode->data = pre[lp]; lpNode->pLeftChild = NULL; lpNode->pRightChild = NULL; int pos = lm; while (mid[pos] != pre[lp]) { pos++; } int iLeftChildLen = pos - lm; if (pos > lm)//有左孩子,递归构造左子树 { TreeFromMidPre(lpNode->pLeftChild, mid, pre, lm, pos - 1, lp + 1, lp + iLeftChildLen); } if (pos < rm)//有右孩子,递归构造右子树 { TreeFromMidPre(lpNode->pRightChild, mid, pre, pos + 1, rm, lp + iLeftChildLen + 1, rp); } } //先序遍历 void PreOrder(LPBINARY_TREE_NODE p) { if(p != NULL) { cout << p->data; //输出该结点 PreOrder(p->pLeftChild); //遍历左子树 PreOrder(p->pRightChild); //遍历右子树 } } //中序遍历 void MidOrder(LPBINARY_TREE_NODE p) { if(p != NULL) { MidOrder(p->pLeftChild); //遍历左子树 cout << p->data; //输出该结点 MidOrder(p->pRightChild); //遍历右子树 } } //后序遍历 void PostOrder(LPBINARY_TREE_NODE p) { if(p != NULL) { PostOrder(p->pLeftChild); //遍历左子树 PostOrder(p->pRightChild); //遍历右子树 cout << p->data; //输出该结点 } } //释放二叉树 void Release(LPBINARY_TREE_NODE lpNode) { if(lpNode != NULL) { Release(lpNode->pLeftChild); Release(lpNode->pRightChild); delete lpNode; lpNode = NULL; } } int main(int argc, char* argv[]) { string pre; //存储先序序列 string mid; //存储中序序列 string post; //存储后序序列 LPBINARY_TREE_NODE lpRoot; //二叉树根节点指针 cout<<"程序1已知二叉树的中序与后序序列,求先序序列"<<endl; cout<<"请先输入中序序列,回车后输入后序序列:"<<endl; cin >> mid; cin >> post; TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1); cout<<"先序遍历结果:"; PreOrder(lpRoot); cout<<endl; cout<<"中序遍历结果:"; MidOrder(lpRoot); cout<<endl; cout<<"后序遍历结果:"; PostOrder(lpRoot); cout<<endl; Release(lpRoot); cout<<endl; cout<<"程序2已知二叉树的中序与先序序列,求后序序列"<<endl; cout<<"请先输入先序序列,回车后输入中序序列:"<<endl; cin >> pre; cin >> mid; TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1); cout<<"先序遍历结果:"; PreOrder(lpRoot); cout<<endl; cout<<"中序遍历结果:"; MidOrder(lpRoot); cout<<endl; cout<<"后序遍历结果:"; PostOrder(lpRoot); cout<<endl; Release(lpRoot); cout<<endl; system("pause"); return 0; }
(1)程序1的输入方式:
已知二叉树的中序与后序序列,求先序序列,请先输入中序序列,回车后输入后序序列:
例如输入:
DGBAECHF
GDBEHFCA
输出:
先序遍历结果:ABDGCEFH
中序遍历结果:DGBAECHF
后序遍历结果:GDBEHFCA
(2)程序2的输入方式:
已知二叉树的先序与中序序列,求后序序列,请先输入先序序列,回车后输入中序序列:
例如输入:
abdefgc
debgfac
输出:
先序遍历结果:abdefgc
中序遍历结果:debgfac
后序遍历结果:edgfbca
已知中序和前序序列,或者已知中序和后序序列,都能够构造一棵二叉树。在本例中,本人用C语言写程序解答了下面两个算法题:
(1)给出一棵二叉树的中序与后序遍历序列,求出它的先序遍历序列。
(2)给出一棵二叉树的中序与先序遍历序列,求出它的后序遍历序列。
知识点扼要回顾:
所谓二叉树的遍历,是指按一定的顺序对二叉树中的每个结点均访问一次,且仅访问一。按照根结点访问位置的不同,通常把二叉树的遍历分为六种:
TLR(根左右), TRL(根右左), LTR(左根右)
RTL(右根左), LRT(左右根), RLT(右左根)
其中,TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树,这与人们先左后右的习惯不同,因此,往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。
前序遍历的规律是:输出根结点,输出左子树,输出右子树;
中序遍历的规律是:输出左子树,输出根结点,输出右子树;
后序遍历的规律是:输出左子树,输出右子树,输出根结点;
不多说了,看代码吧:)
1. #include <iostream>
2. #include <string>
3.
4. using namespace std;
5.
6. //存储节点数据,为简便起见,这里选用字符
7. typedef char DATA_TYPE;
8.
9. typedef struct tagBINARY_TREE_NODE BINARY_TREE_NODE, *LPBINARY_TREE_NODE;
10.
11. struct tagBINARY_TREE_NODE
12. {
13. DATA_TYPE data; //节点数据
14. LPBINARY_TREE_NODE pLeftChild; //左孩子指针
15. LPBINARY_TREE_NODE pRightChild; //右孩子指针
16. };
17.
18. //
19. //函数名称:TreeFromMidPost
20. //函数功能:给出一棵二叉树的中序与后序序列,构造这棵二叉树。
21. //输入参数:LPBINARY_TREE_NODE & lpNode:二叉树的结点
22. // string mid:存储了二叉树的中序序列的字符串
23. // string post:存储了二叉树的后序序列的字符串
24. // int lm, int rm:二叉树的中序序列在数组mid中的左右边界
25. // int lp, int rp:二叉树的后序序列在数组post中的左右边界
26. //
27. void TreeFromMidPost(LPBINARY_TREE_NODE & lpNode, string mid, string post, int lm, int rm, int lp, int rp)
28. {
29. //构造二叉树结点
30. lpNode = new BINARY_TREE_NODE;
31. lpNode->data = post[rp];
32. lpNode->pLeftChild = NULL;
33. lpNode->pRightChild = NULL;
34.
35. int pos = lm;
36.
37. while (mid[pos] != post[rp])
38. {
39. pos++;
40. }
41. int iLeftChildLen = pos - lm;
42.
43. if (pos > lm)//有左孩子,递归构造左子树
44. {
45. TreeFromMidPost(lpNode->pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1);
46. }
47.
48. if (pos < rm)//有右孩子,递归构造右子树
49. {
50. TreeFromMidPost(lpNode->pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1);
51. }
52. }
53.
54. //
55. //函数名称:TreeFromMidPre
56. //函数功能:给出一棵二叉树的先序与中序序列,构造这棵二叉树。
57. //输入参数: BINARY_TREE_NODE & lpNode:二叉树的结点
58. // string mid:存储了二叉树的中序序列的字符串
59. // string pre:存储了二叉树的先序序列的字符串
60. // int lm, int rm:二叉树的中序序列在数组mid中的左右边界
61. // int lp, int rp:二叉树的先序序列在数组pre中的左右边界
62. //
63. void TreeFromMidPre(LPBINARY_TREE_NODE & lpNode, string mid, string pre, int lm, int rm, int lp, int rp)
64. {
65. //构造二叉树结点
66. lpNode = new BINARY_TREE_NODE;
67. lpNode->data = pre[lp];
68. lpNode->pLeftChild = NULL;
69. lpNode->pRightChild = NULL;
70.
71. int pos = lm;
72.
73. while (mid[pos] != pre[lp])
74. {
75. pos++;
76. }
77. int iLeftChildLen = pos - lm;
78.
79. if (pos > lm)//有左孩子,递归构造左子树
80. {
81. TreeFromMidPre(lpNode->pLeftChild, mid, pre, lm, pos - 1, lp + 1, lp + iLeftChildLen);
82. }
83.
84. if (pos < rm)//有右孩子,递归构造右子树
85. {
86. TreeFromMidPre(lpNode->pRightChild, mid, pre, pos + 1, rm, lp + iLeftChildLen + 1, rp);
87. }
88. }
89.
90. //先序遍历
91. void PreOrder(LPBINARY_TREE_NODE p)
92. {
93. if(p != NULL)
94. {
95. cout << p->data; //输出该结点
96. PreOrder(p->pLeftChild); //遍历左子树
97. PreOrder(p->pRightChild); //遍历右子树
98. }
99. }
100.
101. //中序遍历
102. void MidOrder(LPBINARY_TREE_NODE p)
103. {
104. if(p != NULL)
105. {
106. MidOrder(p->pLeftChild); //遍历左子树
107. cout << p->data; //输出该结点
108. MidOrder(p->pRightChild); //遍历右子树
109. }
110. }
111.
112. //后序遍历
113. void PostOrder(LPBINARY_TREE_NODE p)
114. {
115. if(p != NULL)
116. {
117. PostOrder(p->pLeftChild); //遍历左子树
118. PostOrder(p->pRightChild); //遍历右子树
119. cout << p->data; //输出该结点
120. }
121. }
122.
123. //释放二叉树
124. void Release(LPBINARY_TREE_NODE lpNode)
125. {
126. if(lpNode != NULL)
127. {
128. Release(lpNode->pLeftChild);
129. Release(lpNode->pRightChild);
130. delete lpNode;
131. lpNode = NULL;
132. }
133. }
134.
135.
136. int main(int argc, char* argv[])
137. {
138. string pre; //存储先序序列
139. string mid; //存储中序序列
140. string post; //存储后序序列
141.
142. LPBINARY_TREE_NODE lpRoot; //二叉树根节点指针
143.
144.
145. cout<<"程序1已知二叉树的中序与后序序列,求先序序列"<<endl;
146. cout<<"请先输入中序序列,回车后输入后序序列:"<<endl;
147.
148. cin >> mid;
149. cin >> post;
150.
151. TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1);
152. cout<<"先序遍历结果:";
153. PreOrder(lpRoot);
154. cout<<endl;
155.
156. cout<<"中序遍历结果:";
157. MidOrder(lpRoot);
158. cout<<endl;
159.
160. cout<<"后序遍历结果:";
161. PostOrder(lpRoot);
162. cout<<endl;
163. Release(lpRoot);
164. cout<<endl;
165.
166. cout<<"程序2已知二叉树的中序与先序序列,求后序序列"<<endl;
167. cout<<"请先输入先序序列,回车后输入中序序列:"<<endl;
168. cin >> pre;
169. cin >> mid;
170.
171. TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1);
172. cout<<"先序遍历结果:";
173. PreOrder(lpRoot);
174. cout<<endl;
175.
176. cout<<"中序遍历结果:";
177. MidOrder(lpRoot);
178. cout<<endl;
179.
180. cout<<"后序遍历结果:";
181. PostOrder(lpRoot);
182. cout<<endl;
183. Release(lpRoot);
184. cout<<endl;
185.
186.
187. system("pause");
188. return 0;
189. }
#include <iostream> #include <string> using namespace std; //存储节点数据,为简便起见,这里选用字符 typedef char DATA_TYPE; typedef struct tagBINARY_TREE_NODE BINARY_TREE_NODE, *LPBINARY_TREE_NODE; struct tagBINARY_TREE_NODE { DATA_TYPE data; //节点数据 LPBINARY_TREE_NODE pLeftChild; //左孩子指针 LPBINARY_TREE_NODE pRightChild; //右孩子指针 }; // //函数名称:TreeFromMidPost //函数功能:给出一棵二叉树的中序与后序序列,构造这棵二叉树。 //输入参数:LPBINARY_TREE_NODE & lpNode:二叉树的结点 // string mid:存储了二叉树的中序序列的字符串 // string post:存储了二叉树的后序序列的字符串 // int lm, int rm:二叉树的中序序列在数组mid中的左右边界 // int lp, int rp:二叉树的后序序列在数组post中的左右边界 // void TreeFromMidPost(LPBINARY_TREE_NODE & lpNode, string mid, string post, int lm, int rm, int lp, int rp) { //构造二叉树结点 lpNode = new BINARY_TREE_NODE; lpNode->data = post[rp]; lpNode->pLeftChild = NULL; lpNode->pRightChild = NULL; int pos = lm; while (mid[pos] != post[rp]) { pos++; } int iLeftChildLen = pos - lm; if (pos > lm)//有左孩子,递归构造左子树 { TreeFromMidPost(lpNode->pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1); } if (pos < rm)//有右孩子,递归构造右子树 { TreeFromMidPost(lpNode->pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1); } } // //函数名称:TreeFromMidPre //函数功能:给出一棵二叉树的先序与中序序列,构造这棵二叉树。 //输入参数: BINARY_TREE_NODE & lpNode:二叉树的结点 // string mid:存储了二叉树的中序序列的字符串 // string pre:存储了二叉树的先序序列的字符串 // int lm, int rm:二叉树的中序序列在数组mid中的左右边界 // int lp, int rp:二叉树的先序序列在数组pre中的左右边界 // void TreeFromMidPre(LPBINARY_TREE_NODE & lpNode, string mid, string pre, int lm, int rm, int lp, int rp) { //构造二叉树结点 lpNode = new BINARY_TREE_NODE; lpNode->data = pre[lp]; lpNode->pLeftChild = NULL; lpNode->pRightChild = NULL; int pos = lm; while (mid[pos] != pre[lp]) { pos++; } int iLeftChildLen = pos - lm; if (pos > lm)//有左孩子,递归构造左子树 { TreeFromMidPre(lpNode->pLeftChild, mid, pre, lm, pos - 1, lp + 1, lp + iLeftChildLen); } if (pos < rm)//有右孩子,递归构造右子树 { TreeFromMidPre(lpNode->pRightChild, mid, pre, pos + 1, rm, lp + iLeftChildLen + 1, rp); } } //先序遍历 void PreOrder(LPBINARY_TREE_NODE p) { if(p != NULL) { cout << p->data; //输出该结点 PreOrder(p->pLeftChild); //遍历左子树 PreOrder(p->pRightChild); //遍历右子树 } } //中序遍历 void MidOrder(LPBINARY_TREE_NODE p) { if(p != NULL) { MidOrder(p->pLeftChild); //遍历左子树 cout << p->data; //输出该结点 MidOrder(p->pRightChild); //遍历右子树 } } //后序遍历 void PostOrder(LPBINARY_TREE_NODE p) { if(p != NULL) { PostOrder(p->pLeftChild); //遍历左子树 PostOrder(p->pRightChild); //遍历右子树 cout << p->data; //输出该结点 } } //释放二叉树 void Release(LPBINARY_TREE_NODE lpNode) { if(lpNode != NULL) { Release(lpNode->pLeftChild); Release(lpNode->pRightChild); delete lpNode; lpNode = NULL; } } int main(int argc, char* argv[]) { string pre; //存储先序序列 string mid; //存储中序序列 string post; //存储后序序列 LPBINARY_TREE_NODE lpRoot; //二叉树根节点指针 cout<<"程序1已知二叉树的中序与后序序列,求先序序列"<<endl; cout<<"请先输入中序序列,回车后输入后序序列:"<<endl; cin >> mid; cin >> post; TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1); cout<<"先序遍历结果:"; PreOrder(lpRoot); cout<<endl; cout<<"中序遍历结果:"; MidOrder(lpRoot); cout<<endl; cout<<"后序遍历结果:"; PostOrder(lpRoot); cout<<endl; Release(lpRoot); cout<<endl; cout<<"程序2已知二叉树的中序与先序序列,求后序序列"<<endl; cout<<"请先输入先序序列,回车后输入中序序列:"<<endl; cin >> pre; cin >> mid; TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1); cout<<"先序遍历结果:"; PreOrder(lpRoot); cout<<endl; cout<<"中序遍历结果:"; MidOrder(lpRoot); cout<<endl; cout<<"后序遍历结果:"; PostOrder(lpRoot); cout<<endl; Release(lpRoot); cout<<endl; system("pause"); return 0; }
(1)程序1的输入方式:
已知二叉树的中序与后序序列,求先序序列,请先输入中序序列,回车后输入后序序列:
例如输入:
DGBAECHF
GDBEHFCA
输出:
先序遍历结果:ABDGCEFH
中序遍历结果:DGBAECHF
后序遍历结果:GDBEHFCA
(2)程序2的输入方式:
已知二叉树的先序与中序序列,求后序序列,请先输入先序序列,回车后输入中序序列:
例如输入:
abdefgc
debgfac
输出:
先序遍历结果:abdefgc
中序遍历结果:debgfac
后序遍历结果:edgfbca
发表评论
-
C#设计模式[链接]
2011-01-05 14:19 838http://zhenyulu.cnblogs.com/cat ... -
C/C++预处理、编译、链接过程【Z】
2011-01-05 14:07 1761在Linux下进行C语言编程,必然要采用GNU GCC来编 ... -
c语言输出重定向【Z】
2010-10-03 22:41 2998可以使用重定向操作符将命令输入和输出数据流从默认位置重定向到不 ... -
C++标准库【Z】
2010-09-29 22:42 885C++标准库的内容分为10类: C1.语言支持 C2.输入/ ... -
c语言socket编程指南
2010-09-29 20:39 1265介绍 Socket 编程让你沮丧吗?从man page ... -
kmp算法【Z】
2010-09-24 19:02 781我们这里说的KMP不是拿来放电影的(虽然我很喜欢这个软件), ... -
虚拟继承、虚函数学习总结【Z】
2010-09-24 16:03 1447虚拟继承、虚函数学习总结 ... -
C++对象内存布局测试总结【Z】
2010-09-24 16:02 1100对于普通的C++对象内存布局,简单得不得了,就不做总结了。这里 ... -
C++隐式成员函数2【Z】
2010-09-24 15:37 9331 编译器自动生成的基本函数 C++编译器会在开发人员没有声 ... -
C++隐式成员函数【Z】
2010-09-24 15:27 1260这篇文章讲述的是C++提供的一些由编译器自 ... -
extern详解【Z】
2010-09-24 14:44 7771 基本解释 extern可 ... -
KMP字符串匹配算法【Z】
2010-09-14 22:44 1148最普通的字符串匹配 ... -
C语言变量存储类型
2010-09-14 19:58 1178C语言变量存储类型 auto static extern ... -
C/C++中的void
2010-09-14 19:54 9441.void的含义 (1)voi ... -
排序算法
2010-09-10 11:10 10471、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排 ... -
C++ Socket连接实现【转载】
2010-08-31 21:27 2916C++ socket程序 下面是一个C++调用windo ... -
虚函数/纯虚函数
2010-08-31 19:17 5261.首先:强调一个概念 定义一个函数 ... -
纯虚函数
2010-08-31 19:07 1007一、定义. 纯虚函数是在基类 中声明的虚函数,它在基类中没 ... -
C++ 对象的内存布局
2010-08-31 16:38 920转载-->C++ 对象的内存布局 ... -
虚继承
2010-08-31 16:06 782虚拟继承在一般的应用 ...
相关推荐
二叉树遍历,c语言 实现数据结构二叉树遍历
二叉树遍历(C语言),输出遍历结果,入门小程序,适合C语言入门小练习 二叉树遍历(C语言),输出遍历结果,入门小程序,适合C语言入门小练习 二叉树遍历(C语言),输出遍历结果,入门小程序,适合C语言入门小...
二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、python、java的实现).rar 二叉树遍历(c语言、...
二叉树遍历的特点
用堆栈实现二叉树遍历,C语言实现的数据结构
二叉树遍历问题C语言源码和简单教程
C语言实现二叉树的非递归遍历,完整源代码
用c语言实现的二叉树的遍历,是数据结构中的经典案例。里面含有设计报告和源代码。代码拷贝出来即可运行。
数据结构二叉树的遍历,采用C语言实现二叉树的非递归先序、中序、后序遍历算法
二叉树遍历 c 层遍历 完整结构层遍历 只有层遍历代码及创建二叉树代码
实现二叉树的层次遍历实现二叉树的层次遍历实现二叉树的层次遍历实现二叉树的层次遍历
二叉树遍历,先根,中根,后根,及程序分析。c语言实现
运行时从键盘输入先序序列,创建对应二叉树T,然后对T进行非递归中序遍历、递归后序遍历和层序遍历。
用c语言实现二叉树的三种遍历,所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行...
有具体的二叉树创建与遍历过程 C语言实现
利用递归方式完成二叉树的简单创建以及遍历。
二叉树的创建与遍历,C语言实现
二叉树的非递归遍历 二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历
基于二叉链表的二叉树遍历输出,实现了先序遍历构造二叉树,先,中,后序遍历输出二叉树功能。
包括两个程序,一个实现二叉树的三种递归遍历,求结点数,求深度,求广度,另一个实现二叉树的非递归遍历,经调试无误