数据结构之二叉搜索树

树是一种非线性的数据结构,其中以二叉树尤为常见。这里我们主要介绍下二叉搜索树。

简介

二叉树可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。除了key和卫星数据之外,每个结点还包含属性left、right和parent,他们分别指向结点的左海孩子,有孩子和双亲(当然对于一个二叉树而言,双亲其实只有一个)。

一棵二叉搜索树是以一棵二叉树来组织的,当二叉树的关键字以如下方式存储的时候,那么它就是一颗二叉搜索树。

设 x 是二叉搜索树中的任意结点,如果 y 是 x 的左子树的一个结点,那个 y和x 必须满足 y.key <= x.key>。同理,如果 y 是 x 的右子树的一个结点,那个 y和x 必须满足 y.key >= x.key>

二叉搜索树是定义

二叉搜索树是定义

前驱和后继

如果一个二叉搜索树的所有关键字互不相同,则结点x的后继是含有大于x的最小关键字的结点;同理,结点x的前驱是含有小于x的最大关键字的结点。

这里必须要指出,结点x的后继(如果存在)一定位于 x 的右子树中,一般为右子树的最左结点;同理结点x的前驱(如果存在)一定位于 x 的左子树中,一般为左子树的最右结点;

基本操作

查找

在 二叉搜索树tree 中查找 特定值x 的过程为:

  1. 若该是空树,则返回NULL;
  2. 否则:若找到 k值 对应的结点的时候,返回该结点;
  3. 否则:若 k值 小于当前结点的数据域的值的时候,则搜索左子树;
  4. 否则:搜索右子树。
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
// 按值对二叉树进行搜索,找到了的话就返回该结点;其搜索的时间为 O(h)。

// 递归法:
struct tNode * tree_search(struct tNode *node, int k) {
if (node == NULL || k == node->key) {
return node;
}

if (k < node->key) {
return tree_search(node->left, k);
}else {
return tree_search(node->right, k);
}
}

// 迭代法:
struct tNode * tree_search_iterative(struct tNode *root, int k) {
struct tNode *node = root;

while (node != NULL && k != node->key) {
if (k < node->key) {
node = node->left;
}else {
node = node->right;
}
}

return node;
}

查找最大最小值:根据二叉搜索树的性质,我们知道含最大值的结点一定是该二叉搜索树的最右子结点。同理,含最小值的结点一定是该二叉搜索树的最左子结点。

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
// 查找最小关键字
// 迭代法:
struct tNode * tree_minimum(struct tNode *root) {
struct tNode *node = root;

// 这里是用 node->left 作为判断的结点,而不用 node 来判断是因为当用 node 判断的时候,
// 当循环至最后一位时,node为空,而最小值所在的结点就是该 node 结点的父结点,所以无法获取到父结点,也就无法获取最小OAO值。
while (node->left != NULL) {
node = node->left;
}

return node;
}

// 递归法:
struct tNode *tree_min(struct tNode *node) {
if (node->left == NULL) {
return node;
}else {
return tree_min(node->left);
}
}

// 查找最大关键字
struct tNode * tree_maximum(struct tNode *root) {
struct tNode *node = root;

// 这里是用 node->left 作为判断的结点,而不用 node 来判断是因为当用 node 判断的时候,
// 当循环至最后一位时,node为空,而最小值所在的结点就是该 node 结点的父结点,所以无法获取到父结点,也就无法获取最小值。
while (node->right != NULL) {
node = node->right;
}

return node;
}

插入

对于二叉搜索树的插入,我们知道,新插入的值一定会是该二叉搜索树的新的叶子结点。

所以向一个二叉搜索树中插入一个特定值的算法的过程如下:

  1. 若该二叉搜索树是空树,则将创建结点作为根结点插入;
  2. 若新插入的值小于当前结点的数据域的值,则把新值插入到左子树中,否则:
  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
35
// 插入一个新的结点
// 用该插入法需要注意新建树的时候使用 struct tNode *tree = NULL; 而非 struct tNode *tree = tree_alloc();
// 还有一个非常注意的地方,因为这里的root可能是空树,为了第一次建立一个树,我们必须传入 root结点 的地址,也就是要**,?????????why?
void tree_insert(struct tNode **root, int x) {

// 使用 node 来使 pNode结点 到达叶子结点
// 在这里 node结点 只是一个用于循环判断的变量
struct tNode *node = *root;
struct tNode *pNode = *root;
while (node != NULL) {
pNode = node;
if (node->key > x) {
node = node->left;
}else {
node = node->right;
}
}

// 新建要插入新的结点
struct tNode *newNode = tree_alloc();
newNode->key = x;

// 如果这是一个空的树,就把新结点赋给根节点
if (pNode == NULL) {
*root = newNode;
return ;
}

// 插入数据
if (pNode->key > x) {
pNode->left = newNode;
}else {
pNode->right = newNode;
}
}

删除

在二叉搜索树的各项操作中,删除是最麻烦的,让我们稍稍分析一下;

我们稍微看一下二叉搜索树的结构,我们就会发现删除一个结点,需要分三种情况讨论:

  1. 若被删除结点为叶子结点,即其左子树和右子树均为空树(或者说其没有孩子结点)。所以我们只要简单地把它删除,并修改其双亲结点的孩子指针为空即可。
  2. 若被删除结点只有左子树或着只有右子树,此时只要让其左子树或着右子树的根节点直接成为其双亲结点的孩子节点即可。
  3. 若被删除结点既有左子树又有右子树。这就比较麻烦了,但是我们可以找被删除节点的后继结点y。并让后继结点y的值代替被删除节点的值,然后将后继结点删除,将其右子树挂到其父节点上即可。

所以在二叉搜索树上删除一个结点的算法代码如下:

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
// 删除也有很多种,这里我们使用按值删除
void tree_delete(struct tNode *root, int x) {
// 首先,让我们和insert方法一样,使用 node 和 pNode结点 找到要删除的结点及其父节点;
struct tNode *node = root;
struct tNode *pNode = root;
while (node != NULL) {
if (node->key == x) {
break;
}else if (node->key > x) {
pNode = node;
node = node->left;
}else {
pNode = node;
node = node->right;
}
}

// 现在,我们已经找到了要删除的 结点node 及其父结点 pNode。
if (node->left == NULL && node->right == NULL) {
if (pNode->left == node) {
pNode->left = NULL;
}else {
pNode->right = NULL;
}
}else if(node->left != NULL && node->right == NULL) {
if (pNode->left == node) {
pNode->left = node->left;
}else {
pNode->right = node->left;
}
}else if(node->left == NULL && node->right != NULL) {
if (pNode->left == node) {
pNode->left = node->right;
}else {
pNode->right = node->right;
}
}else {
// 如果 node结点 的左子树和右子树均不空。在删去node结点之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整.
// 我们的做法是搜索 node结点 右子树上值最小的节点min(即后继结点)并用min的值代替 node结点 的值,最后把 min节点(后继结点) 删除即可

struct tNode *min = node->right;
pNode = node;

while (min->left != NULL) {
pNode = min;
min = min->left;
}

//把找到的后继结点的值赋给node结点
node->key = min->key;

// 然后我们只需把后继结点删除了
// 这个判断是用于万一 后继结点min 正好是 node结点 的右孩子,那么就没有走 pNode->left,所以直接删除右孩子即可
if(pNode->right == min)
pNode->right = min->right;
else
pNode->left = min->right;
}
}

遍历

对于一颗二叉树,我们可以进行前序遍历、中序遍历和后序遍历,这个比较简单,所以这里我们放一下前序遍历和中序遍历代码就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 中序遍历输出,这里所写的是中序遍历,还有前序遍历,后序遍历,要实现它们只需要改变‘所需操作’的位置即可。
void tree_inorder_walk(struct tNode *node) {
if (node != NULL) {
tree_inorder_walk(node->left);

// 此处进行所需的操作
printf("%d ", node->key);

tree_inorder_walk(node->right);
}
}


void tree_preorder_walk(struct tNode *node) {
if (node != NULL) {
// 此处进行所需的操作
printf("%d ", node->key);

tree_preorder_walk(node->left);
tree_preorder_walk(node->right);
}
}

补充

本文中使用了的其他代码:

数据结构如下:

1
2
3
4
5
6
#include <stdlib.h>
struct tNode {
int key;
struct tNode *left;
struct tNode *right;
};

为二叉搜索树分配一个空间:

1
2
3
4
5
6
7
// 为二叉搜索树分配一个空间
struct tNode *tree_alloc() {
struct tNode *node = (struct tNode *)malloc(sizeof(struct tNode));
node->left = NULL;
node->right = NULL;
return node;
}
文章目录
  1. 简介
    1. 前驱和后继
  2. 基本操作
    1. 查找
    2. 插入
    3. 删除
    4. 遍历
    5. 补充
|