C++：二叉搜索树-171主机测评

Hello大家好！很高兴与大家见面！给生活添点快乐，开始今天的编程之路。

我的博客:<但愿.

我的专栏:C语言、题目精讲、算法与数据结构、C++

欢迎点赞，关注

一⼆叉搜索树的性能分析和概念

1.1⼆叉搜索树的概念

1.2⼆叉搜索树的性能分析

二⼆叉搜索树增删查的实现，这里不支持修改(修改一个就可能不是二叉搜索树的结构了）

2.1⼆叉搜索树基本结构的实现

2.1.1节点的定义(由于后面实现⼆叉搜索树要访问节点成员所以这里使用struct定义(默认是公有))

2.1.2默认成员函数

2.1.2.1⼆叉搜索树的基本结构

2.1.2.2⼆叉搜索树的默认构造

2.1.2.3⼆叉搜索树的拷贝构造

2.1.2.4⼆叉搜索树的赋值重载

2.1.2.5⼆叉搜索树的析构

2.2⼆叉搜索树的插⼊

2.2.1⼆叉搜索树的插⼊整体思路

2.2.2⼆叉搜索树的插⼊代码实现

2.3⼆叉搜索树的查找

2.3.1⼆叉搜索树的查找整体思路

2.3.2⼆叉搜索树的查找代码实现

2.4⼆叉搜索树的删除(最难）

2.4.1⼆叉搜索树删除的整体思路

2.4.2⼆叉搜索树删除的代码实现

2.5⼆叉搜索树的排序(使用中序遍历)

三二叉搜索树增删查排序的整体代码实现

四 key和(key，value)结构

4.1key和(key，value)结构搜索二叉树的定义

4.2(key，value)结构搜索二叉树的实现

五⼆叉搜索树key和key/value使⽤场景

5.1⼆叉搜索树key使⽤场景

5.2⼆叉搜索树key/value使⽤场景

一⼆叉搜索树的性能分析和概念

1.1⼆叉搜索树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，是一种具有以下性质的⼆叉树:

•若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值

•若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值

• 它的左右⼦树都是⼆叉搜索树

•
⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，例如：
map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等
值，multimap/multiset⽀持插⼊相等值

1.2⼆叉搜索树的性能分析

由于它本身自己和它的子树都是⼆叉搜索树，这里观察上面的特点，不难发现：⼆叉搜索树的中序遍历一定是升序序列(所以⼆叉搜索树⼜称⼆叉排序树）。

⼆叉搜索树顾名思义，其只有由于搜索(或者搜索效率高)，下面我们来分析其最优情况和最插情况

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为： log2 N

最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为： N

所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为： O(N)

那么这样的效率显然是⽆法满⾜我们需求的，必须将二叉搜索树优化即⼆叉搜索树的变形：平衡⼆
叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。

那有的人说使用另
⼆分查找也可以实现 O(log2 N) 级别的查找效率
为啥还有将二叉搜索树变形外。需要说明的是，⼆分查找也可以实现 O(log
2
N
)
级别的查找效率，但是⼆分查找有两⼤缺陷：

1. 需要存储在⽀持下标随机访问的结构中，并且有序。

2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数

据。

这⾥也就体现出了平衡⼆叉搜索树的价值。

二⼆叉搜索树增删查的实现，这里不支持修改(修改一个就可能不是二叉搜索树的结构了）

2.1⼆叉搜索树基本结构的实现

2.1.1节点的定义(由于后面实现⼆叉搜索树要访问节点成员所以这里使用struct定义(默认是公有))

template<class K>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;

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

2.1.2默认成员函数

由于⼆叉搜索树涉及到节点资源的开辟、拷贝、删除，所以这里我们需要自己写拷贝构造，赋值重载，析构函数，默认构造一般不满足我们的需求所以看情况是否要写，而这里由于我们需要写拷贝构造(一种特殊的默认构造)所以这里一定要手写默认规则(可以缺省值)

2.1.2.1⼆叉搜索树的基本结构

template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
private:
Node* _root=nullptr;
};

2.1.2.2⼆叉搜索树的默认构造

//默认函数两种方法

//方法1-前面定义有缺省值
/*BSTree()
{ }*/

//方法二
BSTree() = default;

2.1.2.3⼆叉搜索树的拷贝构造

前面的链式结构的树的拷贝需要递归完成（即使用了递归），所以访问私有成员(在类外面调用该函数会出错),而这个函数的实现过程仅供内部使用所以这里应该定义一个私有函数，在定义一个公有函数来调用对应的私有函数。

public:
//拷贝构造
BSTree(const BSTree<K>& t)
{
void _Copy(t._root);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* copy = root;
Node* copy->_left = Copy(root->_left);
Node* copy->right = Copy(root->right);
return copy;
}

2.1.2.4⼆叉搜索树的赋值重载

pubilc:
//赋值重载
BStree<K>& operator(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}

2.1.2.5⼆叉搜索树的析构

public:
//析构函数
~BSTree()
{
Destroy(_root);
}

private:
void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}

2.2⼆叉搜索树的插⼊

2.2.1⼆叉搜索树的插⼊整体思路

1.
树为空，则直接新增结点，赋值给root指针

2.
树不空，按⼆叉搜索树性质，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位置，插⼊新结点。

注意：如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛）【这里我们不讲，一般不用】

2.2.2⼆叉搜索树的插⼊代码实现

//1插入数据-不支持插入已有数据
bool Insert(const K& key)
{
//树为空，则直接新增结点，赋值给root指针
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//由于二插搜索树的特征，所以要先找到插入的位置；
//由于要改变节点直接之间的指向关系，所以要定义两个变量
// 一个变量用于遍历，一个用于储存要插入位置的父节点，方便改变节点之间的指向关系
Node* cur = _root;//用于遍历
Node* parent = nullptr;//用于储存要插入位置的父节点
while(cur)
{
if (cur->_key < key)//插⼊值⽐当前结点⼤往右⾛
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)//插⼊值⽐当前结点⼩往左⾛
{
parent = cur;
cur = cur->_left;
}
else//找到插入位置
{
return false;
}

}

2.3⼆叉搜索树的查找

2.3.1⼆叉搜索树的查找整体思路

1.
从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。

2.
最多查找⾼度次，⾛到到空，还没找到，这个值不存在。

3.
如果不⽀持插⼊相等的值，找到x即可返回

注意：如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。

2.3.2⼆叉搜索树的查找代码实现

//2查找数据
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)//从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找
{
cur = cur->_right;
}
else if(cur->_key > key)//x⽐根值⼩则往左边⾛查找
{
cur = cur->_left;
}
else
{
return true;//找到返回
}
}
return false;//⾛到到空，还没找到，这个值不存在。
}

2.4⼆叉搜索树的删除(最难）

2.4.1⼆叉搜索树删除的整体思路

⾸先
查找元素是否在⼆叉搜索树中，如果不存在，则返回false。

如果查找元素存在则分以下四种情况：（假设要删除的结点为x）

情况一：

问题
：要删除结点x左右孩⼦均为空

解决办法
：把x结点的⽗亲对应孩⼦指针指向空，直接删除x结点

情况二：

问题
：要删除的结点x左孩⼦位空，右孩⼦结点不为空

解决办法
：把x结点的⽗亲对应孩⼦指针指向x的右孩⼦，在直接删除x结点

情况三：

问题
：要删除的结点x右孩⼦位空，左孩⼦结点不为空

解决办法
：把x结点的⽗亲对应孩⼦指针指向x的左孩⼦，在直接删除x结点

情况四(最复杂)

问题
：要删除的结点x左右孩⼦结点均不为空。

解决办法
：⽆法直接删除x结点，因为x的两个孩⼦⽆处安放，只能⽤替换法删除。找x左⼦树的值最⼤结点R(最右结点)或者x右⼦树的值最⼩结点R(最左结点)替代x，因为这两个结点中任意⼀个，放到x的
位置，都满⾜⼆叉搜索树的规则。替代x的意思就是x和R的两个结点的值交换，转⽽变成删除R结
点，R结点符合情况2或情况3，可以直接删除。

总结：情况1可以当成2或者3处理，效果是⼀样的。这些情况就好比一个人生孩子，如果只是生了一个孩子甚至没生孩子可以找父母帮忙，如果生了两个孩子父母忙不过来怎么办呢？这时候可以找一个保姆的思路。

2.4.2⼆叉搜索树删除的代码实现

//删除数据
bool Erase(const K& key)
{
//先找到要删除的节点的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//找到了，准备删除数据
//分为三种情况
//1左孩子为空,左右孩子为空可以一起处理
if (cur->_left == nullptr)
{
if (cur == _root)//要删除的节点就是根节点，直接改变根节点的指向即可
{
_root = cur->_right;
}
else
{
//要删除的节点不是根节点，要判断要删除的节点
//是其父节点的左孩子还是右孩子，方便改变节点直接的指向关系
if (cur == parent->_left)
{
parent->_left= cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;//删除要删除的结点
}
else if (cur->_right == nullptr)//右孩子为空
{
if (cur == _root)////要删除的节点就是根节点，直接改变根节点的指向即可
{
_root = cur->_left;
}
else
{
//要删除的节点不是根节点，要判断要删除的节点
//是其父节点的左孩子还是右孩子，方便改变节点直接的指向关系
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;//删除要删除的结点
}
else
{//有两孩子-两种处理方法这里使用找有子数中最小值节点
Node* pMinRight = cur;
Node* minRight = cur->_right;
//找到右子树中值最小的节点
while (minRight->_left)
{
pMinRight = minRight;
minRight = minRight->_left;
}

2.5⼆叉搜索树的排序(使用中序遍历)

由于使用到了中序遍历即使用了递归，所以访问私有成员(在类外面调用该函数会出错),所以这里应该定义一个私有函数，在定义一个公有函数来调用对应的私有函数。

代码实现：

//排序-利用其特点这里可以使用中序遍历
//由于使用到了中序遍历即使用了递归，所以访问私有成员(在类外面调用该函数回出错)
void InOrder()//定义一个公有函数来调用对应的私有函数
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)//定义一个私有函数
{
if (root == nullptr)
{
return;
}

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

三二叉搜索树增删查排序的整体代码实现

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

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

template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
//默认函数
/*BSTree()
{ }*/
BSTree() = default;

//2拷贝构造
BSTree(const BSTree<K>& t)
{
void _Copy(t._root);
}
//赋值重载
BStree<K>& operator(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
//析构函数
~BSTree()
{
Destroy(_root);
}
//
//1插入数据-不支持插入已有数据
bool Insert(const K& key)
{
//树为空，则直接新增结点，赋值给root指针
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//由于二插搜索树的特征，所以要先找到插入的位置；
//由于要改变节点直接之间的指向关系，所以要定义两个变量
// 一个变量用于遍历，一个用于储存要插入位置的父节点，方便改变节点之间的指向关系
Node* cur = _root;//用于遍历
Node* parent = nullptr;//用于储存要插入位置的父节点
while(cur)
{
if (cur->_key < key)//插⼊值⽐当前结点⼤往右⾛
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)//插⼊值⽐当前结点⼩往左⾛
{
parent = cur;
cur = cur->_left;
}
else//找到插入位置
{
return false;
}

}

cur = new Node(key);
//要判断插入的是当前节点的左子节点还是右子节点
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
//2查找数据
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)//从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找
{
cur = cur->_right;
}
else if(cur->_key > key)//x⽐根值⼩则往左边⾛查找
{
cur = cur->_left;
}
else
{
return true;//找到返回
}
}
return false;//⾛到到空，还没找到，这个值不存在。
}

swap(minRight->_key, pMinRight->_key);
if (pMinRight->_left == minRight)
{
pMinRight->_left = minRight->_right;
}
else
{
pMinRight->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return true;
}
//排序-利用其特点这里可以使用中序遍历
//由于使用到了中序遍历即使用了递归，所以访问私有成员(在类外面调用该函数回出错)
void InOrder()//定义一个公有函数来调用对应的私有函数
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)//定义一个私有函数
{
if (root == nullptr)
{
return;
}

_InOrder(root->_left);
cout << root->_key << " ";
_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* copy = root;
Node* copy->_left = Copy(root->_left);
Node* copy->right = Copy(root->right);
return copy;
}
private:
Node* _root=nullptr;
};

}

四 key和(key，value)结构

4.1key和(key，value)结构搜索二叉树的定义

上面我们实现的二叉搜索树，节点中只储存了一个值(key)，key，称为关键码，关键码即为需要搜索到的值，使用这种搜索二叉树只需要判断key是否存在。key的搜索场景实现的⼆叉树搜索树⽀持增删查，但是不⽀持修改，修改key破坏搜索树结构了(性质)。

这里还有一种搜索二叉树：(key，value)结构的二叉搜索树：

每⼀个关键码还是key，但是每⼀个关键码都有与之对应的值value，value可以任意类型对象。所以树的结构中(结点)除了需要存
储key还要存储对应的value，注意增/删/查还是以key为关键字在⼆叉搜索树的规则下操作，这里不支持修改key，支持修改value。

4.2(key，value)结构搜索二叉树的实现

namespace key_value
{
template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;

K _key; // 中文
V _value; // 英文

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

template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
// 强制生成
BSTree() = default;

// BSTree(const BSTree& t)
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}

// t1 = t3
// BSTree& operator=(BSTree t)
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._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->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}

cur = new Node(key, value);

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

return true;
}

Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{

cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
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->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
// 准备删除
if (cur->_left == nullptr)
{
//if (parent == nullptr)
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}

delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}

delete cur;
}
else // 两个孩子
{
Node* pMinRight = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
pMinRight = minRight;
minRight = minRight->_left;
}

swap(cur->_key, minRight->_key);
if (pMinRight->_left == minRight)
{
pMinRight->_left = minRight->_right;
}
else
{
pMinRight->_right = minRight->_right;
}

delete minRight;
}

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 << endl;
_InOrder(root->_right);
}

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

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

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

Node* copy = new Node(root->_key, root->_value);
copy->_left = Copy(root->_left);
copy->_right = Copy(root->_right);

return copy;
}

private:
Node* _root = nullptr;
};
}

五⼆叉搜索树key和key/value使⽤场景

5.1⼆叉搜索树key使⽤场景

场景1：⼩区⽆⼈值守⻋库，⼩区⻋库买了⻋位的业主⻋才能进⼩区，那么物业会把买了⻋位的业主的
⻋牌号录⼊后台系统，⻋辆进⼊时扫描⻋牌在不在系统中，在则抬杆，不在则提⽰⾮本⼩区⻋辆，⽆
法进⼊。

场景2：检查⼀篇英⽂章单词拼写是否正确，将词库中所有单词放⼊⼆叉搜索树，读取⽂章中的单

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

5.2⼆叉搜索树key/value使⽤场景

场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜索时输⼊英⽂，则同时查找到了英⽂对应的中⽂。

场景2：商场⽆⼈值守⻋库，⼊⼝进场时扫描⻋牌，记录⻋牌和⼊场时间，出⼝离场时，扫描⻋牌，查找⼊场时间，⽤当前时间-⼊场时间计算出停⻋时⻓，计算出停⻋费⽤，缴费后抬杆，⻋辆离场。

场景3：统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。

本篇文章就到此结束，欢迎大家订阅我的专栏，欢迎大家指正，希望有所能帮到读者更好理解C++相关知识，觉得有帮助的还请三联支持一下~后续会不断更新C/C++相关知识，我们下期再见。