当前位置：首页 > news >正文

二叉排序树

news 来源：原创 2024/5/2 17:21:32

实现二叉排序树的搜索，插入，删除。

代码如下：

  1 //#define int ElemType
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4  
  5 //#define int KeyType
  6 typedef struct BiTNode{
  7     int data;
  8     struct BiTNode *lchild,*rchild;
  9 }BiTNode,*BiTree;
 10 bool SearchBST(BiTree T,int key,BiTree f,BiTree &p)
 11 {
 12   if(!T)
 13   {
 14       p=f;
 15       return false;
 16   }
 17   else
 18       if(key==T->data)
 19       {
 20           p=T;
 21           return true;//查找成功
 22       }
 23       else
 24           if(key<T->data)
 25               return SearchBST(T->lchild,key,T,p);//继续在左子树中查找
 26           else
 27               return SearchBST(T->rchild,key,T,p);//继续在右子树中查找
 28 }
 29 void InsertBST(BiTree &T,int e)
 30 {
 31     BiTree p,s;
 32     if(!SearchBST(T,e,NULL,p))
 33     {
 34         s=(BiTree)malloc(sizeof(BiTNode));
 35         s->data=e;
 36         s->lchild=s->rchild=NULL;
 37         if(!p)
 38             T=s;//被插结点*s为新的根节点
 39         else
 40             if(e<p->data)
 41                 p->lchild=s;//被插入结点*s为左孩子
 42             else
 43                 p->rchild=s;//被插结点*s为右孩子
 44 
 45     }
 46     else
 47         printf("已有相同数据，请重新插入");    
 48 }
 49 void Delete(BiTree &p)
 50 {
 51     BiTree q,s;
 52     if(!p->rchild)
 53     {
 54       q=p;
 55       p=p->lchild;
 56       free(q);
 57     }
 58     else
 59         if(!p->lchild)
 60         {
 61             q=p;
 62             p=p->rchild;
 63             free(q);
 64         }
 65         else//左右子树均不为空的情况
 66         {
 67             q=p;
 68             s=p->lchild;
 69             while(s->rchild)
 70             {
 71                 q=s;
 72                 s=s->rchild;
 73             }
 74             p->data=s->data;
 75             if(q!=p)
 76                 q->rchild=s->lchild;
 77             else
 78                 q->lchild=s->rchild;
 79             delete s;
 80         }
 81 }
 82 void DeleteBST(BiTree &T,int key)
 83 {
 84     if(!T)
 85         printf("不存在关键字等于key的数据元素");
 86     else
 87     {
 88         if(key==T->data)
 89             Delete(T);
 90         else
 91             if(key<T->data)
 92                 DeleteBST(T->lchild,key);
 93             else
 94                 DeleteBST(T->rchild,key);
 95     }
 96 }
 97 
 98 //中序遍历二叉树
 99 void Midorder(BiTree bt)
100 {
101     if(bt)
102     {
103         Midorder(bt->lchild);
104         printf("%d",bt->data);
105         Midorder(bt->rchild);
106     }
107 }
108 int main()
109 {
110     BiTree bt;
111     bt=(BiTNode*)malloc(sizeof(BiTNode));
112     bt->data=1;
113     bt->lchild=NULL;
114     bt->rchild=NULL;
115     InsertBST(bt,2);
116     InsertBST(bt,3);
117     InsertBST(bt,4);
118     DeleteBST(bt,1);
119     Midorder(bt);
120     return 0;
121 }