ggg002磁力:二叉树遍历及C语言实现

来源：百度文库 编辑：偶看新闻 时间：2024/04/27 23:14:12
二叉树遍历及C语言实现

已知中序和前序序列，或者已知中序和后序序列，都能够构造一棵二叉树。在本例中，本人用C语言写程序解答了下面两个算法题：

（1）给出一棵二叉树的中序与后序遍历序列，求出它的先序遍历序列。

（2）给出一棵二叉树的中序与先序遍历序列，求出它的后序遍历序列。

知识点扼要回顾：
所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问一次，且仅访问一。按照根结点访问位置的不同，通常把二叉树的遍历分为六种：
TLR（根左右）, TRL（根右左）, LTR（左根右）
RTL（右根左）, LRT（左右根）, RLT（右左根）

其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。

前序遍历的规律是：输出根结点，输出左子树，输出右子树；
中序遍历的规律是：输出左子树，输出根结点，输出右子树；
后序遍历的规律是：输出左子树，输出右子树，输出根结点；

不多说了，看代码吧：）

   1. #include  
   2. #include  
   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<<"程序１已知二叉树的中序与后序序列，求先序序列"< 146.     cout<<"请先输入中序序列，回车后输入后序序列："< 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< 155.  
156.     cout<<"中序遍历结果："; 
157.     MidOrder(lpRoot); 
158.     cout< 159.  
160.     cout<<"后序遍历结果："; 
161.     PostOrder(lpRoot); 
162.     cout< 163.     Release(lpRoot); 
164.     cout< 165.  
166.     cout<<"程序２已知二叉树的中序与先序序列，求后序序列"< 167.     cout<<"请先输入先序序列，回车后输入中序序列："< 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< 175.  
176.     cout<<"中序遍历结果："; 
177.     MidOrder(lpRoot); 
178.     cout< 179.  
180.     cout<<"后序遍历结果："; 
181.     PostOrder(lpRoot); 
182.     cout< 183.     Release(lpRoot); 
184.     cout< 185.  
186.  
187.     system("pause"); 
188.     return 0; 
189. } 

#include #include 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<<"程序１已知二叉树的中序与后序序列，求先序序列"<> mid; cin >> post; TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1); cout<<"先序遍历结果："; PreOrder(lpRoot); cout<> pre; cin >> mid; TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1); cout<<"先序遍历结果："; PreOrder(lpRoot); cout<
（1）程序1的输入方式：
已知二叉树的中序与后序序列，求先序序列，请先输入中序序列，回车后输入后序序列：
例如输入：
DGBAECHF
GDBEHFCA
输出：
先序遍历结果：ABDGCEFH
中序遍历结果：DGBAECHF
后序遍历结果：GDBEHFCA

（2）程序2的输入方式：
已知二叉树的先序与中序序列，求后序序列，请先输入先序序列，回车后输入中序序列：
例如输入：
abdefgc
debgfac
输出：
先序遍历结果：abdefgc
中序遍历结果：debgfac
后序遍历结果：edgfbca


> 前序遍历、中序遍历、后序遍历的关系
递归求解，已知先序和中序，或者后序和中序都能求出一种唯一的。例如    先序：ABCDE       中序：CBDAE递归第一次：在所有节点中找根节点，即先序最左边的（A），所以（A）为根节点。再到中序里以A为分界线分成左子树（CBD）和右子树（E）；递归第二次：在左子树（CBD）中找根节点，及左子树节点中在先序里最靠前的（B），以（B）分割，即左子树（C），右子树（D）；递归结束条件：只有一个节点是返回
代码如下：
已知前序中序求后序procedure Solve(pre,mid:string);var i:integer; beginif (pre='') or (mid='') then exit; i:=pos(pre[1],mid); solve(copy(pre,2,i),copy(mid,1,i-1)); solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i)); post:=post+pre[1];  end;已知中序后序求前序（NOIP2001普及组第3题）procedure Solve(mid,post:string); var i:integer; begin if (mid='') or (post='') then exit;i:=pos(post[length(post)],mid); pre:=pre+post[length(post)];  solve(copy(mid,1,I-1),copy(post,1,I-1)); solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));end;已知前序后序求中序function ok(s1,s2:string):boolean; var i,l:integer; p:boolean; begin ok:=true; l:=length(s1);for i:=1 to l do begin p:=false; for j:=1 to l do if s1[i]=s2[j] then p:=true; if not p then begin ok:=false;exit;end;end; end; Procedure solve(pre,post:string); var i:integer; begin if (pre='') or (post='') then exit;i:=0; repeat inc(i); until ok(copy(pre,2,i),copy(post,1,i)); solve(copy(pre,2,i),copy(post,1,i)); midstr:=midstr+pre[1]; solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1)); end;

求二叉树遍历算法C语言实现的 在vb中实现二叉树的建立及遍历 建立二叉树的先序遍历（用递归的方法）c语言源代码 求java实现二叉树启遍历的算法 二叉树遍历程序 二叉树的遍历 二叉树遍历问题 二叉树的遍历 关于二叉树的遍历 有关二叉树的遍历 请问哪有先序和中序确定唯一的二叉树的C语言实现程序 怎样用JAVA实现二叉树的建立，遍历和节点删除 怎样用JAVA实现二叉树的建立，遍历和节点删除 求高手解答数据结构—按层次遍历二叉树`语言C++ C语言编最优二叉树 关于二叉树的问题(C语言) 关于二叉树的问题(C语言) 二叉树遍历的程序怎么写？ 谁会写二叉树的遍历操作？？？？ 二叉树的层次遍历算法 关于二叉树遍历的问题 什么是二叉树数的遍历 什么是二叉树数的遍历 二叉树中的层序遍历？