c9_bst.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
二叉排序树的插入，删除以及查找
BY：wangyucao
第五次上级作业
*/
#include<iostream>
#include<string>
#include<stack>
using namespace std;
struct BiNode{
       int key;
       BiNode* lc;
       BiNode* rc;
       };
typedef BiNode *BiTree;
BiTree Insert(BiTree T,int t)
{
   BiTree node,p;
   node=new BiNode;
   node->key=t;
   node->lc=NULL;
   node->rc=NULL;
   if(T==NULL) return node;
   p=T;
   int c=0;
   while(1)
   {
      if(t<p->key) 
          {if(p->lc==NULL) {c=1;break;}
           p=p->lc;
           }
      else {if(p->rc==NULL){c=2;break;}
           p=p->rc;
           }
   }
   if(c==1) p->lc=node;
   else p->rc=node;
   return T;
}
void display(BiTree T)
{
     if(T== NULL) return;
     display(T->lc);
     cout<<T->key<<' ';
     display(T->rc);
}
BiTree find_node(BiTree T,int k,int mode=0) 
{
   BiTree p;
   if(T==NULL) {cout<<"树为空，查找失败！"<<endl;return T;}
   p=T;
   int c=0;
   if(T->key==k) return T;
   while(p)
   {
      //if(p->key==k) break;
      if(k<p->key) 
          {if(p->lc->key==k) break;
           p=p->lc;
           }
      else {if(p->rc->key==k) {c=1;break;}
           p=p->rc;
           }
   }
   
   if(p==NULL) cout<<"树中没有要查找的结点！"<<endl;
   if(mode==1) return p;
   if(c) return p->rc;
   else return p->lc;
}
BiTree delete_node(BiTree T,int k)
{
   BiTree f,p,pre,q;
   bool isl=true;
   if(T==NULL) {cout<<"树为空，删除失败！"<<endl;return T;}
   p=T;pre=NULL;
   f=find_node(T,k,1);
   if(f==T) {p=T;
            if(!(p->lc||p->rc)) return NULL;
            if(!p->lc) 
            {
                       q=p;
                       T=p->rc;
                       delete q;
            }
            else if(!p->rc) {q=p;T=p->lc; delete q;}
            else{
                 pre=T;
                 p=T->lc;
                 while(!p->rc){ pre=p; p=p->rc;}
                 q=T; f=T->rc; T=T->lc;
                 p->rc=f;
                 delete q;     
                 }                      
            }
   else{
   if(f==NULL) return NULL;
   if(k>=f->key) isl=false;
   if(isl) p=f->lc;
   else p=f->rc;   
   if(!p->rc){
              if(isl){
              q=p; f->lc=p->lc; delete q;
              }
              else{
                    q=p; f->rc=p->lc; delete q;
                    }
              }
   else if(!p->lc){
        if(isl){
              q=p; f->lc=p->rc; delete q;
              }
              else{
                    q=p; f->rc=p->rc; delete q;
                    }
        }
   else{
        q=p;pre=p->lc;f=NULL;
        while(pre->rc) {q=pre;pre=pre->rc;}
        pre->rc=p->lc;
        q=p;
        if(isl) f->lc=p->rc;
        else f->rc=p->rc;
        delete q;
        }
   }
   return T;
}
int main()
{
    BiTree T=NULL,f;
    int *a;
    int i,j,n,k;
    cout<<"请输入二叉排序树的初始结点数："<<endl;
    cin>>n;
    a=(int *)malloc(n*sizeof(int));
    cout<<"请输入"<<n<<"个结点的值：";
    for(i=0;i<n;i++) 
      {cin>>a[i];
       T=Insert(T,a[i]);
      }
    while(1)
    {
        cout<<"功能：\n1.插入结点\n2.查找结点\n3.删除结点\n4.显示当前树的中序遍历序列\n5.退出\n请选择："<<endl;
        cin>>j;
        switch(j){
                  case 1:cout<<"请输入要插入的关键字："<<endl; 
                         cin>>k;
                         Insert(T,k);
                         break;
                  case 2:cout<<"请输入要查找的关键字："<<endl; 
                         cin>>k;
                         f=find_node(T,k);
                         cout<<f->key<<endl;
                         break;
                  case 3:cout<<"请输入要删除的关键字："<<endl; 
                         cin>>k;
                         delete_node(T,k);
                         break;
                  case 4:display(T);
                         cout<<endl;
                         break;
                  case 5:exit(0);
                  default: cout<<"ERROR!!输入错误，请重新输入!!"<<endl;
                  }
                  
    }
    system("PAUSE");
    return 0;
}