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

2019-11-08 00:59:35

字体：大中小

来源：转载

供稿：网友

PRoblem Description 输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。 Input 第一行输入二叉树的先序遍历序列；第二行输入二叉树的中序遍历序列。 Output 输出该二叉树的后序遍历序列。 Example Input

ABDCEF BDAECF

Example Output

DBEFCA

先序遍历的第一个为根节点，再在中序遍历中找到根节点的位置，根节点左边为左子树，右边为右子树，之后在左右子树重复之前的操作。

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct node{ char date; struct node *l,*r;}tree;tree *creat(int len,char s[60],char h[60]){ int i; tree *t; if(len<=0) return NULL; t=(tree *)malloc(sizeof(tree)); t->date=s[0]; for(i=0;i<len;i++) { if(h[i]==s[0]) break; } t->l=creat(i,s+1,h); t->r=creat(len-i-1,s+i+1,h+i+1); return t;}void show(tree *root){ if(root) { show(root->l); show(root->r); printf("%c",root->date ); }}int main(){ tree *root; char s[60],h[60]; int len; scanf("%s %s",s,h); len=strlen(h); root=creat(len,s,h); show(root); printf("/n"); return 0;}

上一篇：类名.this的使用

下一篇：操作系统是如何工作的-------通过一个简单的时间片轮转多道程序内核代码分析