二叉树的中序遍历为：4、5、2、1、6、3、8、7、9.后序遍历为：5、4、2、6、8、9、7、3、1，画出二叉树

Question

如题所述

Answer 1

首先理解概念：
前序遍历：访问根结点的操作发生在遍历其左右子树之前。
中序遍历：访问根结点的操作发生在遍历其左右子树之中(间)。
后序遍历：访问根结点的操作发生在遍历其左右子树之后。
来看你的题目：
1.由后序遍历5、4、2、6、8、9、7、3、1可知根为1
2.在中序遍历4、5、2、1、6、3、8、7、9中找到1，可知（左）452-1-63879（右）
对左右支分别重复上述步骤，即
在后序遍历中观察452的相对位置可知2为根，则有45-2-空
在后序遍历中观察63879的相对位置可知3为根，则有6-3-879
……
由此可得出树的结构为
------------------------------1
---------2L 3R
----4L 空 6L 7R
-空 5R 空 空 8L 9R
图中L表示左，R表示右，用空格区分位置，希望楼主能够明白

Answer 2

步骤：
后序最后一个值为1，则表示根节点为1。
查看中序由1，分割成 452 和 63879 两棵子树。

对“左子树”---中序452和后序542，得到根节点为2。中序452表明45组成2的左子树，根节点为4，5为4的右子树。

对“右子树”---中序63879和后序68973，得到根节点为3。6为左子树，右子树为--中序879和后序897。所以根节点为7，左子树为8，右子树为9。

所以最后是 1
/ \
2 3
/ / \
4 6 7
\ / \
5 8 9

Answer 3

/*
10 用0替代 运行C程序 输入如下：
***********Bitree*****
input a tree preorder:
1236457890
input a tree midoeder:
3625419807

1236457890
3625419807
6354290871
结果为：6 3 5 4 2 9 10 8 7 1
*/

#include <stdio.h>
#include <stdlib.h>
#define max 100

typedef char ch[10];

void fun(ch x,ch y){
if(*x){
ch x1,x2,y1,y2;
char *p,*q,*t; char r; int n=0;
r=*x; t=y; p=y1; q=y2;
while(*t!=r){
*(p++)=*(t++);
n++;
}
t++; *p='\0';
while(*t) *(q++)=*(t++);
*q='\0'; t=&x[1]; p=x1; q=x2;
for (int i=0;i<n;i++) *(p++)=*(t++); *p='\0';
while(*t) *(q++)=*(t++); *q='\0';
fun(x1,y1); fun(x2,y2);
printf("%c",r);
}
}

void f(){
ch x,y;
printf("input a tree preorder:\n"); gets(x);
printf("input a tree midoeder:\n"); gets(y);
printf("\n");
puts(x); puts(y);
fun(x,y);
printf("\n");
}

void main(){
printf("***********Bitree************\n");
int n=1;
while(n){
f();
printf("0:break 1 :continue\n");
printf("input your select :");
scanf("%d",&n); getchar();
}
}