欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

【C++笔记】【二叉搜索树】流食般投喂

2026-08-01 分类：服务器技术 阅读(28) 评论(0)

本编介绍二叉搜索树，其删除的实现需要特别关注，有些难度。

1、二叉搜索树的基本概念

2、二叉搜索树的性能分析

3、二叉搜索树的实现

4、二叉搜索树的实际应用场景

5、二叉搜索树走深拷贝，其析构、拷贝、赋值、默认构造的强制写法

1、二叉搜索树的基本概念

🧀通俗介绍：将二叉搜索树划分为 "左子树"、"根"、"右子树"，这三部分存在大小关系，即 "左子树" < "根" < "右子树"，他们的左右子树拆成这样，也要符合这个大小关系。

📌二叉搜索树可以支持插入相等的值，也可以不支持插入相等的值，下文实现的是不支持插入相等的值的二叉搜索树。

📌后续学习的 "map/set/multimap/multiset" 底层就是二叉搜索树，其中 "map/set" 不支持插入相等的值，"multimap/multiset" 支持插入相等的值。

2、二叉搜索树的性能分析

最优情况 二叉搜索树是完全二叉树，或者接近完全二叉树 O(log n)
最差情况 退化为单链表那种 O(N)

📌综合：O(N)。

3、二叉搜索树的实现

3.1二叉搜索树的插入
  • 插入分为树空不空，空就新开一个结点给根节点；不空就用插入的值比较大小，找到合适的地方插入，过程需记录父节点，方便最后的链接。

bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}

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;
}
}

cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}

return true;
}

3.2二叉搜索树的查找
  • 用要查找的值和结点值一一比较。

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;
}

🍞如果实现支持插入相等的值，意味着会有多个与查找值相同值的数x，一般要求查找中序的第一个x。

3.3二叉搜索树的删除
  • 先找到要删除的数的位置，cur。
  • 将要删除的结点由孩子的个数分类做不同处理，"0个孩子"、"1个孩子"、"2个孩子"。
  • "0个孩子"，可以归到 "1个孩子" 那。
  • 结点有 "1个孩子"，分为：没有左孩子、没有右孩子，我们这里代码实现是将 "0个孩子"归到没有左孩子那。
  • 没有左孩子：根节点特判，直接换根；特判父母是用那只手牵的右孩子。
  • 没有右孩子：根节点特判，直接换根；特判父母是用那只手牵的左孩子。
  • "2个孩子"：此处这个结点可以泛泛的看成 "根节点"，我们可以通过找右子树的最小值（左子树的最大值），对应树结构就是找右子树的最左结点（左子树的最右结点），去替换掉此时 "根节点" 的值；转换成 "1个孩子"/"0个孩子" 那个解法。

bool Erase(const K& 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;
}
else
{
// 左边没有孩子
if (cur->_left == nullptr)
{
if (_root->_key == key)
{
_root = _root->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}

delete cur;
}
}
else if (cur->_right == nullptr) // 右边没有孩子
{
if (_root->_key == key)
{
_root = _root->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}

delete cur;
}
}
else // 两边都有孩子
{
// 用右子树的最左节点替换
Node* Parentreplace = cur; // 如果该节点的右孩子就是要替换的结点
// 那么，代码就不会执行while循环，Parentreplace开始初始化为nullptr，后面也不会更新
Node* replace = cur->_right;

while (replace->_left)
{
Parentreplace = replace;
replace = replace->_left;
}

cur->_key = replace->_key;

if (Parentreplace->_left == replace)
Parentreplace->_left = replace->_right;
else
Parentreplace->_right = replace->_right;

delete replace;
}

return true;
}
}

return false;
}

3.4二叉搜索树的完整实现

#pragma once
#include<iostream>
using namespace std;

namespace key
{
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;

BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{
}
};

template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}

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;
}
}

cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}

return true;
}

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 Erase(const K& 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;
}
else
{
// 左边没有孩子
if (cur->_left == nullptr)
{
if (_root->_key == key)
{
_root = _root->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}

delete cur;
}
}
else if (cur->_right == nullptr) // 右边没有孩子
{
if (_root->_key == key)
{
_root = _root->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}

delete cur;
}
}
else // 两边都有孩子
{
// 用右子树的最左节点替换
Node* Parentreplace = cur; // 如果该节点的右孩子就是要替换的结点
// 那么，代码就不会执行while循环，Parentreplace开始初始化为nullptr，后面也不会更新
Node* replace = cur->_right;

while (replace->_left)
{
Parentreplace = replace;
replace = replace->_left;
}

cur->_key = replace->_key;

if (Parentreplace->_left == replace)
Parentreplace->_left = replace->_right;
else
Parentreplace->_right = replace->_right;

delete replace;
}

return true;
}
}

return false;
}

void InOrder()
{
_InOrder(_root);
cout << endl;
}

private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}

_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

private:
Node* _root = nullptr;
};
}

4、二叉搜索树的实际应用场景

4.1key搜索场景

📌只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断 key在不在。key的搜索场景实现的⼆叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

场景1

场景2

小区无人值守⻋库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录⼊后台系统，车辆进⼊时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进⼊。
检查⼀篇英文章单词拼写是否正确，将词库中所有单词放⼊⼆叉搜索树，读取⽂章中的单

词，查找是否在⼆叉搜索树中，不在则波浪线标红提示。

4.2key_value搜索场景

📌每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。

场景1

场景2

场景3

简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输⼊英文，则同时

查找到了英文对应的中文。

商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查

找入场时间，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。

统计⼀篇文章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次

出现，（单词，1），单词存在，则++单词对应的次数。

4.3key_value场景二叉搜索树的代码实现

namespace key_value
{
template<class K, class V>
struct BSTNode
{
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;

BSTNode(const K& key, const V& value)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};

template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
public:
// 拷贝构造也是构造，显示写了构造，就不生成默认构造了
// 强制生成默认构造的方法
BSTree() = default;

//拷贝构造
BSTree(const BSTree& t)
{
_root = Copy(t._root);
}

// 赋值重载
BSTree& operator= (BSTree tmp)
{
swap(_root, tmp._root);
return *this;
}

// 析构
~BSTree()
{
Destory(_root);
_root = nullptr;
}

bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}

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;
}
}

cur = new Node(key, value);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}

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)
{
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
{
// 左边没有孩子
if (cur->_left == nullptr)
{
if (_root->_key == key)
{
_root = _root->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}

delete cur;
}
}
else if (cur->_right == nullptr) // 右边没有孩子
{
if (_root->_key == key)
{
_root = _root->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}

delete cur;
}
}
else // 两边都有孩子
{
// 用右子树的最左节点替换
Node* Parentreplace = cur; // 如果该节点的右孩子就是要替换的结点
// 那么，代码就不会执行while循环，Parentreplace开始初始化为nullptr，后面也不会更新
Node* replace = cur->_right;

while (replace->_left)
{
Parentreplace = replace;
replace = replace->_left;
}

cur->_key = replace->_key;

if (Parentreplace->_left == replace)
Parentreplace->_left = replace->_right;
else
Parentreplace->_right = replace->_right;

delete replace;
}

return true;
}
}

return false;
}

void InOrder()
{
_InOrder(_root);
cout << endl;
}

private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}

_InOrder(root->_left);
cout << root->_key << ":" << root->_value << " ";
_InOrder(root->_right);
}

void Destroy(Node* root)
{
if (root == nullptr)
return;

Destroy(root->_left);
Destroy(root->_right);
delete root;
}

Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;

Node* newRoot = new Node(root->_key, root->_value); // 先弄个根
newRoot->_left = Copy(root->_left); // 我相信编译器能把左子树拷贝过来挂到根左边
newRoot->_right = Copy(root->_right);// 我相信编译器能把右子树拷贝过来挂到根右边
return newRoot;
}

private:
Node* _root = nullptr;
};
}

5、二叉搜索树走深拷贝，其析构、拷贝、赋值、默认构造的强制写法

5.1 析构函数

// 析构
~BSTree()
{
Destory(_root);
_root = nullptr;
}

void Destroy(Node* root)
{
if (root == nullptr)
return;

Destroy(root->_left);
Destroy(root->_right);
delete root;
}

5.2拷贝构造

//拷贝构造
BSTree(const BSTree& t)
{
_root = Copy(t._root);
}

Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;

Node* newRoot = new Node(root->_key, root->_value); // 先弄个根
newRoot->_left = Copy(root->_left); // 我相信编译器能把左子树拷贝过来挂到根左边
newRoot->_right = Copy(root->_right);// 我相信编译器能把右子树拷贝过来挂到根右边
return newRoot;
}

5.3赋值运算符重载

// 赋值重载
BSTree& operator= (BSTree tmp)
{
swap(_root, tmp._root);
return *this;
}

5.4强制生成默认构造函数的写法

📌此处需要强制的原因：

拷贝构造也是构造，显示写了构造，就不生成默认构造了

// 拷贝构造也是构造，显示写了构造，就不生成默认构造了
// 强制生成默认构造的方法
BSTree() = default;

赞(0)
未经允许不得转载：171主机测评 » 【C++笔记】【二叉搜索树】流食般投喂
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(60784)#python(20499)#开发语言(17146)#java(15723)#运维(15591)#linux(15133)#大数据(14796)#服务器(13233)#算法(11900)#前端(11123)#网络(9536)#ai(9251)#数据库(9053)#c++(8280)#学习(6905)#课程设计(6886)#机器学习(6799)#区块链(5966)#OpenClaw(5399)#后端(5242)#spring boot(5072)#深度学习(5025)#c语言(4417)#毕业设计(4326)#数据结构(4232)#安全(4217)#docker(3974)#架构(3962)#javascript(3862)#大模型(3730)

热门文章

最新文章

归档

分类