数据结构上机测试4.1:二叉树的遍历与应用1 (*详解

2/22/2017来源:ASP.NET技巧人气:351

数据结构上机测试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; }

他奶奶的,今天这一天过的,到现在晚上了才做了两题。。