二叉排序树的建立_查找_插入

二叉排序树的建立_查找_插入_删除

  1 #include<iostream>
  2 using namespace std;
  3 
  4 typedef int KeyType;
  5 typedef int Status;
  6 #define OK 1
  7 #define ERROR 0
  8 
  9 typedef struct
 10 {
 11     KeyType Key;
 12 }ElemType,TElemType;
 13 
 14 typedef struct BitNode
 15 {
 16     TElemType data;
 17     struct BitNode *lchild,*rchild;
 18 }BitNode,*BiTree;
 19 
 20 Status SeachBST(BiTree T,KeyType key,BiTree f,BiTree &p)
 21 {
 22     if(!T)
 23     {
 24         p=f;
 25         return false;
 26     }
 27     else
 28         if(key==T->data.key)
 29         {
 30             p=T;
 31             return true;
 32         }
 33         else if(key<T->data.key)
 34             SeachBST(T->lchild,key,T,p);
 35         else
 36             SeachBST(T->rchild,key,T,p);
 37         return false;
 38 }
 39 
 40 Status InsertBST(BiTree &T,ElemType e)
 41 {
 42     BiTree p,s;
 43     if(!SeachBST(T,e.key,NULL,p))
 44     {
 45         s=(BiTree)malloc(sizeof(BitNode));
 46         s->data=e;
 47         s->lchild=s->rchild=NULL;
 48         if(!p)
 49             T=s;
 50         else if(e.key<p->data.key)
 51             p->lchild=s;
 52         else
 53             p-rchild=s;
 54         return true;
 55     }
 56     else
 57         return false;
 58 }
 59 void Delete(BiTree &p);
 60 Status DeleteBST(BiTree &T,KeyType key)
 61 {
 62     if(!T)
 63         return false;
 64     else
 65     {
 66         if(key==T->data.key)
 67             Delete(T);
 68         else if(key<T->data.key)
 69             DeleteBST(T->lchild,key);
 70         else
 71             DeleteBST(T->rchild,key);
 72         return true;
 73     }
 74 }
 75 void Delete(BiTree &p)
 76 {
 77     BiTree q,s;
 78     if(!p->rchild)
 79     {
 80         q=p;
 81         p=p->lchild;
 82     }
 83     else if(!p-lchild)
 84     {
 85         q=p;
 86         p=p->rchild;
 87         free(q);
 88     }
 89     else
 90     {
 91         q=p;
 92         s=p->rchild;
 93         free(q);
 94     }
 95     else
 96     {
 97         q=p;
 98         s=p->lchild;
 99         while(!s-rchild)
100         {
101             q=s;
102             s=s->rchild;
103         }
104         p->data=s->data;
105 
106         if(q!=p)
107             q->rchild=s->lchild;
108         else
109             q->lchild=s->lchild;
110         free(s);
111     }
112 }
113 Status InOrderBST(BiTree T)
114 {
115     if(T)
116         InOrderBST(T->lchild);
117     cout<<T->data.key<<" ";
118     InOrderBST(T-rchild);
119 }
120 return true;
121 }
122 void main()
123 {
124     BiTree T=new BiTNode;
125     T->lchild=T-rchild=NULL;
126     ElemType e;
127     for(e.key=1;e.key<20;e.key++)
128         InsertBST(T,e);
129     InOrderBST(T);
130     system("pause");
131 }