BST的用栈实现的非递归版中序遍历

2008-10-02 11:33



#include<iostream>
using namespace std;

struct node{
       int data;
       node* leftchild;
       node* rightchild;
   };
 
class Stack{
      public:
      Stack();
      void Push(node* n);
      void Pop();
      node* GetTop();
      bool Is_empty();
      private:
      node* data[100];
      int top;
};

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;
}

Stack::Stack(){
       top = -1;
}

void Stack::Push(node* n){
     if(top==-1){
        data[0] = n;
        top = 0;
        return;
     }
     if(top+1>=100){
        cout<<"Stack full!";
        system("pause");
        exit(0);
     }
     top++;
     data[top] = n;
}

void Stack::Pop(){
     if(top==-1){
         cout<<"Stack empty!";
         system("pause");
         exit(0);
     }
     top--;
}

node* Stack::GetTop(){
      if(top==-1){
         cout<<"Stack empty!";
         system("pause");
         exit(0);
      }
      return data[top];
}
    
bool Stack::Is_empty(){ return top==-1; }
     
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(){
     Stack st;
     node* p = root;
     do{
           while(p){
                 st.Push(p);
                 p = p->leftchild;
           }
           if(!st.Is_empty()){
              p = st.GetTop();
              st.Pop();
              cout<<p->data<<" ";
              p = p->rightchild;
          }
     }while(!st.Is_empty()||p);//若遍历完左子树和根时st.Is_empty()==true,

                               //而此时还没有遍历完，故要加上||p

}