题目： 二叉树的不同形态
问题描述
给定二叉树T（树深度H<=10，深度从1开始，结点个数N<1024，结点编号1~N）的层次遍历序列和中序遍历序列，输出T从左向右叶子结点以及二叉树先序和后序遍历序列。
输入格式
输入共三行：第一行是整数n，表示二叉树中的结点数目；第二行有n个整数，表示该二叉树的层次遍历序列；第三行也是n个整数，表示该二叉树的中序遍历序列。整数间以空格隔开。
输出格式
输出三行，分别是：从左向右的叶子结点，先序遍历序列，后序遍历序列。结点编号用空格隔开。
样例输入
7
3 5 4 2 6 7 1
2 5 3 6 4 7 1
样例输出
2 6 1
3 5 2 4 6 7 1
2 5 6 1 7 4 3
1、已知层次遍历和中序遍历创建二叉树
1 tree createTree(int *level,int *in,int begin1, int end1,int begin2,int end2) 2 { 3 if(begin2>end2) return NULL; 4 else 5 { 6 treenode *t; 7 t=(treenode*)malloc(sizeof(treenode)); 8 9 int i,j; 10 int flag=0; 11 for(i=begin1;i<=end1;i++) 12 { 13 for(j=begin2;j<=end2;j++) 14 { 15 if(level[i]==in[j]) 16 { 17 flag=1; break; 18 } 19 } 20 if(flag==1) break; 21 } 22 23 t->data=level[i]; 24 t->lchild=createTree(level,in,begin1+1,end1,begin2,j-1); 25 t->rchild=createTree(level,in,begin1+1,end1,j+1,end2); 26 return t; 27 28 29 } 30 31 }
*********对比：已知先序和中序的create***************
1 tree createTree(char *pre,char *in,int n) 2 { 3 int k; 4 char *p; 5 //if(n<=0) return NULL; 6 7 treenode *b=(treenode*)malloc(sizeof(treenode)); 8 b->data=*pre; 9 for(p=in;p<in+n;p++) 10 { 11 if(*p==*pre) break; 12 } 13 14 k=p-in; 15 b->lchild=createTree(pre+1,in,k); 16 b->rchild=createTree(pre+k+1,p+1,n-k-1); 17 return b; 18 19 }
2、输出叶子结点：
1 void printleaf(tree t) 2 { 3 if(t==NULL) 4 { 5 return; 6 } 7 else 8 { 9 if(!t->lchild&&!t->rchild) 10 { 11 printf("%d ",t->data); 12 } 13 printleaf(t->lchild); 14 printleaf(t->rchild); 15 } 16 }//from CSDN 17 18 19 20 /*void printleaf(tree t) 21 { 22 if(!t->lchild&&!t->rchild) 23 { 24 printf("%d ",t->data); 25 } 26 else//多余的else 27 { 28 printleaf(t->lchild); 29 printleaf(t->rchild); 30 } 31 }//MINE*/
纠错：
20 void printleaf(tree t)
21 {
22 if(!t->lchild&&!t->rchild)
23 {
24 printf("%d ",t->data);
25 }
26
27
28 printleaf(t->lchild);
29 printleaf(t->rchild);
30
31 }
3、后序遍历，略
4、整合：
1 #include<stdio.h> 2 #include<stdlib.h> 3 typedef struct treenode 4 { 5 int data; 6 struct treenode *lchild; 7 struct treenode *rchild; 8 }treenode,*tree; 9 tree createTree(int *level,int *in,int left1,int right1,int left2,int right2 ); 10 //core 11 void printleaf(tree t); 12 void preorder(tree t); 13 void postorder(tree t); 14 15 16 int main() 17 { 18 int n;//the number of vertex 19 scanf("%d",&n); 20 21 int level[n],in[n]; 22 int i,j; 23 24 for(i=0;i<n;i++) 25 { 26 scanf("%d",&level[i]); 27 } 28 for(j=0;j<n;j++) 29 { 30 scanf("%d",&in[j]); 31 }//input 32 33 tree t=NULL; 34 int begin1=0,begin2=0; 35 int end1=n-1,end2=n-1; 36 t=createTree(level,in,begin1,end1,begin2,end2); 37 printleaf(t); 38 printf("\n"); 39 preorder(t); 40 printf("\n"); 41 postorder(t); 42 } 43 tree createTree(int *level,int *in,int begin1, int end1,int begin2,int end2) 44 { 45 if(begin2>end2) return NULL; 46 else 47 { 48 treenode *t; 49 t=(treenode*)malloc(sizeof(treenode)); 50 51 int i,j; 52 int flag=0; 53 for(i=begin1;i<=end1;i++) 54 { 55 for(j=begin2;j<=end2;j++) 56 { 57 if(level[i]==in[j]) 58 { 59 flag=1; break; 60 } 61 } 62 if(flag==1) break; 63 } 64 65 t->data=level[i]; 66 t->lchild=createTree(level,in,begin1+1,end1,begin2,j-1); 67 t->rchild=createTree(level,in,begin1+1,end1,j+1,end2); 68 return t; 69 70 71 } 72 73 } 74 75 void printleaf(tree t) 76 { 77 if(!t->lchild&&!t->rchild) 78 { 79 printf("%d ",t->data); 80 } 81 printleaf(t->lchild); 82 printleaf(t->rchild); 83 84 } 85 86 void preorder(tree t) 87 { 88 if(t) 89 { 90 printf("%d ",t->data); 91 preorder(t->lchild); 92 preorder(t->rchild); 93 } 94 } 95 void postorder(tree t) 96 { 97 if(t) 98 { 99 postorder(t->lchild); 100 postorder(t->rchild); 101 printf("%d ",t->data); 102 } 103 }