二叉排序树

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 #define TRUE 1
  5 #define FALSE 0
  6 #define ElemType int
  7 #define KeyType int
  8 
  9 
 10 /* 二叉排序树的节点结构定义 */
 11 typedef struct BiTNode
 12 {
 13     ElemType data;
 14     struct BiTNode *lchild, *rchild;
 15 } BiTNode, *BiTree;
 16 
 17 
 18 /*二叉排序树查找算法*/
 19 int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p)
 20 {
 21     //如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点，并返回查找失败的信息
 22     if(!T)
 23     {
 24         *p = f;
 25         return FALSE;
 26     }
 27     //如果相等，令 p 指针指向该关键字，并返回查找成功信息
 28     else if (key == T->data)
 29     {
 30         *p = T;
 31         return TRUE;
 32     }
 33     //如果 key 值比 T 根结点的值小，则查找其左子树
 34     else if (key < T->data)
 35     {
 36         return SearchBST(T->lchild, key, T, p);
 37     }
 38     //如果 key 值比 T 根结点的值大，则查找其右子树
 39     else
 40     {
 41         return SearchBST(T->rchild, key, T, p);
 42     }
 43 }
 44 
 45 
 46 int InsertBST(BiTree *T, ElemType e)
 47 {
 48     BiTree p = NULL;
 49     //如果查找不成功，需做插入操作
 50     if (!SearchBST((*T), e, NULL, &p))
 51     {
 52         //初始化插入结点
 53         BiTree s = (BiTree)malloc(sizeof(BiTNode));
 54         s->data = e;
 55         s->lchild = s->rchild = NULL;
 56 
 57         //如果 p 为NULL，说明该二叉排序树为空树，此时插入的结点为整棵树的根结点
 58         if (!p)
 59         {
 60             *T = s;
 61         }
 62 
 63         //如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子
 64         else if (e < p->data)
 65         {
 66             p->lchild = s;
 67         }
 68         else
 69         {
 70             p->rchild = s;
 71         }
 72 
 73         return TRUE;
 74     }
 75 
 76     //如果查找成功，不需要做插入操作，插入失败
 77     return FALSE;
 78 }
 79 
 80 //删除函数
 81 int Delete(BiTree *p)
 82 {
 83     BiTree q, s;
 84     //情况 1，结点 p 本身为叶子结点，直接删除即可
 85     if (!(*p)->lchild && !(*p)->rchild)
 86     {
 87         *p = NULL;
 88     }
 89 
 90     else if (!(*p)->lchild)   //左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可；
 91     {
 92         q = *p;
 93         *p = (*p)->rchild;
 94         free(q);
 95     }
 96 
 97     else if (!(*p)->rchild)  //右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可；
 98     {
 99         q = *p;
100         *p = (*p)->lchild;//这里不是指针 *p 指向左子树，而是将左子树存储的结点的地址赋值给指针变量 p
101         free(q);
102     }
103 
104     else  //左右子树均不为空，采用直接前驱来代替需要删除的结点
105     {
106         q = *p;
107         s = (*p)->lchild;
108         //遍历，找到结点 p 的直接前驱
109         while (s->rchild)
110         {
111             q = s;
112             s = s->rchild;
113         }
114 
115         //直接改变结点 p 的值
116         (*p)->data = s->data;
117 
118         //判断结点 p 的左子树 s 是否有右子树，分为两种情况讨论
119         if (q != *p)
120         {
121             q->rchild = s->lchild;//若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点
122         }
123         else
124         {
125             q->lchild = s->lchild;//否则，直接将左子树上移即可
126         }
127         free(s);
128     }
129     return TRUE;
130 }
131 
132 int DeleteBST(BiTree *T, int key)
133 {
134     if (!(*T))  //不存在关键字等于key的数据元素
135     {
136         return FALSE;
137     }
138     else
139     {
140         if (key == (*T)->data)
141         {
142             Delete(T);
143             return TRUE;
144         }
145         else if (key < (*T)->data)
146         {
147             //使用递归的方式
148             return DeleteBST(&(*T)->lchild, key);
149         }
150         else
151         {
152             return DeleteBST(&(*T)->rchild, key);
153         }
154     }
155 }
156 
157 
158 void order(BiTree t)//中序输出
159 {
160     if (t == NULL)
161     {
162         return;
163     }
164     order(t->lchild);
165     printf("%d ", t->data);
166     order(t->rchild);
167 }
168 
169 
170 int main()
171 {
172     while(1)
173     {
174         BiTree T = NULL;
175 
176         printf("你想在无序序列中输入几个元素用来构建一棵二叉排序树？\n");
177         int n;
178         scanf("%d", &n);
179 
180         //创建二叉排序数
181         for(int i=0; i<n ; i++)
182         {
183             printf("请输入这个无序序列中的元素：");
184             int x;
185             scanf("%d", &x);
186             InsertBST(&T, x);
187         }
188 
189         //中序输出二叉排序树
190         printf("中序遍历二叉排序树：\n");
191         order(T);
192         printf("\n");
193 
194         //删除操作
195         printf("请输入您想要删除的元素：\n");
196         int x1;
197         scanf("%d", &x1);
198         DeleteBST(&T, x1);
199         if(DeleteBST(&T, x1))
200         {
201             printf("删除3后，中序遍历二叉排序树：\n");
202             order(T);
203             printf("\n");
204         }
205         else
206         {
207             printf("请输入正确的关键字!\n");
208         }
209         printf("-------------------------------------\n");
210     }
211     return 0;
212 }