先序+中序/中序+后序/先序+后序 构造二叉树

 1 #include<iostream>
 2 using namespace std;
 3 
 4 typedef struct BiTNode{
 5     int data;
 6     struct BiTNode *lChild,*rChild;
 7 }BiTNode,*BiTree;
 8 
 9 bool preAndInCreate(BiTree &T,int pre[],int in[],int length){
10     if(length<=0){
11         T=NULL;
12     }else{
13         int i;
14         T=new BiTNode; 
15         T->data=pre[0];
16         for(i=0;i<length&&in[i]!=pre[0];++i);
17         if(i>length) return false;
18         preAndInCreate(T->lChild,pre+1,in,i);
19         preAndInCreate(T->rChild,pre+i+1,in+i+1,length-1-i);
20     }
21     return true;
22 }
23 
24 bool deleteTree(BiTree &T){
25     if(T){
26         BiTree L=T->lChild;
27         BiTree R=T->rChild;
28         delete T;
29         T=NULL;
30         deleteTree(L);
31         deleteTree(R);
32     }
33 }
34 
35 bool postTraverse(const BiTree &T){
36     if(T){
37         if(postTraverse(T->lChild))
38             if(postTraverse(T->rChild)){
39                 cout<<T->data<<" ";
40                 return true;
41             }
42         return false;
43     }
44     return true;
45 }
46 
47 int main(){
48     int n;
49     cout<<"Input the number of nodes : ";
50     cin>>n;
51     cout<<"Input preorder tree : ";
52     int pre[n],in[n];
53     for(int i=0;i<n;++i) cin>>pre[i];
54     cout<<"Input inorder tree : ";
55     for(int i=0;i<n;++i) cin>>in[i];
56     BiTree T=NULL;
57     preAndInCreate(T,pre,in,n);
58     cout<<"\nthe tree in postorder : ";
59     postTraverse(T);
60     deleteTree(T);
61 }

 1 #include<iostream>
 2 using namespace std;
 3 
 4 typedef struct BiTNode{
 5     int data;
 6     struct BiTNode *lChild,*rChild;
 7 }BiTNode,*BiTree;
 8 
 9 bool InAndPostCreate(BiTree &T,int in[],int post[],int length){
10     if(length<=0){
11         T=NULL;
12     }else{
13         int i;
14         T=new BiTNode; 
15         T->data=post[length-1];
16         for(i=0;i<length&&in[i]!=post[length-1];++i);
17         if(i>length) return false;
18         InAndPostCreate(T->lChild,in,post,i);
19         InAndPostCreate(T->rChild,in+i+1,post+i,length-1-i);
20     }
21     return true;
22 }
23 
24 bool deleteTree(BiTree &T){
25     if(T){
26         BiTree L=T->lChild;
27         BiTree R=T->rChild;
28         delete T;
29         T=NULL;
30         deleteTree(L);
31         deleteTree(R);
32     }
33 }
34 
35 bool preTraverse(const BiTree &T){
36     if(T){
37         cout<<T->data<<" ";
38         preTraverse(T->lChild);
39         preTraverse(T->rChild);
40     }
41     return true;
42 }
43 
44 int main(){
45     int n;
46     cout<<"Input the number of nodes : ";
47     cin>>n;
48     int post[n],in[n];
49     cout<<"Input inorder tree : ";
50     for(int i=0;i<n;++i) cin>>in[i];
51     cout<<"Input postorder tree : ";
52     for(int i=0;i<n;++i) cin>>post[i];
53     BiTree T=NULL;
54     InAndPostCreate(T,in,post,n);
55     cout<<"\nthe tree in preorder : ";
56     preTraverse(T);
57     deleteTree(T);
58 }

 1 #include<iostream>
 2 using namespace std;
 3 
 4 typedef struct BiTNode{
 5     int data;
 6     struct BiTNode *lChild,*rChild;
 7 }BiTNode,*BiTree;
 8 
 9 bool preAndPostCreate(BiTree &T,int pre[],int post[],int length){//用 传指针或者传新数组（其实传指针相当于传新数组） 而不用 传下标数字以及原数组 真的简化了很多，省了很多关于下标的麻烦。
10     if(length<=0){
11         T=NULL;
12     }else if(length==1){
13         T=new BiTNode;
14         T->data=pre[0];
15         preAndPostCreate(T->lChild,NULL,NULL,0);
16         preAndPostCreate(T->rChild,NULL,NULL,0);
17     }else{ 
18         int i;
19         T=new BiTNode;
20         T->data=pre[0];
21         for(i=0;i<length&&post[i]!=pre[1];++i);
22         preAndPostCreate(T->lChild,pre+1,post,i+1);
23         preAndPostCreate(T->rChild,pre+2+i,post+i+1,length-2-i);
24     }
25     return true;
26 }
27 
28 bool deleteTree(BiTree &T){
29     if(T){
30         BiTree L=T->lChild;
31         BiTree R=T->rChild;
32         delete T;
33         T=NULL;
34         deleteTree(L);
35         deleteTree(R);
36     }
37 }
38 
39 bool inTraverse(const BiTree &T){
40     if(T){
41         inTraverse(T->lChild);
42         cout<<T->data<<" ";
43         inTraverse(T->rChild);
44     }
45     return true;
46 }
47 
48 int main(){
49     int n;
50     cout<<"Input the number of nodes : ";
51     cin>>n;
52     cout<<"Input preorder tree : ";
53     int pre[n],post[n];
54     for(int i=0;i<n;++i) cin>>pre[i];
55     cout<<"Input postorder tree : ";
56     for(int i=0;i<n;++i) cin>>post[i];
57     BiTree T=NULL;
58     if(!preAndPostCreate(T,pre,post,n)){
59         cout<<"fail"<<endl;
60     }else{
61         cout<<"\nthe tree in inorder : ";
62         inTraverse(T);    
63     }
64     deleteTree(T);
65 }