BST的逐层遍历

 2008-10-02 13:26


#include<iostream>
using namespace std;
struct node{
       int data;
       node* leftchild;
       node* rightchild;
};
struct member{
       node* data;
       member* next;
};
class Queue{
      public:
      void EnQueue(node* n);
      void DeQueue();
      node* GetHead();
      bool Is_empty();
      Queue();
      private:
      member *front,*rear;
};
class BST{
      public:
      BST();
      void Insert(int i);
      void Order();
      private:
      node* root;
      void Insert(node* &n,int i);
};
int main(void){
    BST a;
    int n;
   
    cin>>n;
    while(n!=-1){
          a.Insert(n);
          cin>>n;
     }
   
    a.Order();
    system("pause");
   
    return 0;
}
Queue::Queue(){
       front = rear = 0;
}
void Queue::EnQueue(node* n){
     if(!front){
        front = new member;
        front->data = n;
        front->next = 0;
        rear = front;
        return;
     }
     member* newr = new member;
     newr->data = n;
     newr->next = 0;
     rear->next = newr;
     rear = newr;
}
node* Queue::GetHead(){
      if(!front){
          cout<<"Queue Empty!";
          system("pause");
          exit(0);
      }
      return front->data;
}
void Queue::DeQueue(){
     if(!front){
          cout<<"Queue Empty!";
          system("pause");
          exit(0);
     }
     if(front==rear){
        delete front;
        front = 0;
        return;
     }
     member* p = front;
     front = front->next;
     delete p;
}
    
bool Queue::Is_empty(){
     return front==0;
}
             
BST::BST(){
     root = 0;
}
void BST::Insert(node* &n,int i){
     if(!n){
        n = new node;
        n->data = i;
        n->leftchild = n->rightchild = 0;
        return;
     }
     if(n->data>=i) Insert(n->leftchild,i);
     else Insert(n->rightchild,i);
}
void BST::Insert(int i){
     Insert(root,i);
}
void BST::Order(){
     node* p = root;
     Queue q;
     q.EnQueue(p);
     while(!q.Is_empty()){
           p = q.GetHead();
           q.DeQueue();
           cout<<p->data<<" ";
           if(p->leftchild) q.EnQueue(p->leftchild);
           if(p->rightchild) q.EnQueue(p->rightchild);
     }
     cout<<endl;
}