二叉搜索树的查找、插入和删除
二叉搜索树
二叉搜索树又被称为二叉排序树，它本身也是一棵二叉树，且满足以下性质：
- 若左子树不为空，则左子树上左右节点的值都小于根节点的值
- 若它的右子树不为空，则它的右子树上所有的节点的值都大于根节点的值
- 它的左右子树也要分别是二叉搜索树
1
2
3
4
5
6
7
8
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
|
验证是否为二叉搜索树
递归法
利用有效二叉树的定义：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| bool helper(TreeNode* root, long long lower, long long upper){
if (root == nullptr){
return true;
}
if (root->val <= lower || root->val >= upper){
return false;
}
return helper(root->left, lower, root->val)
&& helper(root->right, root->val, upper);
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
|
中序遍历
中序遍历结果应为递增序列
二叉搜索树的查找
1
2
3
4
5
6
7
8
9
| TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr){
return nullptr;
}
if (root->val == val){
return root;
}
return root->val > val ? searchBST(root->left, val) : searchBST(root->right, val);
}
|
二叉搜素树的插入
当将 val插入到以 root为根的子树上时，根据 val与 root.val的大小关系，就可以确定要将 val插入到哪个子树中：
- 如果该子树不为空，则问题转化成了将
val插入到对应子树上
- 否则，在此处新建一个以
val为值的节点，并链接到其父节点 root上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr){
return new TreeNode(val);
}
TreeNode* pos = root;
while (pos != nullptr){
if (pos->val < val){
if (pos->right == nullptr){
pos->right = new TreeNode(val);
break;
} else{
pos = pos->right;
}
} else{
if (pos->left == nullptr){
pos->left = new TreeNode(val);
break;
} else{
pos = pos->left;
}
}
}
return root;
}
|
二叉搜索树的的删除
删除操作比较复杂，可以分为以下三种情况：
- 被删除节点为叶子节点：直接删除该节点
- 被删除结点有一个左孩子或一个右孩子：将孩子结点设为该结点的父结点的孩子后，即可删除该结点
- 被删除结点有两个孩子结点：一般的删除策略是，用被删除结点的右子树中的最小结点替代被删除结点，并递归地删除这个最小数据结点
利用前继和后继节点也可以分为以下三种情况：
- 要删除的节点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代，该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点
- 删除的节点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代，该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点
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
|
TreeNode* successor(TreeNode* root){
root = root->right;
while (root->left != nullptr){
root = root->left;
}
return root;
}
TreeNode* predecessor(TreeNode* root){
root = root->left;
while (root->right != nullptr){
root = root->right;
}
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr){
return nullptr;
}
if (root->val > key){
root->left = deleteNode(root->left, key);
} else if(root->val < key){
root->right = deleteNode(root->right, key);
} else{
if (root->left == nullptr && root->right == nullptr){
root = nullptr;
} else if (root->right != nullptr){
root->val = successor(root)->val;
root->right = deleteNode(root->right, root->val);
} else{
root->val = predecessor(root)->val;
root->left = deleteNode(root->left, root->val);
}
}
return root;
}
|
