二叉搜索树--BinarySerachTree(BSTree)
目录
🎇二叉搜索树
🎆二叉搜索树概念
✨character：
🎇二叉树的实现
🎆二叉树的创建
🎆二叉树的插入~（非递归）
🎆中序遍历
🎆删除（非递归）~
🎆exception:
🎆Recursion edition
✨递归插入
✨递归删除
🎆二叉树的KVAl模型
✨kval模型介绍
✨Kval全码实现~
csdn主页
🎇二叉搜索树
🎆二叉搜索树概念
我们知道树是非线性结构的，但是在二叉树知识中我们可以创建某种类型的树，对它进行~增~删·~查~改。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~