数据结构高阶–二叉搜索树（原理+实现）
二叉搜索树
概念
二叉搜索树又称为二叉排序树，因为这棵树的中序遍历是有序的。二叉搜索树总结起来有以下几个性质：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于于根节点的值
- 它的左右子树都是二叉搜索树
- 这棵树中没有重复的元素
举个例子：
二叉搜索树的实现
基本框架
template
struct BST_Node
{
BST_Node* left;
BST_Node* right;
K key;
V value;
//构造函数
BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value)
{}
};
template
class BST_Tree
{
typedef BST_Node Node;
public:
private:
Node* root = nullptr;
};
要实现的接口
bool Insert(const K& key,const V& value);//二叉搜索树的插入
void InOrder();//打印功能，采用中序遍历（递归）
Node* Find(const K& key);//二叉搜索树的查找
bool Erase(const K& key);//二叉搜索树的删除
二叉搜索树的插入
插入分为下面几个步骤：
- 先判断树是否为空，为空就让要插入的这个节点作为根节点，然后结束
- 确定要插入节点的位置
- 用一个cur记录当前节点，parent记录父节点
- 要插入节点的值如果比当前节点的值小，cur就往左走，如果比当前节点的值大，就往右子树走，如果等于就返回false，表面这棵树中有这个数据，不需要插入
//二叉搜索树的插入
bool Insert(const K& key,const V& value)
{
//没有节点的时候就是根节点
if (root == nullptr)
{
root = new Node(key,value);
return true;
}
//用一个父节点记录cur的上一个节点
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
parent = cur;
//小于往左走
if (key key)
{
cur = cur->left;
}
else if (key > cur->key)
{
cur = cur->right;
}
else
return false;
}
cur = new Node(key,value);
//判断应该插在父节点的左边还是右边
if (cur->key key)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
return true;
}
打印二叉搜索树（中序遍历）
//中序遍历（递归）
void InOrder()
{
_InOrder(root);
cout left);
cout key value right);
}
}
二叉搜索树的查找
查找的步骤如下：（和插入的步骤有些类似）
- 如果查找值key比当前节点的值小，就往左子树走
- 如果查找值key比当前节点的值大，就往右子树走
- 如果查找值key和当前节点的值相等，就返回当前节点的指针
//二叉搜索树的查找
Node* Find(const K& key)
{
if (root == nullptr)
{
return nullptr;
}
Node* cur = root;//遍历结点
while (cur)
{
//小于往左走
if (cur->key > key)
{
cur = cur->left;
}
else if (cur->key right;
}
else
{
return cur;
}
}
return nullptr;
}
二叉搜索树的删除（难）
分四种情况：我们一个一个来讨论
以下面这颗树为例：
情景一：
情景二：
还要分析一种特殊的情况，就是此时2没有父亲节点，也就是自己为根时，看下面如何操作
情景三：
该节点如果为根节点，就让自己的右孩子变成根节点
情景四：
总结： 一共有四种情况，但是情况1可以归为情况3，因为它也是左为空，所以整体处理下来是三种情况
//二叉搜索树的删除
bool Erase(const K& key)
{
//树为空，删除失败
if (root == nullptr)
{
return false;
}
//parent始终是cur的父亲节点
//cur就是要找的删除的当前节点
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
//小于往左边走
if (key key)
{
parent = cur;
cur = cur->left;
}
else if (key > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
// 找到了，开始删除
// 1.左右子树都为空，直接删除，可以归类为左为空
// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左
// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
//当前情况是情景三，删除的节点它的左为空，右未知
if (cur->left == nullptr)
{
// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
// 根节点的话会导致parent为nullptr
if (root == cur)
{
root = root->right;
}
else
{
//左为空，父亲指向我的右
//判断cur在父亲的左还是右
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
cur = nullptr;
}
//当前情况是情景二，删除节点它的右为空，左未知
else if (cur->right == nullptr)
{
if (root ==cur )
{
root = root->left;
}
else
{
//右为空，父亲指向我的左
//判断cur在父亲的左还是右
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
}
delete cur;
cur = nullptr;
}
//只剩下情景四
else
{
//找右子树中最小的节点，当前cur就是要删除的节点
Node* rightMinParent = cur;
Node* rightMin = cur->right;//去右子树找最小的节点
while (rightMin->left)
{
rightMinParent = rightMin;
rightMin = rightMin->left;
}
//替代删除
cur->key = rightMin->key;
//转化成了情景三，左孩子为空
if (rightMinParent->left == rightMin)
rightMinParent->left = rightMin->right;
else
rightMinParent->right = rightMin->right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
完整代码以及测试
#define _CRT_SECURE_NO_WARNINGS
#include //引入头文件
#include//C++中的字符串
using namespace std; //标准命名空间
template
struct BST_Node
{
BST_Node* left;
BST_Node* right;
K key;
//构造函数
BST_Node(const K& key):left(nullptr),right(nullptr),key(key)
{}
};
template
class BST_Tree
{
typedef BST_Node Node;
public:
//二叉搜索树的插入
bool Insert(const K& key)
{
//没有节点的时候就是根节点
if (root == nullptr)
{
root = new Node(key);
return true;
}
//用一个父节点记录cur的上一个节点
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
parent = cur;
//小于往左走
if (key key)
{
cur = cur->left;
}
else if (key > cur->key)
{
cur = cur->right;
}
else
return false;
}
cur = new Node(key);
//判断应该插在父节点的左边还是右边
if (cur->key key)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
return true;
}
//中序遍历（递归）
void InOrder()
{
_InOrder(root);
cout left);
cout key right);
}
}
//二叉搜索树的查找
Node* Find(const K& key)
{
if (root == nullptr)
{
return nullptr;
}
Node* cur = root;//遍历结点
while (cur)
{
//小于往左走
if (cur->key > key)
{
cur = cur->left;
}
else if (cur->key right;
}
else
{
return cur;
}
}
return nullptr;
}
//二叉搜索树的删除
bool Erase(const K& key)
{
//树为空，删除失败
if (root == nullptr)
{
return false;
}
//parent始终是cur的父亲节点
//cur就是要找的删除的当前节点
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
//小于往左边走
if (key key)
{
parent = cur;
cur = cur->left;
}
else if (key > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
// 找到了，开始删除
// 1.左右子树都为空，直接删除，可以归类为左为空
// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左
// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
//当前情况是情景三，删除的节点它的左为空，右未知
if (cur->left == nullptr)
{
// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
// 根节点的话会导致parent为nullptr
if (root == cur)
{
root = root->right;
}
else
{
//左为空，父亲指向我的右
//判断cur在父亲的左还是右
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
cur = nullptr;
}
//当前情况是情景二，删除节点它的右为空，左未知
else if (cur->right == nullptr)
{
if (root ==cur )
{
root = root->left;
}
else
{
//右为空，父亲指向我的左
//判断cur在父亲的左还是右
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
}
delete cur;
cur = nullptr;
}
//只剩下情景四
else
{
//找右子树中最小的节点，当前cur就是要删除的节点
Node* rightMinParent = cur;
Node* rightMin = cur->right;//去右子树找最小的节点
while (rightMin->left)
{
rightMinParent = rightMin;
rightMin = rightMin->left;
}
//替代删除
cur->key = rightMin->key;
//转化成了情景三，左孩子为空
if (rightMinParent->left == rightMin)
rightMinParent->left = rightMin->right;
else
rightMinParent->right = rightMin->right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
private:
Node* root = nullptr;
};
void TestBSTree()
{
BST_Tree bt;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
cout 二叉搜索树的应用
二叉搜索树有两种模型：
- K模型： K模型只有key值，节点只存储key值。这里主要应用就是查找判断某个元素在不在。
- KV模型： KV模型每个key值都对应着一个value，主要应用就是通过key找value。（我们平时查找单词就是通过中文找英文，或者通过英文找中文）
上面的测试代码是KV模型改成了K模型，接下来我们来看看KV模型的作用
#define _CRT_SECURE_NO_WARNINGS
#include //引入头文件
#include//C++中的字符串
using namespace std; //标准命名空间
template
struct BST_Node
{
BST_Node* left;
BST_Node* right;
K key;
V value;
//构造函数
BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value)
{}
};
template
class BST_Tree
{
typedef BST_Node Node;
public:
//二叉搜索树的插入
bool Insert(const K& key,const V& value)
{
//没有节点的时候就是根节点
if (root == nullptr)
{
root = new Node(key,value);
return true;
}
//用一个父节点记录cur的上一个节点
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
parent = cur;
//小于往左走
if (key key)
{
cur = cur->left;
}
else if (key > cur->key)
{
cur = cur->right;
}
else
return false;
}
cur = new Node(key,value);
//判断应该插在父节点的左边还是右边
if (cur->key key)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
return true;
}
//中序遍历（递归）
void InOrder()
{
_InOrder(root);
cout left);
cout key value right);
}
}
//二叉搜索树的查找
Node* Find(const K& key)
{
if (root == nullptr)
{
return nullptr;
}
Node* cur = root;//遍历结点
while (cur)
{
//小于往左走
if (cur->key > key)
{
cur = cur->left;
}
else if (cur->key right;
}
else
{
return cur;
}
}
return nullptr;
}
//二叉搜索树的删除
bool Erase(const K& key)
{
//树为空，删除失败
if (root == nullptr)
{
return false;
}
//parent始终是cur的父亲节点
//cur就是要找的删除的当前节点
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
//小于往左边走
if (key key)
{
parent = cur;
cur = cur->left;
}
else if (key > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
// 找到了，开始删除
// 1.左右子树都为空，直接删除，可以归类为左为空
// 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左
// 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
//当前情况是情景三，删除的节点它的左为空，右未知
if (cur->left == nullptr)
{
// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
// 根节点的话会导致parent为nullptr
if (root == cur)
{
root = root->right;
}
else
{
//左为空，父亲指向我的右
//判断cur在父亲的左还是右
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
cur = nullptr;
}
//当前情况是情景二，删除节点它的右为空，左未知
else if (cur->right == nullptr)
{
if (root ==cur )
{
root = root->left;
}
else
{
//右为空，父亲指向我的左
//判断cur在父亲的左还是右
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
}
delete cur;
cur = nullptr;
}
//只剩下情景四
else
{
//找右子树中最小的节点，当前cur就是要删除的节点
Node* rightMinParent = cur;
Node* rightMin = cur->right;//去右子树找最小的节点
while (rightMin->left)
{
rightMinParent = rightMin;
rightMin = rightMin->left;
}
//替代删除
cur->key = rightMin->key;
//转化成了情景三，左孩子为空
if (rightMinParent->left == rightMin)
rightMinParent->left = rightMin->right;
else
rightMinParent->right = rightMin->right;
delete rightMin;
rightMin = nullptr;
}
return true;
}
}
return false;
}
private:
Node* root = nullptr;
};
int main()
{
system("pause");
return EXIT_SUCCESS;
}
实例1
英汉字典
void TestBSTree_KV1()
{
// 创建一个简易的字典
BST_Tree dict;
dict.Insert("苹果", "apple");
dict.Insert("香蕉", "banana");
dict.Insert("橘子", "orange");
dict.Insert("葡萄", "grape");
dict.Insert("apple", "苹果");
dict.Insert("banana", "香蕉");
dict.Insert("orange", "橘子");
dict.Insert("grape", "葡萄");
string str;
while (cin >> str)
{
BST_Node* ret = dict.Find(str);
if (ret)
{
cout value 实例2
统计树
void TestBSTree_KV2()
{
// 统计水果个数
BST_Tree countTree;
string strArr[] = { "香蕉","水蜜桃","西瓜","苹果","香蕉" ,"西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" };
for (auto e : strArr)
{
BST_Node* ret = countTree.Find(e);
if (ret == nullptr)
{
// 第一次插入
countTree.Insert(e, 1);
}
else
{
ret->value++;
}
}
countTree.InOrder();
}
文章来源于互联网：数据结构高阶--二叉搜索树（原理+实现）
THE END
二维码