二叉树遍历及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 > 前序遍历、中序遍历、后序遍历的关系 |
|