二叉查找树

二叉查找树（BST：Binary Search Tree）是一种特殊的二叉树，它改善了二叉树节点查找的效率。二叉查找树有以下性质：

（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值

（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值

（3）左、右子树也分别为二叉排序树

（4）没有键值相等的节点

二叉查找树节点的定义：

1 typedef struct BSTreeNode
2 {
3     int data;
4     struct BSTreeNode *left;//左子树
5     struct BSTreeNode *right;//右子树
6 }BSTree;

跟普通二叉树的节点定义相同

因为查找节点和插入节点都是在已经构建好二叉查找树的前提下才能进行的，在删除节点的时候才涉及到调整二叉树的操作，所以这里先以前序遍历的顺序直接输入一个二叉查找树，代码如下

 1 /* 创建二叉查找树（数据以前序遍历顺序输入）*/
 2 BSTree *Create_BSTreeNode(BSTree *nod)
 3 {
 4     int num;
 5 
 6     scanf_s("%d", &num, 1);
 7     if (num == 0)    /* 假定输入的数据都为正数，以0作为NULL的标志 */
 8     {
 9         return NULL;
10     }
11     else
12     {
13         if ((nod = (BSTree *)malloc(sizeof(BSTree))) == NULL)
14         {
15             printf("内存空间不足");
16             exit(0);
17         }
18         nod->data = num;
19         nod->left = Create_BSTreeNode(nod->left);
20         nod->right = Create_BSTreeNode(nod->right);
21 
22         return nod;
23     }
24 }
25 
26 /* 前序遍历二叉树，并打印 */
27 void PreOrder_Traverse(BSTree *nod, int level)
28 {
29     if (nod == NULL)
30     {
31         return ;
32     }
33 
34     printf("data = %d level = %d
", nod->data, level);
35     PreOrder_Traverse(nod->left, level + 1);
36     PreOrder_Traverse(nod->right, level + 1);
37 }

View Code

1、查找节点（递归实现）

若根结点的关键字等于查找的关键字，查找成功，若小于根结点的关键字的值，递归查找左子树，若大于根结点的关键字的值，递归查找右子树，若子树为空，则查找失败，查找的操作较为简单，实现代码如下

 1 /* 查找特定值 */
 2 void SearchData(int targ, BSTree *nod)
 3 {
 4     if (nod != NULL)
 5     {
 6         if (nod->data == targ)
 7         {
 8             printf("查找值存在，值为%d
", nod->data);
 9         }
10         else if (nod->data > targ)
11         {
12             SearchData(targ, nod->left);    //递归查找左子树
13         }
14         else if (nod->data < targ)
15         {
16             SearchData(targ, nod->right);    //递归查找右子树
17         }
18     }
19     else if (nod == NULL)
20     {
21         printf("查找值不存在
");
22     }
23 }

通过 BST 查找节点，理想情况下我们需要检查的节点数可以减半。如下图中的 BST 树，包含了 15 个节点。从根节点开始执行查找算法，第一次比较决定我们是移向左子树还是右子树，对于任意一种情况，一旦执行这一步，我们需要访问的节点数就减少了一半，从 15 降到了 7。同样，下一步访问的节点也减少了一半，从 7 降到了 3，以此类推，根据这一特点，查找算法的时间复杂度应该是 O(log₂n)

（图片来源：https://www.cnblogs.com/gaochundong/p/binary_search_tree.html）

对于 BST 查找算法来说，其十分依赖于树中节点的拓扑结构，也就是节点间的布局关系，当 BST 树中的节点以扇形结构散开时，对它的插入、删除和查找操作最优的情况下可以达到亚线性的运行时间 O(log₂n)，

因为当在 BST 中查找一个节点时，每一步比较操作后都会将节点的数量减少一半。尽管如此，如果拓扑结构像下图中的样子时，运行时间就会退减到线性时间 O(n)。因为每一步比较操作后还是需要逐个比较其余的节点，

也就是说，在这种情况下，在 BST 中查找节点与在数组（Array）中查找就基本类似了。

因此，BST 算法查找时间依赖于树的拓扑结构。最佳情况是 O(log₂n)，而最坏情况是 O(n)

测试用例：

查找：以前序遍历顺序输入一个二叉查找树（0作为NULL标志）

2、插入节点（递归实现）

新插入的结点一定是一个新添加的叶子结点，如下图

虽然上面两种插入结果得到的二叉树都符合二叉查找树的性质，但是不满足“新插入的结点一定是一个新添加的叶子结点”，因为有了这个特点插入的操作变得相对简单，实现代码如下

 1 /* 添加新节点 */
 2 BSTree *AddNewNode(BSTree *cur, int NewData)
 3 {
 4     if (cur == NULL)
 5     {
 6         if ((cur = (BSTree *)malloc(sizeof(BSTree))) == NULL)    //创建新节点
 7         {
 8             printf("内存不足");
 9             exit(0);
10         }
11         cur->data = NewData;
12         cur->left = NULL;
13         cur->right = NULL;
14 
15         return cur;
16     }
17     if (NewData > cur->data)
18     {
19         cur->right = AddNewNode(cur->right, NewData);
20     }
21     else if (NewData < cur->data)
22     {
23         cur->left = AddNewNode(cur->left, NewData);
24     }
25     else if (NewData == cur->data)
26     {
27         printf("不允许插入重复值
");
28         exit(0);
29     }
30 
31     return cur;
32 }

测试用例：

插入：以前序遍历顺序输入一个二叉查找树

3、删除节点

删除节点的操作相对查找和插入要相对复杂一些，主要考虑以下三种情况（前两种情况操作较为简单，第三种较为复杂）

在删除操作前先用要找到待删除节点的位置（这里使用的递归，也可以改成迭代）

情形一：删除叶子节点

因为删除叶子节点不会破坏BST的结构，删除叶子节点的操作较为简单，步骤如下

1、判断待删除节点的左右子树是否为空，如果都为空那么就是叶子节点

2、判断待删除节点是待删除节点父节点的右子树还是左子树，将对应的指针赋值NULL

3、free待删除节点

实现代码：

 1 /* 删除节点 */
 2 void DeletNode(BSTree *parent, BSTree *cur, int DelData)
 3 {
 4     BSTree *SNode = NULL; //后继节点
 5     BSTree *PSNode = NULL;    //后继节点的父节点
 6 
 7     if (DelData > cur->data)
 8     {
 9         DeletNode(cur, cur->right, DelData);
10     }
11     else if (DelData < cur->data)
12     {
13         DeletNode(cur, cur->left, DelData);
14     }
15     else if(DelData == cur->data)
16     {
17         if (cur->left == NULL && cur->right == NULL)    //删除节点为叶子节点
18         {
19             if (parent->left == cur)    //如果该节点是父节点的左子树
20             {
21                 parent->left = NULL;
22             }
23             else if (parent->right == cur)    //如果该节点是父节点的右子树
24             {
25                 parent->right = NULL;
26             }
27             free(cur);    //释放删除节点
28         }

情形二：删除带有一个子节点的节点

（图片来源：https://www.cnblogs.com/songwenjie/p/8973217.html）

上图写了四种，但对待删除节点来说只有两种，只有左子树，或只有右子树，两种情况的处理方式基本相同，都是将待删除节点的左/右子树赋值给待删除节点的父节点的左/右子树

实现代码：

 1 else if(cur->left != NULL && cur->right == NULL)    //待删除节点只有左子树
 2         {
 3             if (parent->left == cur)
 4             {
 5                 parent->left = cur->left;
 6             }
 7             else if (parent->right == cur)
 8             {
 9                 parent->right = cur->left;
10             }
11             free(cur);    //释放待删除节点
12         }
13         else if(cur->left == NULL && cur->right != NULL)    //待删除节点只有右子树
14         {
15             if (parent->left == cur)
16             {
17                 parent->left = cur->right;
18             }
19             else if (parent->right == cur)
20             {
21                 parent->right = cur->right;
22             }
23             free(cur);    //释放待删除节点
24         }

情形三：删除带两个节点的节点

因为删除节点会有破坏 BST 正确结构的风险，删除带两个节点的节点操作显得较为复杂，首先需要找到待删除节点的 后继节点 和该后继节点的父节点，（一个节点的后继节点是指，这个节点在中序遍历序列中的下一个节点，相应的，前驱节点是指这个节点在中序遍历序列中的上一个节点），删除节点的后继节点一定是删除节点右子树的最左侧节点，这篇随笔采用的方式是后继节点替代待删除节点的方式而不是前驱节点替代删除节点，需要考虑的情况如下

1、后继节点为待删除节点的子节点

在后继节点为待删除节点的子节点的前提下，该后继节点有右子树和没有右子树的操作是相同的，都是将 后继节点 替代 待删除节点，并将待删除节点的左子树 赋值给 后继节点的左子树

实现代码：

 1 else if(cur->left != NULL && cur->right != NULL)    //待删除节点既有左子树也有右子树
 2         {
 3             SNode = SearchSuccessorNode(cur->right);    //搜索后继节点
 4             PSNode = SearchParentofSNode(cur->right, cur->right);    //搜索后继节点的父节点
 5 
 6             if (cur->right == SNode)    //后继节点为待删除节点的右子树（后继节点有右子树和没有右子树的操作相同）
 7             {
 8                 if (parent->left == cur)
 9                 {
10                     parent->left = SNode;
11                     SNode->left = cur->left;
12 
13                     free(cur);
14                 }
15                 else if (parent->right == cur)
16                 {
17                     parent->right = SNode;
18                     SNode->left = cur->left;
19 
20                     free(cur);
21                 }
22             }

2、后继节点不为待删除节点的子节点

这里后继节点还要在分为后继节点有子节点和没有子节点的情况

（1）后继节点没有右子节点

根据实现代码来标注上面的节点

删除后：

实现代码：

 1 else if (cur->right != SNode && SNode->right == NULL)    //后继节点不为待删除节点的右子树，并且该后继节点没有右子树
 2             {
 3                 if (parent->left == cur)
 4                 {
 5                     parent->left = SNode;
 6                     SNode->left = cur->left;
 7                     SNode->right = cur->right;
 8                     PSNode->left = NULL;
 9 
10                     free(cur);
11                 }
12                 else if (parent->right == cur)
13                 {
14                     parent->right = SNode;
15                     SNode->left = cur->left;
16                     SNode->right = cur->right;
17                     PSNode->left = NULL;
18 
19                     free(cur);
20                 }
21             }

（2）后继节点有右子节点

删除后：

与上面的后继节点没有右子节点相比需要增加一个操作，需要将后继节点的右子树 赋值给 后继节点的父节点的左子树

实现代码：

 1 else if (cur->right != SNode && SNode->right != NULL)    //后继节点不为待删除节点的右子树，并且该后继节点有右子树
 2             {
 3                 if (parent->left == cur)
 4                 {
 5                     parent->left = SNode;
 6                     PSNode->left = SNode->right;    //后继节点的右子树作为后继节点父节点的左子树
 7                     SNode->left = cur->left;
 8                     SNode->right = cur->right;
 9 
10                     free(cur);
11                 }
12                 else if (parent->right == cur)
13                 {
14                     parent->right = SNode;
15                     PSNode->left = SNode->right;    //后继节点的右子树作为后继节点父节点的左子树
16                     SNode->left = cur->left;
17                     SNode->right = cur->right;
18 
19                     free(cur);
20                 }
21             }

测试数据：

一、“后继节点是删除节点的子节点”（因为后继节点有无子树的操作相同，这里只测试没有子树的情况）

二、“后继节点不是删除节点的子节点，且后继节点没有右子树”

三、“后继节点不是删除节点的子节点，且后继节点有右子树”

完整代码：（注：对free(cur)的位置进行了调整）

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <conio.h>
  4 
  5 #define LEFT 1
  6 #define RIGHT 2
  7 
  8 typedef struct BSTreeNode
  9 {
 10     int data;
 11     struct BSTreeNode *left;//左子树
 12     struct BSTreeNode *right;//右子树
 13 }BSTree;
 14 
 15 BSTree *Create_BSTreeNode(BSTree *nod);    //创建二叉查找树
 16 void PreOrder_Traverse(BSTree *nod, int level);    //前序遍历二叉树，并打印
 17 void SearchData(int targ, BSTree *nod);    //查找特定值
 18 BSTree *AddNewNode(BSTree *cur, int NewData);    //添加新的节点
 19 void DeletNode(BSTree *parent, BSTree *cur, int DelData);    //删除节点
 20 BSTree *SearchSuccessorNode(BSTree *nod);    //搜索后继节点
 21 BSTree *SearchParentofSNode(BSTree *Pnod, BSTree *nod);    //搜索后继节点的父节点
 22 
 23 int main()
 24 {
 25     BSTree *nod = NULL;
 26     //int num;
 27     //int key;
 28     int del;
 29 
 30     nod = Create_BSTreeNode(nod);
 31     PreOrder_Traverse(nod, 1);
 32     //printf("输出查找数据
");
 33     //scanf_s("%d", &num, 1);
 34     //SearchData(num, nod);
 35     //printf("输出新插入数据
");
 36     //scanf_s("%d", &key, 1);
 37 
 38     printf("输出删除的数据
");
 39     scanf_s("%d", &del, 1);
 40     DeletNode(nod, nod, del);
 41 
 42     //AddNewNode(nod, key);
 43     PreOrder_Traverse(nod, 1);
 44 
 45     return 0;
 46 }
 47 
 48 /* 搜索后继节点的父节点 */
 49 BSTree *SearchParentofSNode(BSTree *Pnod, BSTree *nod)
 50 {
 51     while (1)
 52     {
 53         if (nod->left != NULL)
 54         {
 55             Pnod = nod;
 56             nod = nod->left;
 57         }
 58         else
 59         {
 60             break;
 61         }
 62     }
 63 
 64     return Pnod;
 65 }
 66 
 67 /* 搜索后继节点 */
 68 BSTree *SearchSuccessorNode(BSTree *nod)
 69 {
 70     while (1)
 71     {
 72         if (nod->left != NULL)
 73         {
 74             nod = nod->left;
 75         }
 76         else
 77         {
 78             break;
 79         }
 80     }
 81 
 82     return nod;
 83 }
 84 
 85 /* 删除节点 */
 86 /* cur为待删除节点， parent为待删除节点的父节点 */
 87 void DeletNode(BSTree *parent, BSTree *cur, int DelData)
 88 {
 89     BSTree *SNode = NULL; //后继节点
 90     BSTree *PSNode = NULL;    //后继节点的父节点
 91 
 92     if (DelData > cur->data)
 93     {
 94         DeletNode(cur, cur->right, DelData);
 95     }
 96     else if (DelData < cur->data)
 97     {
 98         DeletNode(cur, cur->left, DelData);
 99     }
100     else if(DelData == cur->data)
101     {
102         if (cur->left == NULL && cur->right == NULL)    //待删除节点为叶子节点
103         {
104             if (parent->left == cur)    //如果该节点是父节点的左子树
105             {
106                 parent->left = NULL;
107             }
108             else if (parent->right == cur)    //如果该节点是父节点的右子树
109             {
110                 parent->right = NULL;
111             }
112         }
113         else if(cur->left != NULL && cur->right == NULL)    //待删除节点只有左子树
114         {
115             if (parent->left == cur)
116             {
117                 parent->left = cur->left;
118             }
119             else if (parent->right == cur)
120             {
121                 parent->right = cur->left;
122             }
123         }
124         else if(cur->left == NULL && cur->right != NULL)    //待删除节点只有右子树
125         {
126             if (parent->left == cur)
127             {
128                 parent->left = cur->right;
129             }
130             else if (parent->right == cur)
131             {
132                 parent->right = cur->right;
133             }
134         }
135         else if(cur->left != NULL && cur->right != NULL)    //待删除节点既有左子树也有右子树
136         {
137             SNode = SearchSuccessorNode(cur->right);    //搜索后继节点
138             PSNode = SearchParentofSNode(cur->right, cur->right);    //搜索后继节点的父节点
139 
140             if (cur->right == SNode)    //后继节点为待删除节点的右子树（后继节点有右子树和没有右子树的操作相同）
141             {
142                 if (parent->left == cur)
143                 {
144                     parent->left = SNode;
145                     SNode->left = cur->left;
146                 }
147                 else if (parent->right == cur)
148                 {
149                     parent->right = SNode;
150                     SNode->left = cur->left;
151                 }
152             }
153             else if (cur->right != SNode && SNode->right == NULL)    //后继节点不为待删除节点的右子树，并且该后继节点没有右子树
154             {
155                 if (parent->left == cur)
156                 {
157                     parent->left = SNode;
158                     SNode->left = cur->left;
159                     SNode->right = cur->right;
160                     PSNode->left = NULL;
161                 }
162                 else if (parent->right == cur)
163                 {
164                     parent->right = SNode;
165                     SNode->left = cur->left;
166                     SNode->right = cur->right;
167                     PSNode->left = NULL;
168                 }
169             }
170             else if (cur->right != SNode && SNode->right != NULL)    //后继节点不为待删除节点的右子树，并且该后继节点有右子树
171             {
172                 if (parent->left == cur)
173                 {
174                     parent->left = SNode;
175                     PSNode->left = SNode->right;    //后继节点的右子树作为后继节点父节点的左子树
176                     SNode->left = cur->left;
177                     SNode->right = cur->right;
178                 }
179                 else if (parent->right == cur)
180                 {
181                     parent->right = SNode;
182                     PSNode->left = SNode->right;    //后继节点的右子树作为后继节点父节点的左子树
183                     SNode->left = cur->left;
184                     SNode->right = cur->right;
185                 }
186             }
187         }
188         free(cur);    //释放待删除节点
189     }
190 }
191 
192 /* 添加新节点 */
193 BSTree *AddNewNode(BSTree *cur, int NewData)
194 {
195     if (cur == NULL)
196     {
197         if ((cur = (BSTree *)malloc(sizeof(BSTree))) == NULL)    //创建新节点
198         {
199             printf("内存不足");
200             exit(0);
201         }
202         cur->data = NewData;
203         cur->left = NULL;
204         cur->right = NULL;
205 
206         return cur;
207     }
208     if (NewData > cur->data)
209     {
210         cur->right = AddNewNode(cur->right, NewData);
211     }
212     else if (NewData < cur->data)
213     {
214         cur->left = AddNewNode(cur->left, NewData);
215     }
216     else if (NewData == cur->data)
217     {
218         printf("不允许插入重复值
");
219         exit(0);
220     }
221 
222     return cur;
223 }
224 
225 /* 查找特定值 */
226 void SearchData(int targ, BSTree *nod)
227 {
228     if (nod != NULL)
229     {
230         if (nod->data == targ)
231         {
232             printf("查找值存在，值为%d
", nod->data);
233         }
234         else if (nod->data > targ)
235         {
236             SearchData(targ, nod->left);    //递归查找左子树
237         }
238         else if (nod->data < targ)
239         {
240             SearchData(targ, nod->right);    //递归查找右子树
241         }
242     }
243     else if (nod == NULL)
244     {
245         printf("查找值不存在
");
246     }
247 }
248 
249 /* 创建二叉查找树（数据以前序遍历顺序输入）*/
250 BSTree *Create_BSTreeNode(BSTree *nod)
251 {
252     int num;
253 
254     scanf_s("%d", &num, 1);
255     if (num == 0)    /* 假定输入的数据都为正数，以0作为NULL的标志 */
256     {
257         return NULL;
258     }
259     else
260     {
261         if ((nod = (BSTree *)malloc(sizeof(BSTree))) == NULL)
262         {
263             printf("内存空间不足");
264             exit(0);
265         }
266         nod->data = num;
267         nod->left = Create_BSTreeNode(nod->left);
268         nod->right = Create_BSTreeNode(nod->right);
269 
270         return nod;
271     }
272 }
273 
274 /* 前序遍历二叉树，并打印 */
275 void PreOrder_Traverse(BSTree *nod, int level)
276 {
277     if (nod == NULL)
278     {
279         return ;
280     }
281 
282     printf("data = %d level = %d
", nod->data, level);
283     PreOrder_Traverse(nod->left, level + 1);
284     PreOrder_Traverse(nod->right, level + 1);
285 }

View Code

因为主要是分析二叉查找树的查找、插入、删除操作，没有考虑二叉树为空或待删除节点为根节点的情况