sdut原题链接
数据结构上机测试4.1:二叉树的遍历与应用1 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。
Input 第一行输入二叉树的先序遍历序列； 第二行输入二叉树的中序遍历序列。
Output 输出该二叉树的后序遍历序列。
Example Input ABDCEF BDAECF
Example Output DBEFCA
Hint
Author
以下为accepted代码
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;}BinTree;BinTree *root;char st1[104], st2[104];BinTree * ans(int len, char *st1, char *st2)//二叉树的建立与后序输出{ BinTree *root; int i; if(len == 0)///判断当前序列是否为空 return NULL; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st1[0];//寻找根节点，根节点为先序序列st1的第一个 for(i = 0; i < len; i++)//寻找根节点在中序序列中的位置 { if(st2[i] == root->date) break; } root->left = ans(i, st1+1, st2);//（左子树的长度，左子树在st1中的开始位置，左子树在st2中的开始位置） root->right = ans(len-i-1, st1+i+1, st2+i+1);//（右子树的长度，右子树在st1中的开始位置，右子树在st2中的开始位置） printf("%c", root->date); return root;}int main(){ int len; scanf("%s %s", st1, st2); len = strlen(st1); ans(len, st1, st2);//调用二叉树的建立与后序输出函数 printf("/n"); return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 112KBSubmit time: 2017-02-07 17:25:34****************************************************/新闻热点
疑难解答
