当前位置：首页 > ds >正文

【C++篇】二叉树进阶（上篇）：二叉搜索树

ds 2025/7/12 13:18:50

文章目录

- 前言
- 1. 二叉搜索树的概念
- 2. 二叉搜索树的操作及模拟实现
- - 2.1 查找
  - 2.2 插入
  - 2.3 删除
- 3. 二叉搜索树的应用
- - 3.1 K模型（Key）
  - 3.2 KV模型（Key_Value）
- 4. 二叉搜索树查找的时间复杂度分析

前言

本文我们补充二叉树的知识——二叉搜索树。在之前学习初阶数据结构时，我们还留下了这部分知识没有讲解，具体原因是由于C语言的限制，会大大增大我们的学习成本，因此，在学会C++后学习会事半功倍。

二叉搜索树我将会分两个阶段来学习：

二叉搜索树的概念和应用，以及模拟实现二叉搜索树（本文内容）
二叉树OJ题（下篇内容）

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它可以是一颗空树。
它是具有以下性质的二叉树：
如果树不为空时：

非空左子树的所有节点的值小于其根节点的值。
非空左子树的所有节点的值小于其根节点的值。
左右子树都是二叉搜索树
节点的值都是唯一的，不存在相等值的两个节点

为什么又可以叫二叉排序树呢？
因为二叉搜索树的中序遍历的结果一定是一个升序序列

那么，二叉搜索树应该是链式结构还是顺序结构呢？
其实很容易想到，这棵树需要具备增删的功能，若是顺序结构，每次都得挪动数据，效率太差。
因此，二叉搜索树是链式结构。

2. 二叉搜索树的操作及模拟实现

这里操作的实现可以有两种方式：递归和非递归（迭代）。这里我们两者一起实现。

2.1 查找

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在。

非递归：

bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key > key)//比根小就往左走{cur = cur->_left;}else if (cur->_key < key)//比根大就往右走{cur = cur->_right;}else//与根相等就找到了{return true;}}return false;
}

递归：

bool _FindR(Node* root, const K& key)
{if (root == nullptr){return false;}if (root->_key > key)//比根小了,就在左子树上查找{_FindR(root->_left, key);}else if (root->_key < key)//比根大了,就在右子树上查找{_FindR(root->_right, key);}else{return true;}
}

2.2 插入

插入的具体过程分两种情况：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

如果有重复的节点，则插入失败，返回false。

非递归：

bool Insert(const K& key)
{Node* cur = _root;Node* parent = nullptr;if (_root == nullptr){_root = new Node(key);return true;}else{//查找插入的位置while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}//插入cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}
}

递归：

小于根节点，化子问题为在左子树插入
大于根节点，化子问题为在右子树插入

设计参数：

bool _InsertR(Node*& root, const K& key)

这里root参数巧用&引用，可以达到效果是：递归的每层root都是同一个，以达到每一层递归都是作用在一颗树上。
后面的删除也是如此。

bool _InsertR(Node*& root, const K& key)
{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InsertR(root->_left, key);}else if (root->_key < key){_InsertR(root->_right, key);}else{return false;}
}

2.3 删除

删除就比较复杂了，情况分为：

删除的节点没有孩子，也就是叶子节点，直接删即可。
删除的节点有一个孩子，将这个孩子交给父亲，也就是托孤。注意区分左右孩子。
删除的节点有两个孩子，替换法，将其与左子树最大的节点或右子树最小的节点进行替换，转换为一个孩子或两个孩子的节点进行删除。
求法：
左子树最大节点——左子树的最右节点；
右子树最小节点——右子树的最左节点。

还有一个很容易疏忽的一个情况：LeftMax存在左孩子的情况
删除8：
在这里插入图片描述
如果替换后直接删除的话，LeftMax的左孩子就丢失了，因此这里需要托孤。

if (parent->_left == LeftMax)
{parent->_left = LeftMax->_left;
}
else
{parent->_right = LeftMax->_left;
}

完整代码（非递归）：

bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}//右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}//左右都不为空else{Node* LeftMax = cur->_left;parent = cur;//找最右节点while (LeftMax->_right){parent = LeftMax;LeftMax = LeftMax->_right;}swap(cur->_key, LeftMax->_key);//处理LeftMax存在左孩子的情况if (parent->_left == LeftMax){parent->_left = LeftMax->_left;}else{parent->_right = LeftMax->_left;}cur = LeftMax;}delete cur;return true;}}return false;
}

递归：

小于根节点，化子问题为在左子树删除
大于根节点，化子问题为在右子树删除
等于根节点，进行删除操作（同上）
好处是无需控制父节点了，也避免了许多复杂的情况。

bool _EraseR(Node*& root, const K& key)
{if (root == nullptr){return false;}if (root->_key > key){return _EraseR(root->_left, key);}else if (root->_key < key){return _EraseR(root->_right, key);}else{Node* del = root;//左为空if (root->_left == nullptr){root = root->_right;}//右为空else if (root->_right == nullptr){root = root->_left;}//右两个孩子：转化为一个或没有孩子的问题else{Node* LeftMax = root->_left;while (LeftMax->_right){LeftMax = LeftMax->_right;}swap(root->_key, LeftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}
}Node* _root;
};