0
0

分享

【校招VIP】二叉排序树（二叉查找树、二叉搜索树）（图解+完整代码）

01月09日 收藏 0 评论 0 java开发

【校招VIP】二叉排序树（二叉查找树、二叉搜索树）（图解+完整代码）

转载声明：文章来源https://blog.csdn.net/weixin_54186646/article/details/124412656

1.什么是二叉排序树
我们直接看它的性质：
若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
它的左、右树又分为⼆叉排序树
显然，二叉排序树与二叉树一样，也是通过递归的形式定义的。因此，它的操作也都是基于递归的方式。
二叉排序树也叫二叉查找树、二叉搜索树，既然名字都不一般，那它显然和普通的二叉树不同。那到底有什么不同，它的特点或者优点在哪里呢？不妨，我们来构建一棵二叉树。

2.构建二叉排序树
假设我们有以下数据，我们按从左到右的顺序来构建二叉排序树：


首先，将8作为根节点
插入3，由于3小于8，作为8的左子树
插入10，由于10大于8，作为8的右子树
插入1，由于1小于8，进入左子树3，1又小于3，则1为3的左子树
插入6，由于6小于8，进入左子树3，6又大于3，则6为3的右子树
插入14，由于14大于8，进入右子树10，14又大于10，则14为10的右子树
插入4，由于4小于8，进入左子树3，4又大于3，进入右子树6，4还小于6，则4为6的左子树
插入7，由于7小于8，进入左子树3，7又大于3，进入右子树6，7还大于于6，则7为6的右子树
插入13，由于13大于8，进入右子树10，又13大于10，进入右子树14,13小于14，则13为14的左子树
经过以上的逻辑，这棵二叉排序树构建完成。


我们可以看出：
只要左子树为空，就把小于父节点的数插入作为左子树
只要右子树为空，就把大于父节点的数插入作为右子树
如果不为空，就一直往下去搜索，直到找到合适的插入位置
了解了如何构建后，我们不禁要问，这有啥用呀？感觉没啥特别的地方呢？别急！我们马上揭晓！
我们对这棵二叉树进行中序遍历，看看会发生什么？你自己试一试！
没错，这棵二叉树中序遍历结果为：


根据以上思路，我们其实就可以写出代码了，构建的过程其实就是插入的过程：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void insert(int key)
{
    //定义一个临时指针 用于移动
    Node* temp = root;//方便移动 以及 跳出循环
    Node* prev = NULL;//定位到待插入位置的前一个结点
    while (temp != NULL)
    {
        prev = temp;
        if (key < temp->data)
        {
            temp = temp->left;
        }
        else if(key > temp->data)
        {
            temp = temp->right;
        }
        else
        {
            return;
        }
    }
  
    if (key < prev->data)
    {
        prev->left = (Node*)malloc(sizeof(Node));
        prev->left->data = key;
        prev->left->left = NULL;
        prev->left->right = NULL;
    }
    else
    {
        prev->right = (Node*)malloc(sizeof(Node));
        prev->right->data = key;
        prev->right->left = NULL;
        prev->right->right = NULL;
    }
}

3.二叉排序树的查找操作
它既然也叫二叉查找树，那想必会非常方便我们查找吧！它的操作并不是把中序遍历的结果存入数组，然后在有序数组里查找，而是直接在树上查找。其操作与二分查找非常相似，我们来查找7试一试？（这里要说明以下：在正常的数据结构中，由于数据量很大，所以我们也不知道我们想要的元素在不在里面；同时也不知道每个元素具体是多少，只知道他们的大小关系。我们是在此基础上进行查找）
首先，访问根节点8
根据性质，7比8小，所以如果7存在，那应该在8的左子树那边，访问8的左子树
访问到了3，根据第2步的思想，访问3的右子树
访问到了6，继续访问6的右子树
访问到了7，刚好找到啦！


显然，它的效率会比在无序数组中挨着查找快多了吧！我们直接上代码。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*查找元素key*/
bool search(Node* root, int key)
{
    while (root != NULL)
    {
        if (key == root->data)
            return true;
        else if (key < root->data)
            root = root->left;
        else
            root = root->right;
    }
    return false;
}

4.二叉排序树的删除

那么删除就稍微比查找与插入复杂一点，因为需要分类讨论了。
1.被删除结点为叶子结点
直接从二叉排序中删除即可，不会影响到其他结点。例如删去7：

2.被删除结点D仅有一个孩子
如果只有左孩子，没有右孩子，那么只需要把要删除结点的左孩子连接到要删除结点的父亲结点，然后删除D结点；
如果只有右孩子，没有左孩子，那么只要将要删除结点D的右孩子连接到要删除结点D的父亲结点，然后删除D结点。
以D=14为例：它没有右孩子，只有左孩子。（先把10指向14的右指针移动，去指向13，然后再删除14）


再以D=10为例，它没有左孩子，只有右孩子。（先把8指向10的右指针移动，去指向14，然后再删除10）


3.被删除结点左右孩子都在
这种情况就要复杂很多了。但没有关系，依然会讲的很清楚。
我们先假设删除根节点8，看看会发生什么？


我们的目标依然是要保证删除结点8后，再次中序遍历它，仍不改变其升序的排列方式。 那么我们只有用7或者10来替换8原来的位置。
我们先看7来顶替位置


此时7从叶子结点“升迁”到了根节点（只是刚好要删除的结点为根节点，如果删除3，就替换3的位置）
我们再看10来顶替位置


这时候我们就应该会产生两个问题：
为什么是7或者10来替换8的位置？
显然，7与10是挨着8的，如果用其他元素替换则会打扰其顺序。
那7和10怎么在二叉排序树中找到呢？
显然，7在8左子树的“最右边”，10在8右子树的“最左边”。根据二叉排序树的插入方式，比8小的元素一定在左子树，而我们又要找到比8小的最大的数，这样才能保证他们俩在顺序上是挨着的，所以它又会在8的左子树的最右边。同理也可以找到10.
根据此方法，我们可以直接给出代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
int delete_node(Node* node, int key)
{
    if (node == NULL)
    {
        return -1;
    }
    else
    {
        if (node->data == key)
        {
            //当我执行删除操作 需要先定位到删除结点的前一个结点（父节点）
            Node* tempNode = prev_node(root, node, key);
            Node* temp = NULL;
             
            //如果右子树为空，只需要重新连接结点（包含叶子结点），直接删除
            if (node->right == NULL)
            {
                temp = node;
                node = node->left;
                /*判断待删除结点是前一个结点的左边还是右边*/
                if (tempNode->left->data == temp->data)
                {
                    Node* free_node = temp;
                    tempNode->left = node;
                    free(free_node);
                    free_node = NULL;
                }
                else
                {
                    Node* free_node = temp;
                    tempNode->right = node;
                    free(free_node);
                    free_node = NULL;
                }
            }
            else if (node->left == NULL)
            {
                temp = node;
                node = node->right;
                if (tempNode->left->data == temp->data)
                {
                    Node* free_node = temp;
                    tempNode->left = node;
                    free(free_node);
                    free_node = NULL;
                }
                else
                {
                    Node* free_node = temp;/
                    tempNode->right = node;
                    free(free_node);
                    free_node = NULL;
                }
            }
            else//左右子树都不为空
            {
                temp = node;
                /*往左子树 找最大值*/
                Node* left_max = node;//找最大值的临时指针
                left_max = left_max->left;//先到左孩子结点
                while (left_max->right != NULL)
                {
                    temp = left_max;
                    left_max = left_max->right;
                }
                node->data = left_max->data;
                if (temp != node)
                {
                    temp->right = left_max->left;
                    free(left_max);
                    left_max = NULL;
                }
                else
                {
                    temp->left = left_max->left;
                    free(left_max);
                    left_max = NULL;
                }
            }
             
        }
        else if(key < node->data)
        {
            delete_node(node->left, key);
        }
        else if (key > node->data)
        {
            delete_node(node->right, key);
        }
    }
}

5.完整代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include<stdio.h>
#include<stdlib.h>
typedef struct SortTree {
    int data;//存放数据的数据域
    struct SortTree* left;//指针域 左指针
    struct SortTree* right;//指针域 右指针
}Node;
/*全局变量*/
Node* root;//根节点
  
void Init(int);//初始化操作
void insert(int);//插入操作
void show(Node*);
int delete_node(Node*, int);
Node* prev_node(Node*, Node*, int);
bool search(Node* root, int key);
int main()
{
    Init(8);
    insert(4);
    insert(2);
    insert(5);
    insert(10);
    insert(9);
    insert(13);
    show(root);
    delete_node(root, 8);
    delete_node(root, 13);
    printf("\n");
    show(root);
}
  
/*初始化根节点
int key : 根节点的值
*/
void Init(int key)
{
    root = (Node*)malloc(sizeof(Node));
    root->data = key;
    root->left = NULL;
    root->right = NULL;
}
  
void insert(int key)
{
    //定义一个临时指针 用于移动
    Node* temp = root;//方便移动 以及 跳出循环
    Node* prev = NULL;//定位到待插入位置的前一个结点
    while (temp != NULL)
    {
        prev = temp;
        if (key < temp->data)
        {
            temp = temp->left;
        }
        else if(key > temp->data)
        {
            temp = temp->right;
        }
        else
        {
            return;
        }
    }
  
    if (key < prev->data)
    {
        prev->left = (Node*)malloc(sizeof(Node));
        prev->left->data = key;
        prev->left->left = NULL;
        prev->left->right = NULL;
    }
    else
    {
        prev->right = (Node*)malloc(sizeof(Node));
        prev->right->data = key;
        prev->right->left = NULL;
        prev->right->right = NULL;
    }
}
  
void show(Node* root)
{
    if (root == NULL)
    {
        return;
    }
    show(root->left);
    printf("%d ", root->data);
    show(root->right);
}
/*查找元素key*/
bool search(Node* root, int key)
{
    while (root != NULL)
    {
        if (key == root->data)
            return true;
        else if (key < root->data)
            root = root->left;
        else
            root = root->right;
    }
    return false;
}
int delete_node(Node* node, int key)
{
    if (node == NULL)
    {
        return -1;
    }
    else
    {
        if (node->data == key)
        {
            //当我执行删除操作 需要先定位到前一个结点
            Node* tempNode = prev_node(root, node, key);
            Node* temp = NULL;
            /*
            如果右子树为空 只需要重新连接结点
            叶子的情况也包含进去了 直接删除
            */
            if (node->right == NULL)
            {
                temp = node;
                node = node->left;
                /*为了判断 待删除结点是前一个结点的左边还是右边*/
                if (tempNode->left->data == temp->data)
                {
                    Node* free_node = temp;//释放用的指针
                    tempNode->left = node;
                    free(free_node);
                    free_node = NULL;
                }
                else
                {
                    Node* free_node = temp;//释放用的指针
                    tempNode->right = node;
                    free(free_node);
                    free_node = NULL;
                }
            }
            else if (node->left == NULL)
            {
                temp = node;
                node = node->right;
                if (tempNode->left->data == temp->data)
                {
                    Node* free_node = temp;//释放用的指针
                    tempNode->left = node;
                    free(free_node);
                    free_node = NULL;
                }
                else
                {
                    Node* free_node = temp;//释放用的指针
                    tempNode->right = node;
                    free(free_node);
                    free_node = NULL;
                }
            }
            else//左右子树都不为空
            {
                temp = node;
                /*往左子树 找最大值*/
                Node* left_max = node;//找最大值的临时指针
                left_max = left_max->left;//先到左孩子结点
                while (left_max->right != NULL)
                {
                    temp = left_max;
                    left_max = left_max->right;
                }
                node->data = left_max->data;
                if (temp != node)
                {
                    temp->right = left_max->left;
                    free(left_max);
                    left_max = NULL;
                }
                else
                {
                    temp->left = left_max->left;
                    free(left_max);
                    left_max = NULL;
                }
            }
             
        }
        else if(key < node->data)
        {
            delete_node(node->left, key);
        }
        else if (key > node->data)
        {
            delete_node(node->right, key);
        }
    }
}
/*定位到待删除节点的前一个结点
Node* root 从根节点开始
Node* node 待删除的结点
int key 待删除数据
*/
Node* prev_node(Node* root, Node* node, int key)
{
    if (root == NULL || node == root)
    {
        return node;
    }
    else
    {
        if (root->left != NULL && root->left->data == key)
        {
            return root;
        }
        else if(root->right != NULL && root->right->data == key)
        {
            return root;
        }
        else if (key < root->data)
        {
            return prev_node(root->left, node, key);
        }
        else
        {
            return prev_node(root->right, node, key);
        }
    }
}</stdlib.h></stdio.h>
C 0条回复 评论

帖子还没人回复快来抢沙发

热门文章
【校招VIP】数据库存储过程（全网最全）
csdn
190
【校招VIP】数据库设计的三大范式
csdn
182
课程推荐
SpingBoot核心注解的分类对比
1,024人学习
ThreadLocal到底用在什么场景？不说要线程池了
1,162人学习