先序遍历和中序遍历建立二叉树，并且以后续遍历输出二叉树_建立一个二叉树并按先序中序后序遍历输出

先序遍历和中序遍历建立二叉树，并且以后续遍历输出二叉树

假设先序遍历为：abcdefghi（根 左 右）
中序遍历为：bcaedghfi （左 根 右）

1. 首先在先序遍历中可以确认a为根节点
2. 在中续遍历中可以看到bc（初始位置为b（长度为2）） 为a 的左子树 edghfi（初始位置为e长度为6）为a的右子树
3. 同时注意前序序列中a左子树的初始位置为b（长度为2），右子树的初始位置为e长度为6；
4. 递归调用求a的左子树的全部，递归调用求a的右子树

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
	char data;
    struct node *lchild,*rchild;
}node,*tree;
tree creat(char *a,char *b,int n)
{
	tree t;
	//char a[0]=a;
	int i=0,len;
	if(n<=0) return;
	 t=(tree)malloc(sizeof(node));
	 t->data=a[0];
	 while(b[i]!=a[0])
	 {
	 	i++;
	 
	 	
	 }
	 len=n-i-1;
	 t->lchild=creat(a+1,b,i);
	 t->rchild=creat(a+i+1,b+i+1,len);
	 printf("%c",t->data);
	 return t;
	
	
	
}
int main()
{
	char a[20],b[20];
	tree t;
		int n;
		printf("请先输入长度/n");
		n=scanf("%d",&n);
	printf("请先输入先序序列/n");
	scanf("%s",a);
	printf("请输入中序序列/n");
	scanf("%s",b);
	creat(a,b,n);
	return 0;
	
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44