二叉搜索树
一、前言
二、模拟实现
1.构建树的单个节点
2.二叉搜索树的概念
3.构造函数与析构函数
4.赋值与拷贝构造
5.实现插入
6.实现删除
7.实现查找
8.实现遍历
三、源码及部分测试用例
一、前言
二叉搜索树，和普通的二叉树不同，它除了拥有链表的快速插入的功能，也拥有比肩数组般快速查找的能力。本文主要模拟实现二叉搜索树的增添、删除、查找以及遍历的功能，编译器环境为VS2019。
二、模拟实现
1.构建树的单个节点
二叉搜索树的单个节点和普通二叉树一样，都是用结构体存储内容，同时使用左右指针指向左右子树，树只要保存最初的根节点即可：
// 树节点
// K表示数据存储类型，V表示对类容的进一步扩展
// 扩展可以是注释，也可以是其他内容
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:
private:
Node* _root;
}
2.二叉搜索树的概念
二叉搜索树相比于普通二叉树有两点不同：
（1）二叉搜索树的所有根节点都比自己的左子树及其子树存储的值要大，同时比自己的右子树及其子树存储的值要小；
（2）二叉搜索树中不能存在相同的值节点。
3.构造函数与析构函数
因为树初始的存储中只有一个根节点，构造函数中根节点给一个空即可；而二叉树的析构函数则要用到深度优先遍历——因为使用前序中序delete掉根节点后无法再访问到子树，就会造成严重数据泄露。
// 初始化
BSTree()
:_root(nullptr)
{}
// 析构
~BSTree()
{
Destory(_root);
}
void Destory(Node*& del)
{
if (del == nullptr)
return;
Destory(del->left);
Destory(del->right);
delete del;
del = nullptr;
}
4.赋值与拷贝构造
给二叉树的赋值类似于拷贝构造，倒不如说一模一样，赋值和拷贝构造都是给new出来一串一样的树。
不过有两种实现方法：一种是传统写法，构建一个Copy函数，传入*this指向的树和参数引用的树，通过广度优先遍历一一拷贝过去；另一种则简单粗暴，传入的参数为实参拷贝构造后的树，直接交换*this的根节点和构造的树即可，函数结束时栈帧销毁同时形参自动调用析构函数，而此时的形参是交换后的*this指向的树根节点，不用管即可，当然，这只适用于赋值，因为要调用拷贝构造函数。
具体实现如下：
// 拷贝构造
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
// 赋值
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
5.实现插入
首先来分析一下，二叉搜索树的要求，要求其左子树比根节点小，右子树比根节点大——因此，每一次比较都是一次大小的筛选——比较大小后选择进入比根节点更小的左树，或进入更大的右树，这也是在不断缩小范围，直到不可缩小大小范围为止，此时是不能继续比较之时，即比较根节点后进入的子树为空之时，插入空节点即可。
// 插入
bool Insert(const K& key, const V& value)
{
// 排除空
if (_root == nullptr)
{
Node* New = new Node(key, value);
_root = New;
return true;
}
// 往下查找
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->left;
}
else
return false;
}
// 放置新节点
cur = new Node(key, value);
if (key > parent->_key)
{
parent->right = cur;
}
else
{
parent->left = cur;
}
return true;
}
6.实现删除
二叉搜索树的删除是最麻烦的，我们一点点来分析，删除的节点共有四种情况：左右子树都为空；仅有左树为空；仅有右树为空；左右子树都不为空。
若左右子树都为空，将删除节点的父节点直接指向空即可；
若仅有左子树或右子树为空，此时将父节点指向删除节点的左子树或右子树即可——这种实现方式叫做托管法；
若左右子树都不为空，此时我们应该让父节点指向哪个节点呢？我们有两种选择方案，取删除节点左树的最大值，亦或是取右树节点的最小值。但他们都存在一个问题，将节点挪上来后，他的子树该怎么办？此处我们取左树最大值来举例，我们找到删除节点左树最大值时，它有一个特性，即没有右子树，最多只有左子树，我们只要将这个节点的左树交给这个节点的父节点托管即可。（取右树最小值时差不多同理）
// 删除
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->left;
}
// 找到要删除的节点时
else
{
// 左右节点为空：托管
if (cur->left == nullptr)
{
// 判断根节点
if (cur == nullptr)
{
_root = cur->right;
}
// 此时不知道cur为左节点还是右节点
if (parent->right = cur)
{
parent->right = cur->right;
}
else
{
parent->left = cur->right;
}
}
else if (cur->right == nullptr)
{
// 判断根节点
if (cur == nullptr)
{
_root = cur->left;
}
// 此时不知道cur为左节点还是右节点
if (parent->right = cur)
{
parent->right = cur->left;
}
else
{
parent->left = cur->left;
}
}
// 左右节点都不为空：替代法
else
{
// 获取左子树最大值
parent = cur;
Node* LeftMax = cur->left;
while (LeftMax->right)
{
parent = LeftMax;
LeftMax = LeftMax->right;
}
// 交换节点内容
std::swap(cur->_key, LeftMax->_key);
std::swap(cur->_value, LeftMax->_value);
// 处理LeftMax的左子树
if (parent->left == LeftMax)
{
parent->left = LeftMax->left;
}
else
{
parent->right = LeftMax->left;
}
cur = LeftMax;
}
delete cur;
cur = nullptr;
return true;
}
}
return false;
}
7.实现查找
查找没什么好说的，我们在前面已经实现过了，这里我们设置返回值为查找到的节点指针。
// 查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->right;
}
else if (key < cur->_key)
{
cur = cur->left;
}
else
return cur;
}
// 没找到
return nullptr;
}
8.实现遍历
二叉搜索树的遍历很简单，与它的特性有关，使用中序遍历即可，代码实现如下：
// 中序遍历
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void _Inorder(Node* node)
{
if (node == nullptr)
return;
_Inorder(node->left);
cout << node->_key << ":" << node->_value << " ";
_Inorder(node->right);
}
三、源码及部分测试用例
#pragma once
// 树节点
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)
{}
};
// 搜索二叉树
// 1.所有根节点比左树大，比右树小
// 2.不能有相同的值节点
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
// 初始化
BSTree()
:_root(nullptr)
{}
// 拷贝构造
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destory(_root);
}
// 插入
bool Insert(const K& key, const V& value)
{
// 排除空
if (_root == nullptr)
{
Node* New = new Node(key, value);
_root = New;
return true;
}
// 往下查找
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->left;
}
else
return false;
}
// 放置新节点
cur = new Node(key, value);
if (key > parent->_key)
{
parent->right = cur;
}
else
{
parent->left = cur;
}
return true;
}
// 查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->right;
}
else if (key < cur->_key)
{
cur = cur->left;
}
else
return cur;
}
return nullptr;
}
// 删除
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->left;
}
// 找到要删除的节点
else
{
// 左右节点为空：托管
if (cur->left == nullptr)
{
// 判断根节点
if (cur == nullptr)
{
_root = cur->right;
}
// 此时不知道cur为左节点还是右节点
if (parent->right = cur)
{
parent->right = cur->right;
}
else
{
parent->left = cur->right;
}
}
else if (cur->right == nullptr)
{
// 判断根节点
if (cur == nullptr)
{
_root = cur->left;
}
// 此时不知道cur为左节点还是右节点
if (parent->right = cur)
{
parent->right = cur->left;
}
else
{
parent->left = cur->left;
}
}
// 左右节点都不为空：替代法
else
{
// 获取左子树最大值
parent = cur;
Node* LeftMax = cur->left;
while (LeftMax->right)
{
parent = LeftMax;
LeftMax = LeftMax->right;
}
// 交换节点内容
std::swap(cur->_key, LeftMax->_key);
std::swap(cur->_value, LeftMax->_value);
// 处理LeftMax的左子树
if (parent->left == LeftMax)
{
parent->left = LeftMax->left;
}
else
{
parent->right = LeftMax->left;
}
cur = LeftMax;
}
delete cur;
cur = nullptr;
return true;
}
}
return false;
}
// 中序遍历
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
Node* _root;
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* NewRoot = new Node(root);
NewRoot->_key = root->_key;
NewRoot->left = Copy(root->left);
NewRoot->right = Copy(root->right);
return NewRoot;
}
void Destory(Node*& del)
{
if (del == nullptr)
return;
Destory(del->left);
Destory(del->right);
delete del;
del = nullptr;
}
void _Inorder(Node* node)
{
if (node == nullptr)
return;
_Inorder(node->left);
cout << node->_key << ":" << node->_value << " ";
_Inorder(node->right);
}#pragma once
// 树节点
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)
{}
};
// 搜索二叉树
// 1.所有根节点比左树大，比右树小
// 2.不能有相同的值节点
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
// 初始化
BSTree()
:_root(nullptr)
{}
// 拷贝构造
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destory(_root);
}
// 插入
bool Insert(const K& key, const V& value)
{
// 排除空
if (_root == nullptr)
{
Node* New = new Node(key, value);
_root = New;
return true;
}
// 往下查找
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->left;
}
else
return false;
}
// 放置新节点
cur = new Node(key, value);
if (key > parent->_key)
{
parent->right = cur;
}
else
{
parent->left = cur;
}
return true;
}
// 查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->right;
}
else if (key < cur->_key)
{
cur = cur->left;
}
else
return cur;
}
return nullptr;
}
// 删除
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->left;
}
// 找到要删除的节点
else
{
// 左右节点为空：托管
if (cur->left == nullptr)
{
// 判断根节点
if (cur == nullptr)
{
_root = cur->right;
}
// 此时不知道cur为左节点还是右节点
if (parent->right = cur)
{
parent->right = cur->right;
}
else
{
parent->left = cur->right;
}
}
else if (cur->right == nullptr)
{
// 判断根节点
if (cur == nullptr)
{
_root = cur->left;
}
// 此时不知道cur为左节点还是右节点
if (parent->right = cur)
{
parent->right = cur->left;
}
else
{
parent->left = cur->left;
}
}
// 左右节点都不为空：替代法
else
{
// 获取左子树最大值
parent = cur;
Node* LeftMax = cur->left;
while (LeftMax->right)
{
parent = LeftMax;
LeftMax = LeftMax->right;
}
// 交换节点内容
std::swap(cur->_key, LeftMax->_key);
std::swap(cur->_value, LeftMax->_value);
// 处理LeftMax的左子树
if (parent->left == LeftMax)
{
parent->left = LeftMax->left;
}
else
{
parent->right = LeftMax->left;
}
cur = LeftMax;
}
delete cur;
cur = nullptr;
return true;
}
}
return false;
}
// 中序遍历
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
Node* _root;
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* NewRoot = new Node(root);
NewRoot->_key = root->_key;
NewRoot->left = Copy(root->left);
NewRoot->right = Copy(root->right);
return NewRoot;
}
void Destory(Node*& del)
{
if (del == nullptr)
return;
Destory(del->left);
Destory(del->right);
delete del;
del = nullptr;
}
void _Inorder(Node* node)
{
if (node == nullptr)
return;
_Inorder(node->left);
cout << node->_key << ":" << node->_value << " ";
_Inorder(node->right);
}
public:
void TestBSTree1()
{
BSTree<string, string> dict;
dict.Insert("insert", "插入");
dict.Insert("sort", "排序");
dict.Insert("right", "右边");
dict.Insert("date", "日期");
string str;
while (cin >> str)
{
BSTreeNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "无此单词" << endl;
}
}
}
void TestBSTree2()
{
// 统计水果出现的次数
string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
BSTree<string, int> countTree;
for (auto& str : arr)
{
auto ret = countTree.Find(str);
if (ret == nullptr)
{
countTree.Insert(str, 1);
}
else
{
ret->_value++;
}
}
countTree.Inorder();
}
};
};
