題目1078：二叉樹遍歷

時間限制：1 秒

內(nèi)存限制：32 兆

特殊判題：否

提交：5326

解決：3174

題目描述：

二叉樹的前序、中序、后序遍歷的定義：
前序遍歷：對任一子樹，先訪問跟，然后遍歷其左子樹，最后遍歷其右子樹；
中序遍歷：對任一子樹，先遍歷其左子樹，然后訪問根，最后遍歷其右子樹；
后序遍歷：對任一子樹，先遍歷其左子樹，然后遍歷其右子樹，最后訪問根。
給定一棵二叉樹的前序遍歷和中序遍歷，求其后序遍歷（提示：給定前序遍歷與中序遍歷能夠唯一確定后序遍歷）。

輸入：

兩個字符串，其長度n均小于等于26。
第一行為前序遍歷，第二行為中序遍歷。
二叉樹中的結(jié)點名稱以大寫字母表示：A，B，C....最多26個結(jié)點。

輸出：

輸入樣例可能有多組，對于每組測試樣例，
輸出一行，為后序遍歷的字符串。

樣例輸入：

ABC BAC FDXEAG XDEFAG

樣例輸出：

BCA XEDGAF

分析：先遞歸重建二叉樹，在遞歸后序遍歷。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <string> 5 using namespace std; 6 7 typedef struct Node{ 8 char data; 9 struct Node *lchild; 10 struct Node *rchild; 11 }BTree; 12 13 string str1, str2; 14 void postOrder(BTree *T) 15 { 16 if(T!=NULL) 17 {if(T->lchild!=NULL) 18 postOrder(T->lchild); 19 if(T->rchild!=NULL) 20 postOrder(T->rchild); 21 cout<<T->data; 22 } 23 return; 24 } 25 26 BTree *trans(int l1,int h1,int l2,int h2){ 27 if(l1 > h1 || l2 > h2)//遞歸出口，不符合條件，直接返回空節(jié)點 28 return NULL; 29 int j = l2; 30 31 while(str2[j] != str1[l1]){ j++; } 32 33 //構(gòu)造根節(jié)點 34 BTree *T=(BTree*)malloc(sizeof(BTree)); 35 T->data=str2[j]; 36 T->lchild=NULL; 37 T->rchild=NULL; 38 39 T->lchild=trans(l1+1,l1+j-l2,l2,j-1); //返回左子樹 40 T->rchild=trans(l1+j-l2+1,h1,j+1,h2); //返回右子樹 41 return T; 42 } 43 44 45 int main() 46 { 47 48 while(cin >> str1 >> str2) 49 { 50 int L1 = str1.length(); 51 int L2 = str2.length(); 52 BTree *T = trans(0,L1-1,0,L2-1); 53 postOrder(T); 54 cout << endl; 55 } 56 return 0; 57 }

?

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 typedef struct Node{ 8 char data; 9 struct Node *lchild; 10 struct Node *rchild; 11 }BTree; 12 13 char str1[30], str2[30]; 14 15 void postOrder(BTree *T){ 16 if(T != NULL){ 17 if(T->lchild != NULL) 18 postOrder(T->lchild); 19 if(T->rchild != NULL) 20 postOrder(T->rchild); 21 printf("%c", T->data); 22 } 23 return; 24 } 25 26 BTree *trans(int l1,int h1,int l2,int h2){ 27 if(l1 > h1 || l2 > h2)//遞歸出口，不符合條件，直接返回空節(jié)點 28 return NULL; 29 int j = l2; 30 31 while(str2[j] != str1[l1]){ j++; } 32 33 //構(gòu)造根節(jié)點 34 BTree *T = (BTree*)malloc(sizeof(BTree)); 35 T->data = str2[j]; 36 T->lchild = NULL; 37 T->rchild = NULL; 38 39 T->lchild = trans(l1+1, l1+j-l2, l2, j-1); //返回左子樹 40 T->rchild = trans(l1+j-l2+1, h1, j+1, h2); //返回右子樹 41 return T; 42 } 43 44 45 int main() 46 { 47 int L1, L2; 48 while(scanf("%s %s", str1, str2) != EOF){ 49 L1 = strlen(str1); 50 L2 = strlen(str2); 51 BTree *T = trans(0,L1-1,0,L2-1); 52 postOrder(T); 53 printf("\n"); 54 } 55 return 0; 56 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/qinduanyinghua/p/6418728.html

總結(jié)

以上是生活随笔為你收集整理的九度oj 题目1078：二叉树遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。