數據結構上機測試4.1:二叉樹的遍歷與應用1 (*詳解

2019-11-08 20:09:09

字體：大中小

來源：轉載

供稿：網友

數據結構上機測試4.1:二叉樹的遍歷與應用1 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic PRoblem Description

輸入二叉樹的先序遍歷序列和中序遍歷序列，輸出該二叉樹的后序遍歷序列。 Input

第一行輸入二叉樹的先序遍歷序列；第二行輸入二叉樹的中序遍歷序列。 Output

輸出該二叉樹的后序遍歷序列。 Example Input

ABDCEF BDAECF Example Output

DBEFCA Hint

#include <stdio.h>#include <string.h>/*只要給出先序，中序；或者后序，中序；就可以畫出樹了。如果只有先和后，會有多種情況就畫不出來了先序是（根左右所以第一個就是根后序是（左右根所以最后一個是根在先或者后序中找到根后，放在中序里看，根的左邊就是都是屬于左邊的，右邊就是都屬于右邊樹的*/typedef struct node{ struct node *l,*r; char data;}node;node *print_postOrder(int len,char *a,char *b){ int i; char x = a[0]; if(len<=0)//遞歸的結束條件 return NULL; node *root; root = (node *)malloc(sizeof(struct node)); root->data = x;//一定別忘了把根的數據賦值過去，要不然根什么都毛了 for(i=0; i<len; i++){ if(b[i]==x)//尋找在中序里根的位置下標 break; } root->l = print_postOrder(i,a+1,b);//左子樹的長度，左子樹在先序中開始的地方，左子樹在中序中開始的地方 root->r = print_postOrder(len-i-1,a+i+1,b+i+1);//右子樹的長度，右子樹在先序中開始的地方，右子樹在中序中開始的地方 printf("%c",root->data);}int main(){ char a[100],b[100]; scanf("%s %s",a,b); int len = strlen(a); print_postOrder(len,a,b); printf("/n"); return 0;}

他奶奶的，今天這一天過的，到現在晚上了才做了兩題。。

上一篇：走迷宮

下一篇：hdu2191 多重背包（dp）