二叉查找树-c语言实现

树简介

对于树的基本认识,我们很容易通过我们平常所见到的树来理解:一棵树,有一个根,根往上又会分叉出大树枝,大树枝又会分叉出小树枝,以此往复,直到最后是叶子。而作为数据结构的树也是类似的,只不过我们通常将它倒着画。树的应用也相当广泛,例如在文件系统,数据库索引中的应用等。本文会对树的基本概念做介绍,但重点介绍二叉查找树。

现实中的树

树的定义

树是一种无向图,其中任意两个节点间存在唯一一条路径。树常常用一种递归的方式来定义,它是一种数据结构,要么为空,要么具有一个值并且有零个或多个孩子,而每个孩子又是树。

例如下图一棵树,任意两个节点间只有一条路径可到达:

树

图一:树

但下图并非树:

树

图二:非树

因为从节点root到节点b并非只有一条路径。

树的种类

我们可能已经听过很多树的名词,例如,红黑树,霍夫曼树,B树,B+树,平衡二叉树等等,而本文将要介绍二叉查找树,很多其他树都是它的变种,不像链表的线性访问,二叉查找树的大部分操作时间复杂度都为O(logN)。

常见名词解释

在学习二叉查找树之前,必须要先了解一些名词,我们借助下面的图来了解,如果已经清楚了可以跳过此节。

介绍树的基本名词:

  • 根节点:root节点没有父节点,我们把它称为根节点
  • 父节点:如b节点的父节点为root节点
  • 子节点:在图三中,root有三个孩子,分别是b,c,d,它们都是root的子节点
  • 兄弟节点:b有两个兄弟节点,c,d,因为它们有相同的父节点root
  • 叶子节点:e f等节点,它们没有子节点,因此是叶子节点。
  • 树的深度:树的深度等于它的最深的树叶的深度,而树叶的深度为从根到本叶子节点的路径长(边数)。根节点的深度为0,例如,图三树的深度root->b->e(也可选其他树叶的深度)为2。
  • 树的层:树的深度+1,根节点的层为1。
  • 二叉树:如图四,每个节点最多两个子节点

树

图三:树

二叉树

图四:二叉树

二叉查找树

二叉树是一种树的特殊形式,它的每个节点最多两个孩子节点,分别为左孩子和右孩子。而二叉查找树在此基础上,还有一个特点,就是每个节点比它左子树的节点值都要大,而比右子树的节点值都要小。另外本文也排除了两个节点存在相同值的情况。

二叉查找树操作

二叉查找树常见操作有插入,查找,删除以及遍历。而实际上二叉查找树既可以使用数组来实现,也可以使用链表,本文采用链表来实现。

节点定义

我们使用一个结构体来定义它:

1
2
3
4
5
6
typedef struct Tree_Node
{
ElementType value; //节点值
struct Tree_Node *left; //左节点
struct Tree_Node *right; //右节点
}TreeNode;

二叉查找树的插入

我们以数据 10,5,19,4,8,13,24为例,来看看二叉查找树的插入流程是怎样的。

  • 插入节点值10,由于原先无节点,因此10作为根节点
  • 插入节点值5,与根节点比较,比根节点小,因此将插入到左子树,而19比根节点大,将插入右子树。
    二叉查找树插入

    图五:二叉查找树插入1
  • 节点值4,与根节点10比较,比根节点小,因此将插入到左子树,继续与5比较,比5小,将插入左子树;节点8,与根节点10比较,比根节点小,因此插入到左子树,与5比较,比5大,因此插入到右子树。
    二叉查找树插入

    图六:二叉查找树插入2
  • 节点值13,与根节点比较,比根节点大,因此将插入到右子树,继续与19比较,比19小,因此插入到左子树;节点值24,与根节点比较,比根节点大,因此将插入到右子树,与19比较,比19大,因此插入到右子树。
    二叉查找树插入

    图七:二叉查找树插入3

最终完成了所有元素的插入。而观察插入后的二叉树可以发现,每个节点都要比左子树的值大,而比右子树的值小。另外,我们在插入的时候不断地与节点值比较,比它大,则将插入右子树,而比它小,则将插入左子树,因此这个过程非常容易用递归来实现。

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
/*将value插入到树中*/
TreeNode *insertTree(ElementType value,TreeNode *tree)
{
if(NULL == tree)
{
/*创建一个节点*/
tree = malloc(sizeof(TreeNode));
if(NULL == tree)
{
printf("malloc failed\n");
return NULL;
}
else
{
/*将节点信息存储在此叶子节点中*/
printf("insert %d to tree\n",value);
tree->value = value;
tree->left = NULL;
tree->right = NULL;
}
}
/*比当前节点小,则插入到左子树*/
else if(value < tree->value)
{
tree->left = insertTree(value,tree->left);
}
/*比当前节点大,则插入到右子树*/
else if(value > tree->value)
{
tree->right = insertTree(value,tree->right);
}
return tree;
}

二叉查找树的查找

实际上,我们在做插入操作的时候,已经在做查找动作了,因为为了将一个元素插入到正确的位置,我们需要从根节点开始,不断比较其值和要插入(查找)的值的大小,如果比该节点值小,则说明该值需要插入到左子树,否则插入到右子树,并且递归调用,最终找到插入的位置。

查找的思路有点像二分查找,我们知道根节点左子树的值都比根节点值小,而右子树的值都比根节点的值要大,以此递归调用,可以很容易找到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*查找值为value的节点*/
TreeNode *findTree(ElementType value,TreeNode *tree)
{
if(NULL == tree)
{
/*最后一层还没有找到*/
return NULL;
}
/*从左子树查找*/
if(value < tree->value)
{
return findTree(value,tree->left);
}
/*从右边子树查找*/
else if(value > tree->value)
{
return findTree(value,tree->right);
}
/*找到*/
else
return tree;
}

二叉查找树的删除

相对来说,删除要比插入和查找复杂很多。因为它需要考虑很多情况:

  • 删除的节点为叶子节点,直接删除
  • 删除的节点有一个子节点,可以将该子节点作为其父节点的子节点
  • 删除的节点有两个子节点,我们可以采取这样的策略:用右子树最小值代替该节点,并递归删除那个节点值。需要递归删除是因为这个最小值的节点可能还有右子树,因此需要做同样的删除操作(它不会有左子树,因为它自己的值最小)。

第一种情况很容易理解,我们来看第二种和第三种情况。

先看第三种情况,假如我们要从前面的二叉树中删除节点值为10的节点。首先我们可以找到节点值为10的节点的右子树的最小值,为13,因此,将13代替节点值为10的节点值,而幸运的是,节点值为13的节点没有右子树,因此释放根节点的内存,完成删除操作。删除前后如图所示:

二叉查找树删除

图八:二叉查找树删除1

再看第二种情况,假如此时要删除值为19的节点,从图中可知,它有一个右儿子,因此删除该节点后,需要将其父节点指向它的右儿子,删除后如下图:

二叉查找树删除2

图九:二叉查找树删除2

总体来说,删除操作并不是一次简单的查找就可以完成,甚至删除会使得整个二叉树变得非常不平衡,所以如果删除次数不多,完全可以采用懒惰删除,即当节点被删除时,仅做一个标记,表明它被删除了,而不是真的从树中移除,这样虽然表面上浪费了一点空间,但是如果后面又要插入该元素值,则为新元素分配内存的开销就免了。

根据上面的分析,代码如下:

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
TreeNode *deleteTree(ElementType value,TreeNode *tree)
{
TreeNode *tempNode = NULL;;
if(NULL == tree)
{
printf("not found \n");
return NULL;
}
/*比当前节点值小,从左子树查找并删除*/
else if(value < tree->value)
{
tree->left = deleteTree(value,tree->left);
}
/*比当前节点值大,从右子树查找并删除*/
else if(value > tree->value)
{
tree->right = deleteTree(value,tree->right);
}
/*等于当前节点值,并且当前节点有左右子树*/
else if(NULL != tree->left && NULL != tree->right)
{
/*用右子树的最小值代替该节点,并且递归删除该最小值节点*/
tempNode = findMin(tree->right);
tree->value = tempNode->value;
tree->right = deleteTree(tree->value,tree->right);
}
/*要删除的节点只有一个子节点或没有子节点*/
else
{
tempNode = tree;
/*要删除节点有右孩子*/
if(NULL == tree->left)
tree=tree->right;
/*要删除节点有左孩子*/
else if(NULL == tree->right)
tree = tree->left;
free(tempNode);
tempNode = NULL;
}
return tree;
}

完整代码及运行结果

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
//binarySearchTree.c
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
#define SUCCESS 0
#define FAILURE -1
typedef struct Tree_Node
{
ElementType value;
struct Tree_Node *left;
struct Tree_Node *right;
}TreeNode;
/*将value插入到树中*/
TreeNode *insertTree(ElementType value,TreeNode *tree)
{
if(NULL == tree)
{
/*创建一个节点*/
tree = malloc(sizeof(TreeNode));
if(NULL == tree)
{
printf("malloc failed\n");
return NULL;
}
else
{
/*将节点信息存储在此叶子节点中*/
printf("insert %d to tree\n",value);
tree->value = value;
tree->left = NULL;
tree->right = NULL;
}
}
/*比当前节点小,则插入到左子树*/
else if(value < tree->value)
{
tree->left = insertTree(value,tree->left);
}
/*比当前节点大,则插入到右子树*/
else if(value > tree->value)
{
tree->right = insertTree(value,tree->right);
}
return tree;
}
/*查找值为value的节点*/
TreeNode *findTree(ElementType value,TreeNode *tree)
{
if(NULL == tree)
{
/*最后一层还没有找到*/
return NULL;
}
/*从左子树查找*/
if(value < tree->value)
{
return findTree(value,tree->left);
}
/*从右边子树查找*/
else if(value > tree->value)
{
return findTree(value,tree->right);
}
/*找到值*/
else
return tree;
}
/*找到一棵树中最小的节点*/
TreeNode *findMin(TreeNode *tree)
{
if(NULL == tree)
return NULL;
else if(NULL == tree->left)
return tree;
else
return findMin(tree->left);
}
TreeNode *deleteTree(ElementType value,TreeNode *tree)
{
TreeNode *tempNode = NULL;;
if(NULL == tree)
{
printf("not found \n");
return NULL;
}
/*比当前节点值小,从左子树查找并删除*/
else if(value < tree->value)
{
tree->left = deleteTree(value,tree->left);
}
/*比当前节点值大,从右子树查找并删除*/
else if(value > tree->value)
{
tree->right = deleteTree(value,tree->right);
}
/*等于当前节点值,并且当前节点有左右子树*/
else if(NULL != tree->left && NULL != tree->right)
{
/*用右子树的最小值代替该节点,并且递归删除该最小值节点*/
tempNode = findMin(tree->right);
tree->value = tempNode->value;
tree->right = deleteTree(tree->value,tree->right);
}
/*要删除的节点只有一个子节点或没有子节点*/
else
{
tempNode = tree;
/*要删除节点有右孩子*/
if(NULL == tree->left)
tree=tree->right;
/*要删除节点有左孩子*/
else if(NULL == tree->right)
tree = tree->left;
free(tempNode);
tempNode = NULL;
}
return tree;
}
int main(void)
{
int a[] = {10,5,19,4,8,13,24};
TreeNode *tree = NULL;
for(int i = 0;i < 7;i++)
{
tree = insertTree(a[i],tree);
}
TreeNode *temp = NULL;
temp = findTree(13,tree);
if(NULL != temp)
printf("find %d\n",temp->value);
deleteTree(13,tree);
deleteTree(19,tree);
return 0;
}

编译运行结果:

1
2
3
4
5
6
7
8
9
10
$ gcc -o binarySearchTree binarySearchTree.c
$ ./binarySearchTree
insert 10 to tree
insert 5 to tree
insert 19 to tree
insert 4 to tree
insert 8 to tree
insert 13 to tree
insert 24 to tree
find 13

总结

本文简单介绍了二叉查找树的插入,查找,删除操作,其中删除操作较为复杂,需要特别注意。

思考

如果待插入数据是已经排好序的,会发生什么情况?

守望 wechat
关注[编程珠玑]获取更多原创技术文章
出入相友,守望相助!