【C++】——二叉搜索树
目录
一、前言
二、二叉搜索树
2.1概念
2.2二叉搜索树操作
2.2.1 二叉树的查找
2.2.2 二叉搜索树的插入
2.2.3 二叉搜索树的删除
编辑 2.3二叉搜索树的实现
2.3.1查找
2.3.2 插入
2.3.3 删除
2.3.4 打印
2.3.5 拷贝构造和赋值重载
2.3.6 析构函数
2.4 二叉搜索树的应用
2.5二叉搜索树的性能分析
三、全部代码
四、结语
一、前言
🌇个人主页：_麦麦_
📚今日名言：滔滔不绝很容易，可我只想和你在一个慢下来 的世界里交谈。——两地书
二、二叉搜索树
2.1概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
●若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
●若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
●它的左右子树也分别为二叉搜索树
2.2二叉搜索树操作
在认识到什么是一颗二叉搜索树后，那么我们能对这棵树树进行什么操作，接下来让我们来进行对这些操作的认识，为了方便操作的讲解，我们以下面这棵二叉搜索树为例进行操作的讲解。
2.2.1 二叉树的查找
首先讲解的操作是对二叉树的查找。
对于一颗二叉树，如果我们想要去找一个值有没有存储在这个树中，就需要用到查找这个操作。我们大致讲一下查找的思路，具体的模拟实现会在下面为大家进行一个呈现。由于二叉搜索树与一般的树不同，根的左节点的值小于根，根的有节点的值大于根，根据这一个特性，当我们进行数据查找的时候，先从根开始。如果我们要查找的数据比根大，我们就走到根的右节点，反之就走到根的左节点，知道找到我们所想要的数据为止，如果一直找到输的最后也就是访问到空结点都没有找到我们想要的数据，就说明这棵树中并没有我们想查找的数据。
我们以查找数字7为例，根结点的8大于7，我们走到它的左节点3，发现左节点3小于7，紧接着来到3的右结点，6还是小于7，我们继续往右走，发现等于7，那么这个节点就是我们想要的节点。那么如果我们查找的数据比如说是20，还是从根节点开始比较，20大于8，我们来到右节点10，20大于10，继续往右节点走，20大于14，继续往右走，发现是个空节点，此时就说明该树中并没有存储我们想要的数据20。
注：对于二叉搜索树的查找最多查找树的高度次也就是O（n）
2.2.2 二叉搜索树的插入
接下来就是二叉树的插入操作，插入的具体过程大致分为两点：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
2.2.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程 如下：
●情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
●情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
●情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)/左子树中寻找中序下的最后一个结点（关键码最大），用它的值填补到被删除节点 中，再来处理该结点的删除问题--替换法删除
2.3二叉搜索树的实现
在讲完二叉搜索树的基本操作后，下面我们来简单模拟实现一下二叉搜索树。
2.3.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(const K& key)
{
return _FindR(_root, key);
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr) return false;
if (root->_key < key)
{
_FindR(root->_right, key);
}
else if (root->_key > key)
{
_FindR(root->_left, key);
}
else
{
return true;
}
}
2.3.2 插入
接下来我们来实现二叉搜索树的插入，对于插入来说，有两种方式可以实现：递归和非递归。
非递归版的插入：当我们向往当前树插入一个新节点的时候，第一个要做的是操作是判断该树是否为空，为空则需要创建新结点并将该节点作为这棵树的根结点；不为空再进行后续的操作。第二，当我们判断出该树不为空后，第一步是要找出新结点应该要插入的位置，然后再将其与上一个结点进行链接即可。那么我们要如何找到新结点的位置呢，其实我们只要根据二叉搜索树的根节点大于左子树，小于右子树这一特点，从根节点开始，将其值与我们要插入的值进行比较，小于根结点就走到根节点的左子树，大于根结点就走到根节点的右子树，然后再重新与其进行比较，直到走到空为止，那么就是该节点要插入的位置，如果遇到相等的情况就直接退出。在找到插入的位置后我们该如何与父节点进行链接呢，我们知道一个结点只能往左右进行链接，是不能往上找到父节点的，因此我们还需要另外一个变量来存储父节点，当我们不断比较大小遍历树的时候，将父节点进行更新，这样当我们来到正确的位置的时候，就能将新结点与父节点进行链接。
递归版的插入：在了解完非递归版的插入后，其实递归版与其思路大致相同，都是从根节点开始不断遍历树，并将其值与所插入的值进行比较来找到正确插入的位置并进行父节点的链接。与其不同的地方在于，递归版的插入可以不用创建一个变量来单独存储父节点，而是可以通过函数的参数来存储父节点，不过要注意的是要传递结点的引用才能够将其与新结点进行链接。
具体代码如下：
//插入-非递归
bool insert(const K& key)
{
//空树
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//树不为空
else
{
//寻找父亲结点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else return false;
}
//插入新节点
if (parent->_key > key) parent->_left = new Node(key);
else parent->_right = new Node(key);
return true;
}
}
//插入-递归
bool insertR(const K& key)
{
return _insertR(_root, key);
}
bool _insertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
_insertR(root->_right, key);
}
else if (root->_key > key)
{
_insertR(root->_left, key);
}
else return false;
}
2.3.3 删除
在插入之后，我们来实现一下删除。
对于二叉搜索树而言，删除是较为复杂的一个操作。当我们想删除某个值对于的节点是，第一步就是在该树中查找我们所需的值，如果没有直接返回即可。第二步当我们找到值所对应的节点的时，该节点可能会有四种情况：1、左右子树都为空 2、左子树为空 3、右子树为空 4、左右子树都不为空。下面我们对这四种情况进行删除的模拟实现。
对于第一种左右子树都为空的情况，由于我们可以将其归为左子树为空或者右子树为空的情况，我们就可以不对其进行单独处理，归于第二种或者第三种情况都可以。
对于左子树为空的情况，我们需要将其父节点与其右子树进行链接之后，再将该节点的空间释放即可。需要注意删除结点为根结点的时候，这时候就需要将根节点与右子树进行链接即可，而不是父节点。
对于右子树为空的情况，与上一种情况类似，将父节点与其左子树进行链接，并将节点释放。需要注意删除结点为根结点的时候，这时候就需要将根节点与左子树进行链接即可，而不是父节点。
对于左右子树都不为空的情况，我们就需要寻找一个替代节点，可以寻找他的左子树中中值最大的节点，亦可以是右子树中最小的节点，只有选择这两个结点来代替我们所要删除的节点才能满足二叉搜索树中值的特性。我们以左子树中值最大的节点为例，来实现删除的操作。第一步就是找到所删除结点左子树中最大的节点，然后将该节点与所删除结点进行交换，最后从原删除结点的左子树开始重新删除的操作。
依旧有递归和非递归两个版本，具体代码如下：
//删除非递归
bool Erase(const K& key)
{
//空树
if (_root == nullptr) return false;
if (Find(key) == false) return false;
//非空树
//找key
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
//找到了
//删除结点没有孩子或者只有一个孩子
if (cur->_left == nullptr)
{
//特殊情况 -位于根结点
if (cur == _root) _root = cur->_right;
//删除结点位于左侧
else if (parent->_left == cur)
{
parent->_left = cur->_right;
}
//删除结点位于右侧
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
else if (cur->_right == nullptr)
{
//特殊情况 -位于根结点
if (cur == _root) _root = cur->_left;
//删除结点位于左侧
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
//删除结点位于右侧
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
//删除结点有两个孩子
else
{
//找左边最大的节
parent = cur;
Node* LeftMax = cur->_left;
while (LeftMax->_right)
{
parent = LeftMax;
LeftMax = LeftMax->_right;
}
swap(cur->_key, LeftMax->_key);
if (parent->_left == LeftMax)
{
parent->_left = LeftMax->_left;
}
else
{
parent->_right = LeftMax->_left;
}
cur = LeftMax;
}
delete cur;
return true;
}
return false;
}
//删除递归
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
bool _EraseR(Node*& root, const K& key)
{
//找不到
if (root = nullptr) return false;
if (root->_key < key)
{
_EraseR(root->_right, key);
}
else if (root->_key > key)
{
_EraseR(root->_left, 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(LeftMax->_key, root->_key);
EraseR(root->_left, key);
}
delete del;
return true;
}
}2.3.4 打印
对于二叉搜索树的打印我们采取中序遍历递归的方法就能够将该树中的数据按照降序的顺序打印出来。
具体代码如下：
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void _Inorder(Node* root)
{
if (root == nullptr) return;
_Inorder(root->_left);
cout << root->_key << ' ';
_Inorder(root->_right);
}2.3.5 拷贝构造和赋值重载
对于二叉搜索树的拷贝，我们采取前序遍历的递归方式对树中的节点进行拷贝，当我们实现完树的拷贝之后，就能够借助现代写法将赋值重载一并实现。
具体代码如下：
Node* Copy(Node*& root)
{
if (root == nullptr) return nullptr;
Node* node = new Node(root->_key);
node->_left = Copy(root->_left);
node->_right = Copy(root->_right);
return node;
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}2.3.6 析构函数
对于二叉搜索树的析构来说，我们采取后续遍历的递归方式来释放结点空间。
具体代码如下：
~BSTree()
{
Destroy(_root);
}
void Destroy(Node*& root)
{
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
if (root->_left == nullptr && root->_right == nullptr)
{
delete root;
root = nullptr;
}
}2.4 二叉搜索树的应用
1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方 式在现实生活中非常常见： 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文就构成一种键值对； 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。
2.5二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：logN
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N
如果退化成单支树，二叉搜索树的性能就失去,那么该应对这种情况，在后续章节学习的AVL树和红黑树就可以很好的解决这种问题。
三、全部代码
对于二叉搜索树模拟实现的全部代码以及对其改造K模型与K_V模型的代码附下：
namespace Key
{
template<class K>
struct BSTreeNode
{
BSTreeNode(K key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
};
template<class K>
class BSTree
{
public:
typedef BSTreeNode<K> Node;
BSTree()
:_root(nullptr)
{}
BSTree(BSTree<K>& t)
{
_root = Copy(t._root);
}
Node* Copy(Node*& root)
{
if (root == nullptr) return nullptr;
Node* node = new Node(root->_key);
node->_left = Copy(root->_left);
node->_right = Copy(root->_right);
return node;
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destroy(_root);
}
void Destroy(Node*& root)
{
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
if (root->_left == nullptr && root->_right == nullptr)
{
delete root;
root = nullptr;
}
}
//插入-非递归
bool insert(const K& key)
{
//空树
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//树不为空
else
{
//寻找父亲结点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else return false;
}
//插入新节点
if (parent->_key > key) parent->_left = new Node(key);
else parent->_right = new Node(key);
return true;
}
}
//插入-递归
bool insertR(const K& key)
{
return _insertR(_root, key);
}
bool _insertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
_insertR(root->_right, key);
}
else if (root->_key > key)
{
_insertR(root->_left, key);
}
else return false;
}
//查找-非递归
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(const K& key)
{
return _FindR(_root, key);
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
//删除非递归
bool Erase(const K& key)
{
//空树
if (_root == nullptr) return false;
if (Find(key) == false) return false;
//非空树
//找key
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
//找到了
//删除结点没有孩子或者只有一个孩子
if (cur->_left == nullptr)
{
//特殊情况 -位于根结点
if (cur == _root) _root = cur->_right;
//删除结点位于左侧
else if (parent->_left == cur)
{
parent->_left = cur->_right;
}
//删除结点位于右侧
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
else if (cur->_right == nullptr)
{
//特殊情况 -位于根结点
if (cur == _root) _root = cur->_left;
//删除结点位于左侧
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
//删除结点位于右侧
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
//删除结点有两个孩子
else
{
//找左边最大的节
parent = cur;
Node* LeftMax = cur->_left;
while (LeftMax->_right)
{
parent = LeftMax;
LeftMax = LeftMax->_right;
}
swap(cur->_key, LeftMax->_key);
if (parent->_left == LeftMax)
{
parent->_left = LeftMax->_left;
}
else
{
parent->_right = LeftMax->_left;
}
cur = LeftMax;
}
delete cur;
return true;
}
return false;
}
//删除递归
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
void _Inorder(Node* root)
{
if (root == nullptr) return;
_Inorder(root->_left);
cout << root->_key << ' ';
_Inorder(root->_right);
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr) return false;
if (root->_key < key)
{
_FindR(root->_right, key);
}
else if (root->_key > key)
{
_FindR(root->_left, key);
}
else
{
return true;
}
}
bool _EraseR(Node*& root, const K& key)
{
//找不到
if (root = nullptr) return false;
if (root->_key < key)
{
_EraseR(root->_right, key);
}
else if (root->_key > key)
{
_EraseR(root->_left, 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(LeftMax->_key, root->_key);
EraseR(root->_left, key);
}
delete del;
return true;
}
}
Node* _root;
};
}
namespace Key_Value
{
template<class K,class V>
struct BSTreeNode
{
BSTreeNode( K key, V val)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_val(val)
{}
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
V _val;
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value)
{
//空树
if (_root == nullptr)
{
_root = new Node(key,value);
return true;
}
//树不为空
else
{
//寻找父亲结点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else return false;
}
//插入新节点
if (parent->_key > key) parent->_left = new Node(key,value);
else parent->_right = new Node(key,value);
return true;
}
}
Node* 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 cur;
}
return nullptr;
}
bool Erase(const K& key)
{
//空树
if (_root == nullptr) return false;
if (Find(key) == false) return false;
//非空树
//找key
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
//找到了
//删除结点没有孩子或者只有一个孩子
if (cur->_left == nullptr)
{
//特殊情况 -位于根结点
if (cur == _root) _root = cur->_right;
//删除结点位于左侧
else if (parent->_left == cur)
{
parent->_left = cur->_right;
}
//删除结点位于右侧
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
else if (cur->_right == nullptr)
{
//特殊情况 -位于根结点
if (cur == _root) _root = cur->_left;
//删除结点位于左侧
else if (parent->_left == cur)
{
parent->_left = cur->_left;
}
//删除结点位于右侧
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
//删除结点有两个孩子
else
{
//找左边最大的节
parent = cur;
Node* LeftMax = cur->_left;
while (LeftMax->_right)
{
parent = LeftMax;
LeftMax = LeftMax->_right;
}
swap(cur->_key, LeftMax->_key);
if (parent->_left == LeftMax)
{
parent->_left = LeftMax->_left;
}
else
{
parent->_right = LeftMax->_left;
}
cur = LeftMax;
}
delete cur;
return true;
}
return false;
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
Node* _root = nullptr;
void _Inorder(Node* root)
{
if (root == nullptr) return;
_Inorder(root->_left);
cout << root->_key << ":" << root->_val << endl;;
_Inorder(root->_right);
}
};
}四、结语
到此为止，关于二叉搜索树的讲解就告一段落了，至于其他的内容，小伙伴们敬请期待呀！
关注我 _麦麦_分享更多干货：_麦麦_-CSDN博客
大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！