功能比较完整的BST

  2009-03-22 11:31



//key code

struct Node{
       int key;
       Node *p,*left,*right;
       Node(){
           p = left = right = 0;
       }
};

class BST{
      public:
         BST();
         Node* TreeSearch(int key);
         Node* TreeMax(Node* x);
         Node* TreeMin(Node* x);
         Node* TreeSuc(Node* x);
         Node* TreePre(Node* x);
         void TreeInsert(int key);
         Node* TreeDel(Node* x);
         void MidOrder();
         void PreOrder();
      private:
         void MidOrder(Node* cur);
         void PreOrder(Node* cur);
         Node* Root;
};

BST::BST(){
     Root = 0;
}

Node* BST::TreeSearch(int key){
      if(Root==0) return 0;
      Node* t = Root;
      while(t){
           if(t->key==key) break;
           if(t->key>=key) t = t->left;
           else t = t->right;
      }
      return t;
}

Node* BST::TreeMax(Node* x){
      while(x->right) x = x->right;
      return x;
}
Node* BST::TreeMin(Node* x){
      while(x->left) x = x->left;
      return x;
}

Node* BST::TreeSuc(Node* x){
      if(x->right) return TreeMin(x->right);
      Node* y = x->p;
      while(y){
           if(x == y->left) break;
           x = y;
           y = y->p;
      }
      return y;
}
Node* BST::TreePre(Node* x){
      if(x->left) return TreeMax(x->left);
      Node* y = x->p;
      while(y){
           if(x == y->right) break;
           x = y;
           y = y->p;
      }
      return y;
}

void BST::TreeInsert(int key){
     if(Root==0){
        Root = new Node;
        Root->key = key;
        return;
     }
     Node* x;
     Node* t = Root;
     Node* p;
     x = new Node;
     x->key = key;
     while(t){
          p = t;
          if(x->key<=t->key) t = t->left;
          else t = t->right;
     }
     if(p->key>=x->key){
        p->left = x;
        x->p = p;
     }
     else{
         p->right = x;
         x->p = p;
     }
}

Node* BST::TreeDel(Node* x){
      Node *y,*z;
      if(x->left==0||x->right==0)
         y = x;
      else y = TreeSuc(x);
      if(y->right)
         z = y->right;
      else if(y->left) z = y->left;
      else z = 0;
      if(z!=0)
         z->p = y->p;
      if(y->p==0) Root = z;
      else if(y==y->p->left) y->p->left = z;
      else y->p->right = z;
      x->key = y->key;
      return y;
}

void BST::MidOrder(){
     if(Root==0) return;
     MidOrder(Root);
}
void BST::PreOrder(){
     if(Root==0) return;
     PreOrder(Root);
}

void BST::MidOrder(Node* cur){
     if(cur==0) return;
     MidOrder(cur->left);
     cout<<cur->key<<" ";
     MidOrder(cur->right);
}
void BST::PreOrder(Node* cur){
     if(cur==0) return;
     cout<<cur->key<<" ";
     PreOrder(cur->left);
     PreOrder(cur->right);
}
//key code