1 #include <iostream>  2 #include <queue>  3 #include <cstdio>  4 using namespace std;  5 typedef char ElemTp;  6 typedef struct Bittree  7 {  8     ElemTp data;  9     struct Bittree *l,*r; 10 }*BitLink,BitNode; 11 BitLink CrtTree() 12 { 13     ElemTp t; 14     t=getchar(); 15     if(t==‘#‘) return NULL; 16     BitLink tree=new BitNode; 17     tree->data=http://www.mamicode.com/t; 18     tree->l=CrtTree(),tree->r=CrtTree(); 19     return tree; 20 } 21 void FreeTree(BitLink tree) 22 { 23     if(!tree) return ; 24     if(!tree->l&&!tree->r) 25     { 26         delete tree; 27         return ; 28     } 29     FreeTree(tree->l); 30     FreeTree(tree->r); 31     delete tree; 32 } 33  34 void DLR(BitLink tree) 35 { 36     if(!tree) return ; 37     cout<<tree->data<<" "; 38     DLR(tree->l); 39     DLR(tree->r); 40 } 41 void LDR(BitLink tree) 42 { 43     if(!tree) return ; 44     LDR(tree->l); 45     cout<<tree->data<<" "; 46     LDR(tree->r); 47 } 48 void LRD(BitLink tree) 49 { 50     if(!tree) return ; 51     LRD(tree->l); 52     LRD(tree->r); 53     cout<<tree->data<<" "; 54 } 55  56  57 void layertrave(BitLink tree) 58 { 59     if(!tree) return ; 60     queue<BitLink> Queue; 61     Queue.push(tree); 62     while(!Queue.empty()) 63     { 64         tree=Queue.front(); 65         Queue.pop(); 66         cout<<tree->data<<" "; 67         if(tree->l) Queue.push(tree->l); 68         if(tree->r) Queue.push(tree->r); 69     } 70 } 71 BitLink CrtTree(char *a,int &i,char *b,int u,int v) 72 { 73     /// CrtTree(a,0,b,0,strlen(b)-1); 74     BitLink tree; 75     int k; 76     if(u>v) return NULL; 77     tree=new BitNode; 78     tree->data=http://www.mamicode.com/a[i++]; 79     for( k=u;k<=v;k++) 80         if(b[k]==tree->data) break; 81     tree->l=CrtTree(a,i,b,u,k-1); 82     tree->r=CrtTree(a,i,b,k+1,v); 83     return tree; 84 } 85 int main() 86 { 87     //-+a##*b##-c##d##/e##f##//a+b*(c-d)-e/f 88     BitLink tree=CrtTree(); 89     cout<<"DLR:"; 90     DLR(tree); 91     cout<<endl; 92  93     cout<<"LDR:"; 94     LDR(tree); 95     cout<<endl; 96  97     cout<<"LRD:"; 98     LRD(tree); 99     cout<<endl;100 101     cout<<"LayerTravel:";102     layertrave(tree);103     cout<<endl;104 105     char a[100],b[100];106     cout<<"please input DLR:";107     cin>>a;108     cout<<"please input LDR:";109     cin>>b;110     int i=0;111     BitLink tree2=CrtTree(a,i,b,0,strlen(b)-1);112     cout<<"LayerTravel:"<<endl;113     layertrave(tree2);114     cout<<endl;115 116     cout<<"LRD:"<<endl;117     LRD(tree2);118 119     FreeTree(tree);120     FreeTree(tree2);121     return 0;122 }