简易BST实现

BST，即二叉搜索树，该数据结构规定任意若一个结点存在左子树，那么该结点键必须要大于左子树上所有键；若有右子树，那么该结点键必须要小于右子树上所有键
简单的BST是树形查找里的入门级数据结构，不涉及平衡性调节，只需要简单插入删除，即可，其中删除稍复杂，但是也不难，只需要把三种情况分清即可。简单的BST因为不存在平衡调节，所以针对某些特定序列(如已排序序列依次插入)在构造好BST后，事实上退化为链表，这样搜索效率大幅下降到O(n)
今天先贴个简单BST实现，改天再贴个AVL树的实现

1. typedef struct BSTnode {
2.     struct BSTnode *left, *right;
3.     int data;
4. }BSTnode, *BST;
6. //simple BST
7. BST batch_create_BST(int a[], int n);
8. void destroy_BST(BST &T);
9. bool insert_BST(BST &T, int e);
10. bool delete_BST(BST &T, int e);
11. bool find_BST(BST &T, int e);
13. BST batch_create_BST(int a[], int n)
14. {
15.     BST T = nullptr;
16.     for (int i = 0; i < n; ++i)
17.         insert_BST(T, a[i]);
18.     return T;
19. }
21. void destroy_BST(BST &T)
22. {
23.     if (!T)
24.         return;
25.     destroy_BST(T->left);
26.     destroy_BST(T->right);
27.     free(T);
28.     T = nullptr;
29. }
31. bool insert_BST(BST &T, int e)
32. {
33.     if (!T)
34.     {
35.         T = (BSTnode *)malloc(sizeof(BSTnode));
36.         T->data = e;
37.         T->left = T->right = nullptr;
38.         return true;
39.     }
40.     if (e > T->data)
41.         return insert_BST(T->right, e);
42.     else if (e < T->data)
43.         return insert_BST(T->left, e);
44.     return false;
45. }
47. bool delete_BST(BST &T, int e)
48. {
49.     if (!T) // 空树删除失败
50.         return false;
51.     if (T->data == e) // 特殊处理根节点删除
52.     {
53.         if (T->left && T->right) // 根有左右子树
54.         {
55.             BSTnode *p = T, *q = T->left;
56.             while (q->right) // 找到根节点的前驱以及前驱的父结点
57.             {
58.                 p = q;
59.                 q = q->right;
60.             }
61.             T->data = q->data; // 覆盖根的元素
62.             // 以下删除q
63.             if (p->left == q)
64.                 p->left = q->left != nullptr ? q->left : q->right; // 这里可以处理叶节点情况
65.             else
66.                 p->right = q->left != nullptr ? q->left : q->right; // 同上
67.             free(q);
68.             q = nullptr;
69.         }
70.         else // 仅有左或右子树以及叶结点情况
71.         {
72.             BSTnode *del = T;
73.             T = T->left != nullptr ? T->left : T->right; // 事实上这里也能处理单节点情况
74.             free(del);
75.             del = nullptr;
76.         }
77.     }
78.     else // 删除内部结点
79.     {
80.         BSTnode *p = nullptr, *q = T;
81.         while (q && q->data != e) // 查找待删除结点及其父结点
82.         {
83.             p = q;
84.             q = q->data > e ? q->left : q->right;
85.         }
86.         if (!q) // 没有这个结点删除失败
87.             return false;
88.         if (q->left && q->right) // 具有左右子树的结点删除
89.         {
90.             BSTnode *pre = q, *del = q->left;
91.             while (del->right) // 寻找待删除结点的中序直接前驱以及这个前驱的父结点
92.             {
93.                 pre = del;
94.                 del = del->right;
95.             }
96.             q->data = del->data; // 前驱直接覆盖原本待删除结点
97.             // 以下删除del
98.             if (pre->left == del)
99.                 pre->left = del->left != nullptr ? del->left : del->right; // 可以处理叶结点情况
100.             else
101.                 pre->right = del->left != nullptr ? del->left : del->right;
102.             ; // 同上
103.             free(del);
104.             del = nullptr;
105.         }
106.         else    // 仅有单子树的结点或叶结点删除
107.         {
108.             if (p->left == q)
109.                 p->left = q->left != nullptr ? q->left : q->right; // 根据这里可以将前面的叶结点删除作优化掉
110.             else
111.                 p->right = q->left != nullptr ? q->left : q->right; // 同上
112.             free(q);
113.             q = nullptr;
114.         }
115.     }
116.     return true;
117. }
119. bool find_BST(BST &T, int e)
120. {
121.     BSTnode *p = T;
122.     while (p)
123.     {
124.         if (e > p->data)
125.             p = p->right;
126.         else if (e < p->data)
127.             p = p->left;
128.         else
129.             break;
130.         ;
131.     }
132.     if (p)
133.         return true;
134.     else
135.         return false;
136. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！