lc52520
- 浏览: 369320 次
- 性别:
- 来自: 成都
-
文章分类
最新评论
-
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<<"程序１已知二叉树的中序与后序序列，求先序序列"<<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<<"程序２已知二叉树的中序与先序序列，求后序序列"<<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<<"程序１已知二叉树的中序与后序序列，求先序序列"<<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<<"程序２已知二叉树的中序与先序序列，求后序序列"<<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<<"程序１已知二叉树的中序与后序序列，求先序序列"<<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<<"程序２已知二叉树的中序与先序序列，求后序序列"<<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<<"程序１已知二叉树的中序与后序序列，求先序序列"<<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<<"程序２已知二叉树的中序与先序序列，求后序序列"<<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 872http://zhenyulu.cnblogs.com/cat ... -
C/C++预处理、编译、链接过程【Z】
2011-01-05 14:07 1802在Linux下进行C语言编程，必然要采用GNU GCC来编 ... -
c语言输出重定向【Z】
2010-10-03 22:41 3031可以使用重定向操作符将命令输入和输出数据流从默认位置重定向到不 ... -
C++标准库【Z】
2010-09-29 22:42 923C++标准库的内容分为10类： C1.语言支持 C2.输入/ ... -
c语言socket编程指南
2010-09-29 20:39 1297介绍 Socket 编程让你沮丧吗？从man page ... -
kmp算法【Z】
2010-09-24 19:02 819我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件）， ... -
虚拟继承、虚函数学习总结【Z】
2010-09-24 16:03 1490虚拟继承、虚函数学习总结 ... -
C++对象内存布局测试总结【Z】
2010-09-24 16:02 1135对于普通的C++对象内存布局，简单得不得了，就不做总结了。这里 ... -
C++隐式成员函数2【Z】
2010-09-24 15:37 9721 编译器自动生成的基本函数 C++编译器会在开发人员没有声 ... -
C++隐式成员函数【Z】
2010-09-24 15:27 1302这篇文章讲述的是C++提供的一些由编译器自 ... -
extern详解【Z】
2010-09-24 14:44 8141 基本解释 extern可 ... -
KMP字符串匹配算法【Z】
2010-09-14 22:44 1187最普通的字符串匹配 ... -
C语言变量存储类型
2010-09-14 19:58 1217C语言变量存储类型 auto static extern ... -
C/C++中的void
2010-09-14 19:54 9761.void的含义 (1)voi ... -
排序算法
2010-09-10 11:10 10911、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排 ... -
C++ Socket连接实现【转载】
2010-08-31 21:27 2951C++ socket程序 下面是一个C++调用windo ... -
虚函数/纯虚函数
2010-08-31 19:17 5491.首先：强调一个概念 定义一个函数 ... -
纯虚函数
2010-08-31 19:07 1045一、定义. 纯虚函数是在基类 中声明的虚函数，它在基类中没 ... -
C++ 对象的内存布局
2010-08-31 16:38 962转载-->C++ 对象的内存布局 ... -
虚继承
2010-08-31 16:06 816虚拟继承在一般的应用 ...
相关推荐
二叉树的遍历C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历...
本文将详细介绍二叉树遍历的相关知识点，特别是用C语言实现时的特点。 #### 二叉树简介 二叉树是一种树形结构，每个节点最多有两个子节点：一个左子节点和一个右子节点。根据节点间的关系，二叉树可以分为多种类型...
二叉树的遍历 C语言 数据结构课设 本文将详细讲解二叉树的遍历的实现，包括二叉树的存储、先序遍历、中序遍历、后序遍历和叶子结点的统计。 一、需求分析 二叉树的遍历是数据结构课程的经典案例，本文将使用 C ...
二叉树遍历（C语言），输出遍历结果，入门小程序，适合C语言入门小练习 二叉树遍历（C语言），输出遍历结果，入门小程序，适合C语言入门小练习 二叉树遍历（C语言），输出遍历结果，入门小程序，适合C语言入门小...
在C语言中实现二叉树遍历涉及到对指针的熟练操作和递归理解。下面将详细介绍二叉树的三种基本遍历方法：前序遍历、中序遍历和后序遍历，以及如何用C语言来实现它们。 1. 前序遍历（根-左-右） 前序遍历的顺序是先...
二叉树的创建与遍历C语言实现代码.zip二叉树的创建与遍历C语言实现代码.zip二叉树的创建与遍历C语言实现代码.zip二叉树的创建与遍历C语言实现代码.zip二叉树的创建与遍历C语言实现代码.zip二叉树的创建与遍历C语言...
二叉树遍历（c语言、python、java的实现）.rar 二叉树遍历（c语言、python、java的实现）.rar 二叉树遍历（c语言、python、java的实现）.rar 二叉树遍历（c语言、python、java的实现）.rar 二叉树遍历（c语言、...
给定的C语言代码实现了二叉树的创建及前序、中序、后序遍历，但仅展示了递归实现。下面，我们将重点分析非递归遍历的实现。 #### 四、非递归前序遍历 ```c void PreOrderNonRecursive(BitTree T) { Stack S; // ...
总的来说，这个项目提供了深入理解和实践二叉树遍历算法的机会，对于学习和掌握C语言编程以及数据结构与算法的运用至关重要。通过这样的练习，开发者可以提升逻辑思维能力，更好地应对实际的软件开发问题。
本文将深入探讨C语言中实现二叉树遍历的方法，包括先根遍历、中根遍历和后根遍历，并通过程序分析帮助理解这些概念。 **先根遍历（Preorder Traversal）** 先根遍历的顺序是：先访问根节点，然后递归地遍历左子树，...
数据结构二叉树的遍历，采用C语言实现二叉树的非递归先序、中序、后序遍历算法
从给定的文件信息来看，该文件主要围绕“堆栈实现二叉树遍历数据结构”的主题，通过C语言编程来实现。以下是基于标题、描述、标签和部分内容的知识点总结和详细说明： ### 1. 数据结构基础 数据结构是计算机科学的...
二叉树遍历 c 层遍历 完整结构层遍历 只有层遍历代码及创建二叉树代码
二叉树遍历是针对这种数据结构进行操作的重要算法，用于访问或处理树中的每一个节点。本篇将详细介绍如何用C语言实现二叉树的递归与非递归遍历，以及如何计算节点数、树的深度和宽度。 首先，我们来看二叉树的递归...
### C语言实现二叉树的创建与遍历 在计算机科学中，二叉树是一种重要的数据结构，它具有丰富的应用场景，比如文件系统、编译器的设计等。本篇文章将详细介绍如何使用C语言来实现二叉树的基本操作：创建与遍历。 ##...
二叉树遍历问题C语言源码和简单教程 二叉树是一种常用的数据结构，遍历是指从根节点开始，对树中的每个节点进行访问的过程。二叉树的遍历方式有多种，例如前序遍历、中序遍历和后序遍历等。每种遍历方式都有递归和...
通过对上述代码的分析，我们可以看到二叉树遍历的基本思路是通过递归的方式来实现的。在实际应用中，二叉树及其遍历方法是非常重要的基础，掌握这些基本概念和技术对于深入理解高级数据结构和算法设计具有重要意义。
用c语言实现二叉树的三种遍历，所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行...
### 层次遍历二叉树C语言实现详解 #### 核心概念解析 在深入分析给定代码之前，我们先来理解一下几个关键的概念。 **二叉树**：二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常被称作左子节点和右...
这是用c语言编写的二叉树层次遍历程序，使用非递归的方法实现。欢迎使用。