二叉搜索树的模拟实现
前言
概念
二叉搜索树，又名二叉排序树、二叉查找树，它的特点是：
① 左节点的值 < 根节点的值 ② 右节点的值 > 根节点的值 ③ 每棵子树都是二叉搜索树
由于这些特性，就使得在该树中查找值非常的方便，大于目前节点的值，就遍历右子树；小于目前节点的值，就遍历左子树。其次，二叉排序树还有以下特点：不可出现重复数据
应用
map，set，AVL树，红黑树，B树，优先队列
特点
由于左子树都小于根节点，右子树大于根节点，所以当中序遍历时，序列是升序排列的
因为这一特点，当你模拟实现时，又不知道如何检查自己实现是否正确时，就可以用用例来中序遍历输出，如果顺序不对，你就要去检查自己的代码啦ε=ε=ε=(~￣▽￣)~
模拟实现
数据结构的模拟实现无非就两个部分构成：
1、基本节点（如链表的节点ListNode） 和 数据结构(如链表List) 的构成，该部分通常由结构体或者类来定义 2、该数据结构的相关操作函数的实现
基本结构定义
拓展
在C++中，我们不用将每个节点的类型提前typedef一下，而是可以通过模板来写，这也是C++支持泛型编程的原因，它大大提高了代码的复用，在C++98的STL的实现中大量使用
结构定义
首先定义二叉树的每个节点，与普通二叉树一样，每个节点有
1、左右节点指针 2、该节点的数据值（二叉搜索树部分大多用key表示，因为除了有key结构，还有key，value结构）
template<typename K>
// 类模板
// 该结构较为常用且类外要使用，因此定义为struct更方便（默认public权限）
struct BSNode/*BinarySearchTree的缩写*/
{
BSNode<K>* left;
BSNode<K>* right;
K key;
/*
key结构：
通常用来用于：查找某值是否存在
现实使用场景：
门禁系统
key、value结构
通常用于：
1、确定一个值是否存在
2、通过key查找value
现实使用场景：
字典
*/
/*自定义的构造函数，当一个值被定义后，就会自动调用，这也是C++对C的改进*/
BSNode(const K& k)
: left(nullptr)
, right(nullptr)
, key(k)
{}
};再定义二叉树的整体数据结构
函数定义
构造函数
template<typename K>
class BSTree
{
typedef BSNode<K> Node;/*<K>不可以省，类模板必须显示传模板参数*/
public:
// 无参拷贝构造
BSTree()
{}
// 析构
void Destory(Node*& root)
{
if (root == nullptr)
return;
Destory(root->left);
Destory(root->right);
delete root;
root = nullptr;
}
private:
Node* _root = nullptr/*初始化，这样子就可以不用在构造时赋值了*/;
};拷贝构造
BSTree(const BSTree<K>& tree)
{
/*
参数：
&:减少拷贝，提高效率
const：避免该函数更改tree的值
*/
_root = Copy(tree._root);
}
Node* Copy(Node* root)
{
// 一个树要构造，就需要它的孩子节点构造好 -------------> 所以要使用后序遍历
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->key);
newRoot->left = Copy(root->left);
newRoot->right = Copy(root->right);
return newRoot;
}重载赋值运算符（=）
扩展
C++中提供了重载函数，我们可以重载大部分运算符，这使我们对自定义类型的操作更方便，但如下运算符不可以被重载
-
.(成员访问运算符): 这个运算符用于访问类、结构体或联合体的成员。由于它用于访问成员变量和成员函数，它的行为是固定的，不能被重载。 -
.*(成员指针访问运算符): 这个运算符用于通过成员指针访问类的成员。同样，由于它直接关联于类的内部结构，它的行为也是固定的，不允许重载。 -
::(作用域解析运算符): 这个运算符用于指定类、命名空间或枚举类型的成员。它用于指定一个特定的作用域中的名称，其意义和作用域在C++中是固定的，因此不能被重载。 -
sizeof(类型大小运算符): 这个运算符用于获取对象或类型在内存中所占的字节大小。由于sizeof在编译时就被求值，并且其行为与具体的运行时上下文无关，因此它不能被重载。 -
typeid(类型识别运算符): 这个运算符用于在运行时获取对象的类型信息。虽然它的行为在某些方面依赖于对象本身，但它是语言内置的运行时类型识别机制的一部分，因此不能被重载。 -
?:(条件运算符，也称为三元运算符): 虽然这个运算符的行为可以根据给定的条件动态变化，但它是C++语言的一部分，其语法和功能在语言中是固定的，因此不允许被重载。 -
#和##(预处理运算符): 这两个运算符在预处理阶段用于宏展开和字符串化等操作，与C++的运行时或编译时环境不直接相关，因此它们不被视为C++的运算符，自然也无法被重载。
我们在写代码时，提高复用有时候能提高效率，而下面关于拷贝构造的复用就是一种标选
BSTree<K>& operator=(BSTree tree)
{
/*
参数：拷贝构造 ----------> 方便后序swap
*/
swap(*this, tree);
/*
这样子就可以出了该函数就会自己调用析构函数
*/
return *this;
// 返回值传引用的原因：
// 1、减少拷贝数据的时间，提高效率
// 2、出了作用域，该返回值仍然存在，所以可以传引用，否则就会崩溃
}Insert函数
bool Insert(const K& k)
{
// 从根节点查找正确插入位置
Node* cur = _root;
// 记录父节点，方便后序插入时操作
Node* parent = nullptr;
// = nullptr更好，如果设置为 = NULL，有时候可能出问题，因为NULL的底层只是数字0被强转为指针，而nullptr是真正的指针
/*
底层：
#ifndef NULL
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void *)0)
#endif
#endif
*/
// 寻找插入位置，由于二叉排序树的数据都需要插入到叶子节点，所以该处的循环停止条件为cur为nullptr
while (cur)
{
parent = cur;
if (k < cur->key)
{
// 如果查找的值 < 该节点的值，查找左子树
cur = cur->left;
}
else if (k > cur->key)
{
// 如果查找的值 > 该节点的值，查找右子树
cur = cur->right;
}
else// 与二叉树中的值相等，在二叉排序树中不可有重复数据，因此返回false
return false;
}
// 处理节点
Node* node = new Node(k);
if (parent == nullptr)
_root = node;
else if (k > parent->key)
{
parent->right = node;
}
else
parent->left = node;
return true;
}Erase函数
void Erase(const K& k)
{
Node* parent = nullptr;
Node* cur = _root;
// 查找该值
while (cur)
{
if (k < cur->key)
{
parent = cur;
cur = cur->left;
}
else if (k > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
// 讲解
}
}
}当查找到该值时，我们需要进行复杂的操作才可以删除这个元素
分析
一、该节点左节点为空
1、删除的节点为根
很显然，只需要将根节点改为根节点的右孩子就好
if (cur->left == nullptr)
{
if (cur == _root)
{
_root = cur->right;
}
}2、该节点不是根节点
（1）它是父节点的左孩子（如下面的1）
我们只需要：
① 父节点的左孩子的指针指向删除元素的右孩子 ② 删除元素的右孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素
（2）它是父节点的右孩子
① 父节点的右孩子的指针指向删除元素的右孩子 ② 删除元素的右孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素
else if (parent->left == cur)
{
parent->left = cur->right;
}
else if (parent->right == cur)
{
parent->right = cur->right;
}
delete cur;// 删除该节点二、该节点右节点为空
1、删除的节点为根
很显然，只需要将根节点改为根节点的左孩子就好
else if (cur->right == nullptr)
{
if (cur == _root)
{
_root = cur->left;
}
}2、该节点不是根节点
（1）它是父节点的左孩子
我们只需要：
① 父节点的左孩子的指针指向删除元素的左孩子 ② 删除元素的左孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素
（2）它是父节点的右孩子
① 父节点的右孩子的指针指向删除元素的左孩子 ② 删除元素的右孩子的父亲 指向 自己的父节点的父节点 ③ 删除该元素
else if (parent->left == cur)
{
parent->left = cur->left;
}
else if (parent->right == cur)
{
parent->right = cur->left;
}
delete cur;三、左右孩子都存在
这种情况有两种解决方法
1、找其左子树的最大节点（也就是左子树最右边的节点） 2、找其右子树的最小节点（也就是右子树最左边的节点）
我将用第二种方法举例
1、先将指针指向右子树节点 2、一直向左遍历 3、找到最左边节点 4、与要删除的节点的 值 交换 5、再按照上面的左孩子为空的解决方法，删除该元素
演示
找到最左边节点，将其与要删除的节点的 值 交换
5、再按照上面的左孩子为空的解决方法，删除该元素
else
{
Node* subLeftParent = cur;
// 1、先将指针指向右子树节点
Node* subLeft = cur->right;
//2、一直向左遍历，找到最左边节点
while (subLeft->left)
{
subLeftParent = subLeft;
subLeft = subLeft->left;
}
// 4、与要删除的节点的 值 交换
swap(subLeft->key, cur->key);
// 5、再按照上面的左孩子为空的解决方法，删除该元素
if (subLeft == subLeftParent->left)
{
subLeftParent->left = subLeft->right;
delete subLeft;
}
else
{
subLeftParent->right = subLeft->right;
delete subLeft;
}
}
// 返回
return;Find函数
bool Find(const K& k)
{
Node* cur = _root;
while (cur)
{
if (k < cur->key)
{
cur = cur->left;
}
else if (k > cur->key)
{
cur = cur->right;
}
else
return true;
}
return false;
}Inorder中序遍历函数
// 因为外界不知道root，所以这样子就省的再写一个函数去获取_root了
void Inorder()
{
_Inorder(_root);
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->left);
cout << root->key << ' ';
_Inorder(root->right);
}FindR函数（递归查找元素）
bool FindR(const K& k)
{
return _FindR(_root, k);
}
private:
bool _FindR(Node* root, const K& k)
{
if (root == nullptr)
return false;
if (k > root->key)
return _FindR(root->right);
else if (k < root->key)
return _FindR(root->left);
else
return true;
}InsertR函数（递归插入）
bool InsertR(const K& k)
{
return _InsertR(_root, k);
}
private:
bool _InsertR(Node*& root, const K& k)
{
if (root == nullptr)
{
// 因为传参是引用，就不需要去记录父节点，而直接改变
root = new Node(k);
return true;
}
if (k > root->key)
return _InsertR(root->right, k);
else if (k < root->key)
return _InsertR(root->left, k);
else
return false;
}EraseR函数（递归删除）
bool EraseR(const K& k)
{
return _EraseR(_root, k);
}
private:
bool _EraseR(Node*& root, const K& k)
{
if (root == nullptr)
return false;
if (root->key < k)
return _EraseR(root->right, k);
else if (root->key > k)
return _EraseR(root->left, k);
else
{
if (root->left == nullptr)
{
Node* del = root;
root = root->right;
delete del;
}
else if (root->right == nullptr)
{
Node* del = root;
root = root->left;
delete del;
}
else
{
// 找右子树最左边的
Node* subLeft = root->right;
while (subLeft->left)
{
subLeft = subLeft->left;
}
// 更改 右子树最小元素 和 要删除元素 的值
swap(root->key, subLeft->key);
/*关键点，因为传的是引用，因此只需要重复“左孩子为空”这种情况的代码就好*/
return _EraseR(root->right, k);
}
}
}析构函数
~BSTree()
{
Destory(_root);
}
private:
Node* Destory(Node*& root)
{
if (root == nullptr)
return nullptr;
root->left = Destory(root->left);
root->right = Destory(root->right);
delete root;
root = nullptr;
return nullptr;
}总代码
#pragma once
/*二叉搜索树*/
/* k模型 */
// 查看是否存在
namespace key
{
template<typename K>
struct BSNode
{
BSNode<K>* left;
BSNode<K>* right;
K key;
BSNode(const K& k)
: left(nullptr)
, right(nullptr)
, key(k)
{}
};
template<typename K>
class BSTree
{
typedef BSNode<K> Node;
public:
BSTree()
{}
BSTree(const BSTree<K>& tree)
{
_root = Copy(tree._root);
}
BSTree<K>& operator=(BSTree tree)
{
swap(*this, tree);
return *this;
}
bool Insert(const K& k)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (k < cur->key)
{
cur = cur->left;
}
else if (k > cur->key)
{
cur = cur->right;
}
else
return false;
}
Node* node = new Node(k);
if (parent == nullptr)
_root = node;
else if (k > parent->key)
{
parent->right = node;
}
else
parent->left = node;
return true;
}
void Erase(const K& k)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// parent = cur;
// 不可以放在这里
if (k < cur->key)
{
parent = cur;
cur = cur->left;
}
else if (k > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
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;
}
delete cur;
}
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;
}
delete cur;
}
else
{
// 找右子树的最左节点
Node* parent = cur;//注意！！！！！！！要等于cur
Node* subLeft = cur->right;
while (subLeft->left)
{
parent = subLeft;
subLeft = subLeft->left;
}
swap(subLeft->key, cur->key);
if (subLeft == parent->left)
{
parent->left = subLeft->right;
delete subLeft;
}
else
{
parent->right = subLeft->right;
delete subLeft;
}
}
return;
}
}
}
bool Find(const K& k)
{
Node* cur = _root;
while (cur)
{
if (k < cur->key)
{
cur = cur->left;
}
else if (k > cur->key)
{
cur = cur->right;
}
else
return true;
}
return false;
}
// 因为外界不知道root，所以这样子就省的再写一个函数去获取_root了
void Inorder()
{
_Inorder(_root);
}
bool FindR(const K& k)
{
return _FindR(_root, k);
}
bool InsertR(const K& k)
{
return _InsertR(_root, k);
}
bool EraseR(const K& k)
{
return _EraseR(_root, k);
}
~BSTree()
{
Destory(_root);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
_root = new Node(root->key);
_root->left = Copy(root->left);
_root->right = Copy(root->right);
return _root;
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->left);
cout << root->key << ' ';
_Inorder(root->right);
}
bool _FindR(Node* root, const K& k)
{
if (root == nullptr)
return false;
if (k > root->key)
return _FindR(root->right);
else if (k < root->key)
return _FindR(root->left);
else
return true;
}
bool _InsertR(Node*&/*这样子就不用记住父节点也能插入*/ root, const K& k)
{
if (root == nullptr)
{
root = new Node(k);
return true;
}
if (k > root->key)
return _InsertR(root->right, k);
else if (k < root->key)
return _InsertR(root->left, k);
else
return false;
}
bool _EraseR(Node*& root, const K& k)
{
if (root == nullptr)
return false;
if (root->key < k)
return _EraseR(root->right, k);
else if (root->key > k)
return _EraseR(root->left, k);
else
{
if (root->left == nullptr)
{
Node* del = root;
root = root->right;/**/
delete del;
}
else if (root->right == nullptr)
{
Node* del = root;
root = root->left;/**/
delete del;
}
else
{
// 找右子树最左边的
Node* subLeft = root->right;
while (subLeft->left)
{
subLeft = subLeft->left;
}
swap(root->key, subLeft->key);
return _EraseR(root->right, k);/**/
}
}
}
Node* Destory(Node*& root)
{
if (root == nullptr)
return nullptr;
root->left = Destory(root->left);
root->right = Destory(root->right);
delete root;
root = nullptr;
}
private:
Node* _root = nullptr;
};
}拓展
key、value结构
当为kv结构时，只需将BNTreeNode部分、Insert部分修改就好
结语
该代码使用了一些C++技巧，简述就是一下部分，若大家回想不起来可以去相关代码地方去看哦
1、传参为引用 和 拷贝 的灵活使用
【注】 当为引用时：减少拷贝时间，提高效率 当为拷贝时：对于重载=这种运算符时，可以及时销毁临时变量
2、返回值为引用 和 拷贝 的灵活使用
【注】 使用引用返回的场景：出了该作用域该对象仍然存在
3、了解NULL的底层，为什么nullptr好
【注】 NULL的底层实际是对数字0的强转指针的define，有时候容易出问题，所以我们尽量使用nullptr
4、提供给外部的接口种调用内部接口的原因
【注】 外部无法得知内部消息（如二叉搜索树的根节点），这样子可以用外部接口中调用内部接口就会方便很多，也不需要专门写一堆用来获取内部属性的接口（如该代码的GetRoot这种函数）
好啦~~，到这里就圆满结束啦，恭喜你今天又进步了一点点哦ε=ε=ε=(~￣▽￣)~，如果对我的文章较为满意的话，欢迎点赞收藏和关注哦，后续我将更新《AVL树》《红黑树》《STL的模拟实现》部分，敬请期待哦
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-08-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
