生成二叉排序树

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef int ElemType;
  4 
  5 typedef struct Node{
  6     ElemType data;
  7     Node* lson;
  8     Node* rson;
  9 }*Tree;
 10 
 11 void preorder1(Tree T){
 12     if(T){
 13         printf("%d ",T->data);
 14         preorder1(T->lson);
 15         preorder1(T->rson);
 16     }
 17 }
 18 
 19 void inorder1(Tree T){
 20     if(T){
 21         inorder1(T->lson);
 22         printf("%d ",T->data);
 23         inorder1(T->rson);
 24     }
 25 }
 26 void preorder(Tree T){
 27     stack<Tree>s;
 28     while(T||!s.empty()){
 29         if(T){
 30             printf("%d ",T->data);
 31             s.push(T);
 32             T=T->lson;
 33         }
 34         else{
 35             T=s.top();
 36             s.pop();
 37             T=T->rson;
 38         }
 39     }
 40 }
 41 
 42 void inorder(Tree T){
 43     stack<Tree>s;
 44     while(T||!s.empty()){
 45         if(T){
 46             s.push(T);
 47             T=T->lson;
 48         }
 49         else{
 50             T=s.top();
 51             printf("%d ",T->data);
 52             s.pop();
 53             T=T->rson;
 54         }
 55     }
 56 }
 57 
 58 void postorder(Tree T){
 59     stack<Tree>s;
 60     Tree p=T,r=NULL;
 61     while(p||!s.empty()){
 62 
 63         if(p){
 64             //printf("%d ",p->data);
 65             s.push(p);
 66             p=p->lson;
 67         }
 68         else{
 69             p=s.top();
 70             if(p&&p->rson==r){
 71                 printf("%d ",p->data);
 72                 s.pop();
 73                 r=p;
 74                 p=NULL;
 75             }
 76             else if(p){
 77                 p=p->rson;
 78                 r=NULL;
 79             }
 80             
 81         }
 82     }
 83 }
 84 
 85 bool add(Tree &T,Tree pre,int x){
 86     if(!T){
 87         Node *p=new Node;
 88         p->data=x;
 89         p->lson=p->rson=NULL;
 90         if(x<pre->data)pre->lson=p;
 91         else pre->rson=p;
 92     }
 93     if(x<T->data){
 94         add(T->lson,T,x);
 95     }
 96     else if(x==T->data)return false;
 97     else{
 98         add(T->rson,T,x);
 99     }
100 }
101 
102 Tree solve(int L[],int n){
103     Tree T=new Node;
104     T->data=L[0];
105     T->lson=T->rson=NULL;
106     for(int i=1;i<n;i++){
107         add(T,T,L[i]);
108     }
109     return T;
110 }
111 
112 
113 int main(){
114     /*Node* v7 = new Node(7, NULL, NULL);
115     Node* v1 = new Node(1, NULL, NULL);
116     Node* v3 = new Node(3, NULL, NULL);
117     Node* v2 = new Node(2, v1, v3);
118     Node* v5 = new Node(5, NULL, NULL);
119     Node* v6 = new Node(6, v5, v7);
120     Node* v4 = new Node(4, v2, v6);
121     Tre*/
122     int L[10]={4,2,6,1,3,5,7};
123     Tree T=solve(L,7);
124     preorder(T);
125     printf("
");
126     inorder(T);
127     printf("
");
128     postorder(T);
129 }