目录
🎇二叉搜索树
🎆二叉搜索树概念
我们知道树是非线性结构的，但是在二叉树知识中我们可以创建某种类型的树，对它进行~增~删·~查~改。Such as BInarySerachTree我们叫它二叉搜索树，一般及简写为BSTree。
?character：
- 若它的 左子树不为空，则左树上的所有节点的值都小于根节点的值~
- 若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值·~
- 它的左右子树也分别二叉搜索树~
这个树长这个样子👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇
我们可以通过这张图观察到它的性质·~~~
这么一颗神奇的树是怎么是实现的呢~~我们通过代码了解一下👇👇👇👇👇👇👇👇👇👇👇
🎇二叉树的实现
🎆二叉树的创建
//树的左右节点，以及节点的值~~
template <class T>
struct BinarySerachTree
{
public:
BinarySerachTree(const T& val)
:right(nullptr)
, left(nullptr)
, _val(val)
{}
BinarySerachTree<T>* left;
BinarySerachTree<T>* right;
T _val;
};
//树的根，我们也给他一个类型，方便写函数~~
template<class T>
struct BinaryTreeRoot
{
public:
typedef BinarySerachTree<T> Node;
BinaryTreeRoot()
:_root(nullptr)
{}
private：
Node*_root;
}以上二叉树就简单的创建好了~~我们试着往里面插入一些数据吧👇👇👇👇👇👇👇👇👇👇
🎆二叉树的插入~（非递归）
我们在插入直线需要考虑两种情况
- case：1? 树为空的话我们直接进行插入~~
- case：2? 树不为空，进行遍历，查找左右子树~??
树为空：
bool Insert(const T& val)
{
//树为空直接进行插入，然后返回~~
if (!_root)
{
_root = new Node(val);
return true;
}
}
int main()
{
BinaryTreeRoot<int> root;
int arr[] = {5,3,4,1,7,8,2,6,0,9};
for (auto e : arr)
{
root.Insert(e);
}
}
树不为空：
? ? ?我们要插入4这个节点~~具体操作就是首先遍历根->左节点or右节点->找到了就new一个新节点出来然后进行插入👇👇👇👇👇👇👇👇👇👇👇👇👇👇
bool Insert(const T& val)
{
if (!_root)
{
_root = new Node(val);
return true;
}
//创建临时变量来遍历这个树·~~再遍历树的同时我们还需要记录要插入
//节点父亲的位置，来进行链接
Node* cur = _root;
Node* parent = nullptr;
//cur为空时就说明找到了合适的插入位置~~
while (cur)
{
if (val > cur->_val)
{
parent = cur;
cur = cur->right;
}
else if(val<cur->_val)
{
parent = cur;
cur = cur->left;
}
else
{
return false;
}
}
//让cur=new出来的新节点，我们需要注意的是要插入的数据大于还是
//小于父亲节点，然后决定放在左边还是右边~~
cur = new Node(val);
if (val > parent->_val)
{
parent->right = cur;
}
else
{
parent->left = cur;
}
return true;
}🎆中序遍历
? ? 中序遍历可以让这棵树以有序的序列进行打印~~
void _Inorder(Node*root)
{
if (!root)
{
return;
}
_Inorder(root->left);
cout << root->_val << " ";
_Inorder(root->right);
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}我们之所以是要用两个函数来实现是因为，我们从外面不容易直接访问成员变量，所以定义一个子函数来进行中序遍历~~~Look👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇我们一棵简单的树就创建好了~~
?我们再来进行一些删除操作~~~
🎆删除（非递归）~
我们要进行删除。需要考虑几种情况~
- ?删除的节点只有左子树或者又子树，比如8这个节点~根只有左子树或者右子树的根节点~
- 终端节点直接删除，比较简单~
- 左右子树都不为空的节点~
? ? 我们只看极端情况~比如我们需要删除8这个节点~
? ? 首先遍历这棵树，设定一个父节点->找到这个节点->判断这个节点是以上哪种情况->准备删除~
🎆exception:?
要被删除的节点有左右子树~替换法进行删除~使用左子树的最大值or右子树的最小值进行替换然后删除掉~这里需要考虑到的情况是，比如说右子树的最小节点~有可能会有右子树的存在，这种情况就需要注意一下，我们还需要一个父亲节点来标记，右子树的最小节点的父亲，使用托孤法来进行链接关系~
else
{
//这里我们就需要设定一个父亲节点来进行记录
Node* minparent = cur;
Node* min = cur->right;
//遍历找到右子树的最小节点~
while (min->left)
{
minparent = min;
min = min->left;
}
//找到之后直接将值付给要被删除的节点~
cur->_val = min->_val;
//判断一下是否有左节点或者右节点~有的话链接一下，然后删除~
if (minparent->left == min)
{
minparent->left = min->right;
}
else
{
minparent->right = min->right;
}
delete min;
min = nullptr;
} bool erase(const T& val)
{
if (!_root)
{
return false;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
//遍历给定节点
if (val > cur->_val)
{
parent = cur;
cur = cur->right;
}
else if (val < cur->_val)
{
parent = cur;
cur = cur->left;
}
//准备删除
else
{
//只有右子树
if (cur->left == nullptr)
{
//判断一下是不是根节点
if (parent == nullptr)
{
_root = cur->right;
delete cur;
return false;
}
//判断是要被删除的节点是父亲的左子树还是右子树
if (cur == parent->right)
{
parent->right = cur->right;
}
if (cur == parent->left)
{
parent->left = cur->right;
}
delete cur;
cur = nullptr;
}
//只有左子树
else if (cur->right == nullptr)
{
if (parent == nullptr)
{
_root = cur->left;
delete cur;
return false;
}
if (cur == parent->right)
{
parent->right = cur->left;
}
if (cur == parent->left)
{
parent->left = cur->left;
}
delete cur;
cur = nullptr;
}
//既有左子树也有右子树，就使用替换删除法，使用右子树的最小值，或者左子树的最大值进行替换~
else
{
Node* minparent = cur;
Node* min = cur->right;
while (min->left)
{
minparent = min;
min = min->left;
}
cur->_val = min->_val;
if (minparent->left == min)
{
minparent->left = min->right;
}
else
{
minparent->right = min->right;
}
delete min;
min = nullptr;
}
}
}
return false;
}👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆基本的插入删除就完成了，我们再看一些Recursion的操作吧👇👇👇👇👇👇👇👇👇
🎆Recursion edition
?递归插入
递归插入思想我们还是对这棵树进行遍历~找到需要插入的位置进行插入，比较简单👇👇👇👇👇
bool InsertR(const T& val)
{
return _InsertR(_root, val);
}
//递归插入
bool _InsertR(Node*& root, const T& val)
{
//如果为空直接new新节点进行插入
if (!root)
{
root = new Node(val);
return true;
}
//递归遍历是属于哪个子树~~
if (val > root->_val)
{
return _InsertR(root->right, val);
}
else if (val < root->_val)
{
return _InsertR(root->left, val);
}
else
{
return false;
}
}?递归删除
递归删除我们需要考虑的情况也是有左右子树的情况~👇👇👇👇👇👇👇👇
bool eraseR(const T& val)
{
return _eraseR(_root, val);
}
bool _eraseR(Node*&root, const T& val)
{
if (!root)
{
return false;
}
if (val > root->_val)
{
return _eraseR(root->right, val);
}
else if (val < root->_val)
{
return _eraseR(root->left, val);
}
else
{
//找到了就开始进行删除~需要考虑被删除的节点的左右子树是否为空~
Node* del = root;
//传引用过的目的就是为了解决这里面的删除情况~直接让
//root=root->的right。又因为root是上一个的引用~~
if (root->left == nullptr)
{
root = root->right;
}
else if (root->right == nullptr)
{
root = root->left;
}
//左右都不为空的情况需要注意~使用替换法进行删除~
else
{
Node* min = root->right;
while (min->left)
{
min = min->left;
}
swap(min->_val, root->_val);
return _eraseR(root->right, val);
}
delete del;
return true;
}
}🎆二叉树的KVAl模型
我们叫它二叉搜索树是是因这颗树的效率是非常高的，最坏情况下时间复杂度为logN。那么我们就可使用这棵树来进行kval的模型创建~~
?kval模型介绍
每一个关键码
key
，都有与之对应的值
Value
，即
<Key, Value>
的键值对
。该种方式在现实生
活中非常常见：比如
英汉词典就是英文与中文的对应关系
，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>
就构成一种键值对；再比如
统计单词次数
，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是
<word, count>
就构成一种键值对
。比如：实现一个简单的英汉词典dict~~~~👇👇👇👇👇👇👇👇👇👇👇👇👇👇
字典树的模型比较容易创建~只是在原来的基础上再给节点申请一个值用来存放~
template <class T,class K>
struct BinarySerachTree
{
public:
BinarySerachTree(const T& val,const K&k)
:right(nullptr)
, left(nullptr)
, _val(val)
,_k(k)
{}
BinarySerachTree<T,K>* left;
BinarySerachTree<T,K>* right;
T _val;
K _k;
};而且对这棵树进行添加，控制相应的K的值，比较也是只比较K的值~
?Kval全码实现~
namespace qzh
{
template <class T,class K>
struct BinarySerachTree
{
public:
BinarySerachTree(const T& val,const K&k)
:right(nullptr)
, left(nullptr)
, _val(val)
,_k(k)
{}
BinarySerachTree<T,K>* left;
BinarySerachTree<T,K>* right;
T _val;
K _k;
};
template<class T,class K>
struct BinaryTreeRoot
{
public:
typedef BinarySerachTree<T,K> Node;
BinaryTreeRoot()
:_root(nullptr)
{}
//递归插入
//bool InsertR(const T& val)
//{
// return _InsertR(_root, val,);
//}
递归插入
//bool _InsertR(Node*& root, const T& val)
//{
// if (!root)
// {
// root = new Node(val);
// return true;
// }
// if (val > root->_val)
// {
// return _InsertR(root->right, val);
// }
// else if (val < root->_val)
// {
// return _InsertR(root->left, val);
// }
// else
// {
// return false;
// }
//}
//常规插入
bool Insert(const T& val,const K&k)
{
if (!_root)
{
_root = new Node(val,k);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (val > cur->_val)
{
parent = cur;
cur = cur->right;
}
else if (val < cur->_val)
{
parent = cur;
cur = cur->left;
}
else
{
return false;
}
}
cur = new Node(val,k);
if (val > parent->_val)
{
parent->right = cur;
}
else
{
parent->left = cur;
}
return true;
}
Node* find(const T& val)
{
return _find(_root, val);
}
Node* _find(Node* root, const T& val)
{
if (!root)
{
return nullptr;
}
if (val > root->_val)
{
return _find(root->right, val);
}
else if (val < root->_val)
{
return _find(root->left, val);
}
else
{
return root;
}
}
//常规删除
bool erase(const T& val)
{
if (!_root)
{
return false;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
//遍历给定节点
if (val > cur->_val)
{
parent = cur;
cur = cur->right;
}
else if (val < cur->_val)
{
parent = cur;
cur = cur->left;
}
//准备删除
else
{
//只有右子树
if (cur->left == nullptr)
{
//判断一下是不是根节点
if (parent == nullptr)
{
_root = cur->right;
delete cur;
return false;
}
//判断是要被删除的节点是父亲的左子树还是右子树
if (cur == parent->right)
{
parent->right = cur->right;
}
if (cur == parent->left)
{
parent->left = cur->right;
}
delete cur;
cur = nullptr;
}
//只有左子树
else if (cur->right == nullptr)
{
if (parent == nullptr)
{
_root = cur->left;
delete cur;
return false;
}
if (cur == parent->right)
{
parent->right = cur->left;
}
if (cur == parent->left)
{
parent->left = cur->left;
}
delete cur;
cur = nullptr;
}
//既有左子树也有右子树，就使用替换删除法，使用右子树的最小值，或者左子树的最大值进行替换~
else
{
Node* minparent = cur;
Node* min = cur->right;
while (min->left)
{
minparent = min;
min = min->left;
}
cur->_val = min->_val;
cur->_k = min->_k;
if (minparent->left == min)
{
minparent->left = min->right;
}
else
{
minparent->right = min->right;
}
delete min;
min = nullptr;
}
}
}
return false;
}
void _Inorder(Node* root)
{
if (!root)
{
return;
}
_Inorder(root->left);
cout << root->_val << " "<<root->_k<<" ";
cout << endl;
_Inorder(root->right);
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
//bool eraseR(const T& val)
//{
// return _eraseR(_root, val);
//}
//
//bool _eraseR(Node*&root, const T& val)
//{
// if (!root)
// {
// return false;
// }
// if (val > root->_val)
// {
// return _eraseR(root->right, val);
// }
// else if (val < root->_val)
// {
// return _eraseR(root->left, val);
// }
// else
// {
// Node* del = root;
// if (root->left == nullptr)
// {
// root = root->right;
// }
// else if (root->right == nullptr)
// {
// root = root->left;
// }
// else
// {
// Node* min = root->right;
// while (min->left)
// {
// min = min->left;
// }
// swap(min->_val, root->_val);
// return _eraseR(root->right, val);
// }
// delete del;
// return true;
// }
//
//}
private:
Node* _root;
};
/*void test()
{
BinaryTreeRoot<int> root;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
root.Insert(e);
}
root.Inorder();
root.erase(5);
root.Inorder();
BinarySerachTree<int>* ret = root.find(7);
cout << ret->_val << endl;
}*/
/*void test1()
{
BinaryTreeRoot<int> root;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
root.Insert(e);
}
root.Inorder();
}*/
//void test2()
//{
// BinaryTreeRoot<int> root;
// int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
// for (auto e : arr)
// {
// root.InsertR(e);
// }
// root.Inorder();
// /*BinarySerachTree<int>* ret = root.find(6);
// cout << ret->_val << endl;*/
//}
/*void test3()
{
BinaryTreeRoot<int> root;
int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
for (auto e : arr)
{
root.InsertR(e);
}
root.Inorder();
for (auto e : arr)
{
root.eraseR(e);
root.Inorder();
}
}*/
void dictest1()
{
BinaryTreeRoot<string, string> dict;
dict.Insert("curry", "库里");
dict.Insert("sort", "排序");
dict.Insert("stephen", "斯蒂芬");
dict.Insert("massacre", "屠杀");
dict.Insert("magnitude", "重要性");
dict.Insert("magnetic", "磁的");
//dict.Inorder();
string str;
while (cin >> str)
{
BinarySerachTree<string, string>* ret = dict.find(str);
if (ret)
{
cout << "对应中文为->" << ret->_k << endl;
}
else
{
cout << "不存在此单词~" << endl;
}
}
}
}🔨二叉树基本类型介绍到这里~~See you~
