avatar
文章
22
标签
8
分类
1
首页
时间轴
标签
分类
关于
清单
Aemonair
首页
时间轴
标签
分类
关于
清单
数据结构C语言实现13.二叉搜索树_BST
|Study
阅读量:

引言

　二叉搜索树（Binary Search Tree），也称BST树、二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（sorted binary tree）.
　它是指一棵空树或者具有下列性质的二叉树：
　　1. 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
　　2. 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
　　3. 任意节点的左、右子树也分别为二叉查找树；
　　4. 没有键值相等的节点。

二叉搜索树示例1
二叉搜索树示例2

一． 二叉搜索树定义

二叉搜索树示例
二叉搜索树,我们将二叉树节点的类型定义为:

1
2
3
4
5
6
7
8
9
10
typedef struct Tree_node Tree_node;

struct Tree_node               //BST树节点
{
    int                data;   //我们以int做测试
    Tree_node *  left_child;   //左孩子
    Tree_node * right_child;   //右孩子
};

typedef Tree_node BSTree;      //BST树

二．二叉树搜索的接口

  • bstree.h
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
#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_
#include "tools.h"

typedef struct Tree_node Tree_node;

struct Tree_node
{
    int                data;
    Tree_node *  left_child;
    Tree_node * right_child;
};

typedef Tree_node BSTree;


//1.销毁BST二叉搜索树
void BSTree_destroy(BSTree **root);
//2.中序遍历BST二叉搜索树
void mid_order_print(BSTree *root);    
//3.寻找BST二叉搜索树中的最大数
Tree_node *BSTree_max(BSTree *root);
//4.寻找BST二叉搜索树中的最小数
Tree_node *BSTree_min(BSTree *root);
//5.通过数组创建BST二叉搜索树
BSTree *BSTree_create(int *a, int length);
//6.删除BST中某节点
Boolean BSTree_delete(BSTree *root, int p);
//7.1.在BST二叉搜索树中插入某节点
Boolean BSTree_insert0(BSTree **root, int p);
//7.2.在BST二叉搜索树中插入某节点
Boolean BSTree_insert1(BSTree **root, int p);
//8.在BST二叉搜索树中根据值寻找某节点
Tree_node *BSTree_search(BSTree *root, int p);
//9.在BST二叉搜索树中寻找某节点的父节点
Tree_node *find_parent(BSTree *root, Tree_node *node);   

#endif//_BINARY_SEARCH_TREE_H_

三. 搜索二叉树的接口实现

  • bstree.c
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
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
#include "bstree.h"
#include "tools.h"

//创建节点
static Tree_node *create_node(void)
{
    Tree_node *node = (Tree_node *)Malloc(sizeof(Tree_node));
    bzero(node, sizeof(Tree_node));
 
    return node;
}
//1.销毁BST二叉搜索树
void BSTree_destroy(BSTree **root)
{
    if(*root != NULL)
    {
        BSTree_destroy(&(*root)->left_child);   //先处理左孩子
        BSTree_destroy(&(*root)->right_child);  //先处理右孩子
        free(*root);                            //销毁当前节点
        *root = NULL;
    }
}
//2.中序遍历BST二叉搜索树
//根据二叉排序树的性质,中序遍历得到升序序列
void mid_order_print(BSTree *root)
{
    if(root != NULL){
         mid_order_print(root->left_child);
         printf("%d ", root->data);
         mid_order_print(root->right_child);
    }
}

//3.寻找BST二叉搜索树中的最大数
//由于是二叉搜索树,所以,最大值在右孩子的最右边节点
Tree_node *BSTree_max(BSTree *root)
{
    if(NULL == root)
    {
        return NULL;
    }
    if(NULL == root->right_child) //若无右孩子,当前根节点比左子树都大
    {
        return root;
    }
    else
    {
        return BSTree_max(root->right_child);//递归右边查找
    }
}
//4.寻找BST二叉搜索树中的最小数
//最小值在最左节点
Tree_node *BSTree_min(BSTree *root)
{
    if(NULL == root)
    {
        return NULL;
    }
    if(NULL == root->left_child)
    {
        return root;
    }
    else
    {
        return BSTree_min(root->left_child);
    }
}
//5.通过数组创建BST二叉搜索树
//
//
//  Φ  8   8    8       8        8        8          8          8          8
//        /    / \     / \      / \      / \        / \        / \        / \
//       3    3  10   3  10    3  10    3  10      3  10      3  10      3  10
//                   /        / \      / \   \    / \   \    / \   \    / \   \
//                  1        1   6    1   6  14  1   6  14  1   6  14  1   6   14
//                                                  /          / \        / \   /
//                                                 4          4   7      4   7 13  
BSTree *BSTree_create(int *a, int length)
{
    int i = 0;
    BSTree *root = NULL;
    if(NULL == a || length < 0)
    {
        return NULL;
    }
    for(i = 0; i < length; ++i)
    {
        printf("a[%d],%d\n", i, a[i]);
        BSTree_insert1(&root, a[i]);    //依次插入数组中元素
    }
    return root;
}
//6.删除BST中某节点
//   1. 欲删除节点为叶子节点,如1,则释放掉并将其父节点指向其节点的指针置为空;
//   2. 欲删除节点无左孩子有右孩子,如10,则用其右孩子的左右子树替换当前左右子树,并释放;
//   3. 欲删除节点无右孩子有左孩子,如14,则用其左孩子的左右子树替换当前左右子树,并将其释放.
//   4. 欲删除节点左右孩子均不为空,如8,在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整。
//      比较好的做法是，找到*p的直接前驱（或直接后继）*s，用*s来替换结点*p，然后再删除结点*s。
Boolean BSTree_delete(BSTree *root, int key)
{
    Tree_node *p = NULL;
    Tree_node *q = NULL;
    Tree_node *s = NULL;
    if(NULL == root)
    {
        return FALSE;
    }
    if(NULL == (p = BSTree_search(root, key)))
    {
        return FALSE;
    }

    if(NULL == p->left_child && NULL == p->right_child)//叶子节点
    {
        q = p;
        s = find_parent(root, BSTree_search(root, key));
        if(s->left_child->data == q->data) //父节点指向空
            s->left_child = NULL;
        else
            s->right_child = NULL;
        free(q);
    }
    else if(NULL == p->left_child && p->right_child != NULL) //2无左子树有右子树 如10
    {
        q = p->right_child;
        p->data = p->right_child->data;
        p->left_child = q->left_child;
        p->right_child = q->right_child;
        free(q);
    }
    else if(NULL == p->right_child && p->left_child != NULL) // 3无右孩子有左孩子 如14
    {
        q = p->left_child;
        p->data = p->left_child->data;
        p->left_child = q->left_child;
        p->right_child = q->right_child;
        free(q);
    }
    else //左右子树均不为空 如8
    {
        q = p;
        s = p->left_child;   //左转
        while(s->right_child)//向右走向尽头
        {
            q = s;
            s = s->right_child;
        }
        p->data = s->data;   //s指向被删节点的"前驱"
        if(q != p)
            q->right_child = s->left_child; //重接q的右子树
        else
            q->left_child = s->left_child;  //重接q的左子树
        free(s);
    }
    return TRUE;
}
//7.1.在BST二叉搜索树中插入某节点
Boolean BSTree_insert0(BSTree **root, int data)
{
    Tree_node *p = create_node();
    p->data = data;
    if(NULL == *root)
    {
        *root = p;
        return TRUE;
    }
    //插入当前节点的左孩子
    if((*root)->left_child == NULL && (*root)->data > data)
    {
        (*root)->left_child = p;
        return TRUE;
    }
    //插入当前节点的右孩子
    if((*root)->right_child == NULL && (*root)->data < data)
    {
        (*root)->right_child = p;
        return TRUE;
    }
    if((*root)->data > data)
    {
        BSTree_insert0(&((*root)->left_child), data);
    }
    else if((*root)->data < data)
    {
        BSTree_insert0(&((*root)->right_child), data);
    }
    else
    {
        return FALSE;
    }
}
//7.2.在BST二叉搜索树中插入某节点
//   首先查找,BST中若有此节点,则不进行插入.
Boolean BSTree_insert1(BSTree **root, int data)
{
    if(BSTree_search(*root, data) != NULL)//已存在不插入
    {
        return FALSE;
    }
    if(NULL == *root)  //根为空
    {
        Tree_node *p = create_node();
        p->data = data;
        *root = p;
        return TRUE;
    }
    else if((*root)->data > data) //在左子树
    {
        BSTree_insert1(&(*root)->left_child, data);
        return TRUE;
    }
    else if((*root)->data < data)
    {
        BSTree_insert1(&(*root)->right_child, data);
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

//8.在BST二叉搜索树中根据值寻找某节点
//递归查找
Tree_node *BSTree_search(BSTree *root, int key)
{
    if(NULL == root)
    {
        return NULL;
    }
    if(root->data < key)
    {
        return BSTree_search(root->right_child, key);
    }
    else if(root->data > key)
    {
        return BSTree_search(root->left_child, key);
    }
    else
    {
        return root;
    }
}

//9.在BST二叉搜索树中寻找某节点的父节点
Tree_node *find_parent(BSTree *root, Tree_node *node)    //找到指定节点的双亲节点
{
    Tree_node *p_node = NULL;

    if(root == NULL || root->left_child == node 
                    || root->right_child == node){
        //root不存在或者root是所要找的双亲节点
        return root;
    }
    p_node = find_parent(root->left_child, node); 
    if(p_node == NULL)
    { 
        p_node = find_parent(root->right_child, node);
    }
    return p_node;
}

四. 函数功能检测

  • main.c
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bstree.h"
#include "tools.h"

int main(int argc, char **argv)
{
    BSTree *root = NULL;
    Tree_node * x = NULL;
    int a[]=
    //{1,2,3,4,5,6};
    //int a[]={3, 1, 4};
    {8, 3, 10, 1, 6, 14, 4, 7, 13};
    int length = sizeof(a)/sizeof(a[0]);
    printf("length:%d\n", length);

    root = BSTree_create(a, length);

    //                        8
    //                      /   \
    //                     3    10
    //                    / \     \
    //                   1   6    14
    //                      / \   /
    //                     4   7 13
    //
    printf("%d ", root->data);
    printf("%d ", root->left_child->data);
    printf("%d \n", root->right_child->data);

    if(x = BSTree_search(root, 3))
    {
        printf("search: %d\n", x->data);
    }
    if(x = BSTree_search(root, 4))
    {
        printf("search: %d\n", x->data);
    }
    if(x = BSTree_search(root, 5))
    {
        printf("search: %d\n", x->data);
    }

    printf("max: %d.", BSTree_max(root)->data);
    printf("min: %d.\n", BSTree_min(root)->data);

    printf("parent:%d\n",find_parent(root, BSTree_search(root, 1))->data);
    printf("parent:%d\n",find_parent(root, BSTree_search(root, 3))->data);

    mid_order_print(root);
    printf("\ndelete\n");
    BSTree_delete(root, 8);
    BSTree_insert1(&root, 3);
    //printf("%d ", root->left_child->left_child->data);
    printf("max: %d.", BSTree_max(root)->data);
    printf("min: %d.\n", BSTree_min(root)->data);

    mid_order_print(root);
    printf("\n");
    BSTree_destroy(&root);
    return 0;
}
  • 运行结果
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
root@aemonair:~/BSTree# cc.sh *.c
Compiling ...
-e CC      bstree.c main.c tools.c -g -lpthread -lm
-e         Completed .
-e         Sat Aug 20 21:43:11 CST 2016
root@aemonair:~/BSTree# ./bstree 
length:9
a[0],8
a[1],3
a[2],10
a[3],1
a[4],6
a[5],14
a[6],4
a[7],7
a[8],13
8 3 10 
search: 3
search: 4
max: 14.min: 1.
parent:3
parent:8
1 3 4 6 7 8 10 13 14 
delete
max: 14.min: 1.
1 3 4 6 7 10 13 14

五. 总结

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望 O(log n)，最坏O(n)（数列有序，树退化成线性表）。

虽然二叉查找树的最坏效率是O(n),但它支持动态查询，且有很多改进版的二叉查找树可以使树高为 O(log n),如SBT,AVL树，红黑树等。故不失为一种好的动态查找方法。

可是嘞,我们一步一步来好了~

文章作者: Air
文章链接: http://aemonair.github.io/2016/08/20/Data_Structure_13_Binary_Search_Tree/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Aemonair！
DataStructTree
相关推荐
2020-04-29
数据结构C语言实现10.树
2020-04-29
数据结构C语言实现12.线索二叉树
2020-04-29
数据结构C语言实现11.二叉树
2020-04-29
数据结构C语言实现14.自平衡二叉查找树_AVL树
2020-04-29
数据结构C语言实现2.带控制信息的链表
2020-04-29
数据结构C语言实现4.进一步封装的双向链表
简