二叉搜索树是有序的。
它可以完成搜索，插入以及删除等操作。
搜索
例题
思考
因为二叉搜索树有以下几个性质。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树。
所以它的搜索效率就跟二分搜索一样很快。
使用迭代法很快就能写出来。
代码
1
2
3
4
5
6
7
8
9
10
| TreeNode* searchNode(TreeNode* root, int target)
{
while (root)
{
if (target == root->val) return root;
if (target < root->val) root = root->left;
if (target > root->val) root = root->right;
}
return nullptr;
}
|
插入
例题
思考
插入就是在搜索的基础上，如果找不到这个节点，那么找个空的位置插入进去。
但在实现上，我们需要记录当前节点以及它的父节点。
否则会发现当前节点是空的之后，丢失了父节点的指针，导致无法建立起联系。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| TreeNode* insertNode(TreeNode* root, int num)
{
if (!root)
{
TreeNode* node = new TreeNode(num);
return node;
}
TreeNode* cur = root;
TreeNode* parent = root;
while (cur)
{
parent = cur;
if (num < cur->val) cur = cur->left;
else cur = cur->right;
}
TreeNode* node = new TreeNode(num);
if (num < parent->val) parent->left = node;
if (num > parent->val) parent->right = node;
return root;
}
|
删除
例题
思考
首先要找到删除的节点，这个用前面的searchNode()函数就可以。
因为要将删除节点的子树连接回去，所以我们要找到的是匹配节点的父节点（就像插入函数那样），直接用搜索函数不行。
麻烦在于删除后结构的调整。
删除一个节点有几种情况呢？
- 没找到删除节点，直接返回原来的树
- 找到删除节点，没有子节点，直接把他变成
NULL删除
- 找到删除节点，有左子节点或右子节点，删去自己，把左子节点或右子节点变成根节点。
- 找到删除节点，同时拥有左右子节点，删去自己，左子树移到右子树的最左边左孩子上，右子节点成为根节点。
第四种情况有些难理解。
因为要保证树的有序，左子树上所有节点肯定是小于右子树任一一个节点的。
把它整个移到右子树的左叶子节点上就不会破坏有序。
代码
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
| TreeNode* deleteNode(TreeNode* root, int target)
{
TreeNode* node = root;
TreeNode* parent = nullptr;
while (node)
{
if (node->val == target) break;
parent = node;
if (target < node->val) node = node->left;
else node = node->right;
}
if (!node) return root;
if (!node->left && !node->right)
{
if (parent->left->val == target) parent->left = nullptr;
if (parent->right->val == target) parent->right = nullptr;
return root;
}
if (node->left && node->right)
{
TreeNode* cur = node->right;
while (cur->left) cur = cur->left;
cur->left = node->left;
if (parent->left && parent->left->val == target)
parent->left = node->right;
if (parent->right && parent->right->val == target)
parent->right = node->right;
}
if (parent->left->val == target)
parent->left = node->left ? node->left : node->right;
if (parent->right->val == target)
parent->right = node->left ? node->left : node->right;
return root;
}
|
小结
至此二叉树的一些基础操作就结束了。其他变形题都可以根据这几种基础操作的思想。
可以发现需要改变二叉树的结构往往都会复杂许多。
如构造，删除等操作。
不过在写这几篇博文的过程中也确实学到许多东西啦。对递归和指针的理解加深了许多。
