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