二叉搜索树
二叉搜索树引入
概念
- 一种树状数据结构,其中每个节点最多有两个子节点,通常称为左子节点和右子节点。
- 左子树上的所有节点的值都小于等于根节点的值。
- 右子树上的所有节点的值都大于等于根节点的值。
- 它的左右子树也分别为二叉搜索树。
- 这个性质使得在二叉搜索树中可以高效地进行搜索、插入和删除操作。
1 | 8 |
别称
- 排序二叉树(Sorted Binary Tree):
- 类似于“有序二叉树”,强调了树中元素的排序。
- 二叉查找树(Binary Search Tree,BST):
- 使用“查找”这个词语,强调了BST在搜索操作上的高效性。
- 二叉排序树(Binary Sort Tree):
- 强调了BST作为一种排序数据的树形结构。
二叉搜索树操作
节点定义
1 | // 节点结构定义 |
1. 搜索操作:
- 思路:
- 从根节点开始比较目标值与当前节点的值。
- 如果目标值等于当前节点值,则找到目标节点。
- 如果目标值小于当前节点值,递归在左子树中搜索。
- 如果目标值大于当前节点值,递归在右子树中搜索。
- 重复以上步骤,直到找到目标节点或到达叶子节点。
2. 插入操作:
- 思路:
- 从根节点开始比较要插入的值与当前节点的值。
- 如果要插入的值小于当前节点值,递归地插入到左子树。
- 如果要插入的值大于当前节点值,递归地插入到右子树。
- 如果当前节点为空,表示找到插入位置,创建一个新节点插入。
3. 删除操作:
- 思路:
- 删除节点分为三种情况:
- 节点没有子节点: 直接删除节点。
- 节点有一个子节点: 将子节点替换为当前节点。
- 节点有两个子节点: 找到右子树的最小节点(或左子树的最大节点),用它替换当前节点,然后在右子树中递归删除这个最小节点。
- 删除节点分为三种情况:
4. 中序遍历:
-
思路:
- 采用递归方式,按照左子树-根节点-右子树的顺序遍历。
- 递归遍历左子树,访问当前节点,然后递归遍历右子树。
- 得到的节点序列是有序的。
函数解析
插入辅助函数
insertHelper
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15BSTNode* insertHelper(BSTNode* root, int val) {
// 如果根节点为空,创建新节点并返回
if (!root) {
return new BSTNode(val);
}
// 根据值的大小关系递归插入节点
if (val < root->_val) {
root->_left = insertHelper(root->_left, val);
} else {
root->_right = insertHelper(root->_right, val);
}
return root;
}-
基本情况: 如果当前节点 (
root
) 为空,表示到达树的底部,创建一个新节点,并将其作为叶子节点插入。1
2
3if (!root) {
return new BSTNode(val);
} -
递归调用: 根据值的大小关系,递归调用插入函数来在左子树或右子树中插入新节点。
1
2
3
4
5if (val < root->_val) {
root->_left = insertHelper(root->_left, val);
} else {
root->_right = insertHelper(root->_right, val);
} -
返回根节点: 返回当前子树的根节点。
1
return root;
查找辅助函数
findHelper
1
2
3
4
5
6
7
8
9
10
11
12
13BSTNode* findHelper(BSTNode* root, int val) {
// 如果根节点为空或找到了目标值,返回当前节点
if (!root || root->_val == val) {
return root;
}
// 根据值的大小关系递归查找节点
if (val < root->_val) {
return findHelper(root->_left, val);
} else {
return findHelper(root->_right, val);
}
}-
基本情况: 如果当前节点 (
root
) 为空或找到了目标值,表示查找成功,返回当前节点。1
2
3if (!root || root->_val == val) {
return root;
} -
递归调用: 根据值的大小关系,递归调用查找函数在左子树或右子树中查找目标值。
1
2
3
4
5if (val < root->_val) {
return findHelper(root->_left, val);
} else {
return findHelper(root->_right, val);
}
删除辅助函数
deleteHelper
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
33BSTNode* deleteHelper(BSTNode* root, int val) {
// 如果根节点为空,返回空
if (!root) {
return root;
}
// 根据值的大小关系递归删除节点
if (val < root->_val) {
root->_left = deleteHelper(root->_left, val);
} else if (val > root->_val) {
root->_right = deleteHelper(root->_right, val);
} else {
// 找到要删除的节点
// 情况1:节点没有子节点或只有一个子节点
if (!root->_left) {
BSTNode* temp = root->_right;
delete root;
return temp;
} else if (!root->_right) {
BSTNode* temp = root->_left;
delete root;
return temp;
}
// 情况3:节点有两个子节点
BSTNode* temp = findMin(root->_right);
root->_val = temp->_val;
root->_right = deleteHelper(root->_right, temp->_val);
}
return root;
}-
基本情况: 如果当前节点 (
root
) 为空,表示到达树的底部,返回空。1
2
3if (!root) {
return root;
} -
递归调用: 根据值的大小关系,递归调用删除函数在左子树或右子树中删除节点。
1
2
3
4
5if (val < root->_val) {
root->_left = deleteHelper(root->_left, val);
} else if (val > root->_val) {
root->_right = deleteHelper(root->_right, val);
} -
节点删除:
- 情况1: 如果要删除的节点没有左子节点或只有一个左子节点,用右子节点(如果存在)替换该节点,然后删除该节点。
1
2
3
4
5if (!root->_left) {
BSTNode* temp = root->_right;
delete root;
return temp;
}- 情况2: 如果要删除的节点没有右子节点或只有一个右子节点,用左子节点(如果存在)替换该节点,然后删除该节点。
1
2
3
4
5else if (!root->_right) {
BSTNode* temp = root->_left;
delete root;
return temp;
}- 情况3:
如果要删除的节点有左右两个子节点,找到右子树中的最小值节点,用其值替换当前节点的值,然后递归地在右子树中删除这个最小值节点。
1
2
3
4
5else {
BSTNode* temp = findMin(root->_right);
root->_val = temp->_val;
root->_right = deleteHelper(root->_right, temp->_val);
}-
返回根节点: 返回当前子树的根节点。
1
return root;
查找右子树的最小值节点辅助函数
findMin
1
2
3
4
5
6
7BSTNode* findMin(BSTNode* node) {
// 遍历左子树找到最小值节点
while (node->_left) {
node = node->_left;
}
return node;
}这个辅助函数用于在右子树中找到最小值的节点,确保在删除操作中正确处理有两个子节点的情况。
这些辅助函数共同协作,确保二叉搜索树的插入、查找和删除操作能够正确地维护树的有序性质。
评论