创建二叉树(已知先序和中序或中序和后序)C-数据结构

题目

已知二叉树的先序序列和中序序列或中序序列和后序序列，创建二叉树

思路

先序序列和后序序列可以找到根节点(先序序列根节点在最前面，后序在最后面)，然后可以通过中序序列将二叉树分为左子树和右子树，然后根据左子树的节点个数和右子树的节点个数可以得到在先序序列和后序序列中左右子树的根节点，由此递推，可以得到完整的二叉树。

代码

#include
#include
#define MAXSIZE 10000

typedef struct tree {
	int data;
	struct tree*left;
	struct tree*right;	
}Tree;

void createTree(Tree**t,int *a,int *b,int l1,int r1,int l2,int r2);//先序中序遍历二叉树
void rearPrint(Tree *t);   //后序遍历二叉树 
Tree* createTree1(int *a,int *b,int root,int left,int right); //中序后序创建二叉树
void prePrint(Tree *t);   //先序遍历二叉树 
void LayerOrder(Tree *t);  //层序遍历二叉树

 
int main()
{
	int a[MAXSIZE]={0},b[MAXSIZE]={0};
	int len=0;
	Tree *tree;
	printf("请输入先序序列和中序序列的长度：") ;
	scanf("%d",&len);
	printf("请输入先序序列：") ;
	for(int i=0;idata=a[l1];
	 int root=0;
	 for(root=l2;root<=r2;root++){
	 	if(a[l1]==b[root]){
	 		break;
		 }
	 }  
	 if(root-l2!=0){
	 	createTree(&(*t)->left,a,b,l1+1,l1+root,l2,root-1);
	 }else{
	 	(*t)->left=NULL;
	 }
	 if(root-r2!=0){
	 	createTree(&(*t)->right,a,b,r1-(r2-root)+1,r1,root+1,r2);
	 }else{
	 	(*t)->right=NULL;
	 }
	 
 }
Tree* createTree1(int *a,int *b,int root,int left,int right) //中序后序创建二叉树
{
	if(left>right){
		return NULL;
	}
	Tree *t=(Tree*)malloc(sizeof(Tree));
	t->data=b[root];
	int i;
	for(i=left;i<=right;i++) 
	{
		if(b[root]==a[i]) break;
	}
	t->left=createTree1(a,b,root-(right-i)-1,left,i-1);
	t->right=createTree1(a,b,root-1,i+1,right);
	return t;
}
 void rearPrint(Tree *t)   //后序遍历二叉树 
 {
 	if(!t){
 		return;
	 }
	 rearPrint(t->left);
	 rearPrint(t->right);
	 printf("%d ",t->data);
 }
  void prePrint(Tree *t)   //先序遍历二叉树 
 {
 	if(!t){
 		return;
	 }
	 printf("%d ",t->data);
	 prePrint(t->left);
	 prePrint(t->right);
 }
 void LayerOrder(Tree *t)  //层序遍历二叉树
 {
 	if(!t) return;
 	int start=-1,end=0,flag=0;
 	Tree *p[MAXSIZE];
 	p[end]=t;
 	while(start!=end){
 		start++;
 		if(flag){
 			printf(" ");
		 }
		 printf("%d",p[start]->data);
		 flag=1;
		if (p[start]->left) {
            end++;
            p[end] = p[start]->left;
        }
        if (p[start]->right) {
            end++;
            p[end] = p[start]->right;
        }
	 }
 } 
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

运行结果