企业全屏网站,叫人做国外公司网站让老外做好还是国内人做好,查询网站ftp地址,微信公众号手机网站开发文章目录 二叉搜索树二叉搜索树的模拟实现构造函数拷贝构造函数赋值运算符重载函数析构函数Insert循环递归 Erase循环递归 Find循环递归 二叉搜索树的应用K模型KV模型 完整代码普通版本递归版本 二叉搜索树
二叉搜索树又称为二叉排序树#xff0c;它或者是一棵空树#xff0… 文章目录 二叉搜索树二叉搜索树的模拟实现构造函数拷贝构造函数赋值运算符重载函数析构函数Insert循环递归 Erase循环递归 Find循环递归 二叉搜索树的应用K模型KV模型 完整代码普通版本递归版本 二叉搜索树
二叉搜索树又称为二叉排序树它或者是一棵空树或者是具有以下性质的二叉树
若它的左子树不为空 则左子树上所有结点的值都小于根结点的值。
若它的右子树不为空 则右子树上所有结点的值都大于根结点的值。
它的左右子树也分别是二叉搜索树。 二叉搜索树的模拟实现
构造函数 BSTree():_root(nullptr){}拷贝构造函数 BSTree(const BSTreeK t)//BSTree( BSTreeK *this , const BSTreeK t)//t1 t {_root Copy(t._root);}private:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* copyNode new Node(root-_key);//递归 copyNode-_left Copy(root-_left);copyNode-_right Copy(root-_right);return copyNode;}赋值运算符重载函数 //赋值重载 BSTreeK operator (BSTreeK t)//t1 t//深拷贝{swap(_root, t._root);return *this;}析构函数
~BSTree(){Destroy(_root);}private:void Destroy(Node* root) //引用的目的将每个节点释放后同时置空{//后序遍历 if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}Insert
核心思路
如果是空树则直接将插入结点作为二叉搜索树的根结点。
如果不是空树则按照二叉搜索树的性质进行结点的插入。 如果待插入结点的值根结点的值则需要将结点插入到左子树当中。 如果待插入结点的值根结点的值则需要将结点插入到右子树当中。 如果待插入结点的值等于根结点的值则插入失败。
循环
bool Insert(const K key ){//空树if (_root nullptr){_root new Node(key);return true;}//不是空树Node* parent nullptr;//找到父节点Node* cur _root;while (cur){//比较if (cur-_key key){//往右子树走parent cur;cur cur-_right;}else if (cur-_key key){//往左子树走parent cur;cur cur-_left;}else{return false;}}//插入节点cur new Node(key);//不知道parent在那一边,需要进一步判断if (parent-_key key){//parent在左边parent-_left cur;}else if (parent-_key key){//parent在右边parent-_right cur;}else{return false;}return true;}递归 bool InsertR(const K key)//递归版本{return _InsertR(_root, key);}private:bool _InsertR(Node* root, const K key) //引用的目的不用找父节点不需要用父节点比较大小{//结束条件if (root nullptr){root new Node(key);return true;}//往左子树走if (root-_key key){return _InsertR(root-_left, key);}//往右子树走else if (root-_key key){return _InsertR(root-_right, key);}else{return false;}}Erase
先找到需要删除的节点 需要删除的节点可能会有三种情况 1、待删除结点的左子树为空待删除结点的左右子树均为空包含在内 2、待删除结点的右子树为空。
1、2 两种情况被删除的节点都只有一个孩子
3、待删除结点的左右子树均不为空即被删除节点有两个孩子 使用替换法处理第3中情况 1、找替换节点替换节点一般是左子树的最大节点最右节点或者是右子树的最小节点最左节点 2、将替换的节点删除 特殊情况 循环 bool Erase(const K key){Node* parent nullptr;//待删除节点的父节点Node* cur _root;//待删除的节点//不是空树while (cur){//往左边走if (cur-_key key){parent cur;cur cur-_left;}//往右边走else if (cur-_key key){parent cur;cur cur-_right;}//找到待删除的节点else{//待删除节点的左子树为空 ,即一个孩子的情况if (cur-_left nullptr){//待删除节点是根节点if (cur _root){//将根节点改为待删除节点的右孩子_root cur-_right;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent-_right cur){parent-_right cur-_right;}else//parent-_left cur{parent-_left cur-_right;}}}//待删除节点的右子树为空 ,即一个孩子的情况else if (cur-_right nullptr){//待删除节点是根节点if (cur _root){//将根节点改为待删除节点的左孩子_root cur-_left;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent-_right cur){parent-_right cur-_left;}else//parent-_leftcur{parent-_left cur-_left;}}} else //待删除的节点的左右孩子都不为空 替换法左子树的最大节点即最右节点或者右子树的最小节点即最左节点,并且将替换的节点删除{//替换法//找替代节点Node* parent cur;//找左子树的最大节点,左子树的最大节点一定没有右孩子Node* leftMax cur-_left;while (leftMax-_right){parent leftMax; //记录leftMax的父节点防止删除leftMax时找不到该节点位置 //一直往右子树找leftMax leftMax-_right;}//左子树的最大节点和待删除节点替换swap(cur-_key, leftMax-_key);//重新改变链接关系//特殊情况 if (parent-_left leftMax){parent-_left leftMax-_left;}else//普通情况 parent-_right leftMax{parent-_right leftMax-_left;}cur leftMax;}//删除左子树的最大节点delete cur;return true;}}return false;}递归 bool EraseR(Node* _root, const K key)//递归版本{return _EraseR(_root, key);}private:bool _EraseR(Node* root, const K key)//引用的目的不用找父节点不需要用父节点比较大小{//结束条件if (root nullptr){return false;}//往左树找if (root-_key key){return _EraseR(root-_left, key);}//往右树找else if (root-_key key){return _EraseR(root-_right, key);}else//找到开始删除{Node* del root;//待删除节点的左子树为空 ,即一个孩子的情况if (root-_left nullptr){root root-_right;}//待删除节点的右子树为空 ,即一个孩子的情况else if (root-_right nullptr){root root-_left;}//待删除的节点的左右孩子都不为空 替换法左子树的最大节点即最右节点或者右子树的最小节点即最左节点,并且将替换的节点删除else{//找左子树最大节点Node* leftMax root-_left;//一直往左边找直到找到左子树最大节点while (root-_left){root root-_left;}//将左子树最大节点与被删除节点替换swap(leftMax-_key, root-_key);return _EraseR(root, key);}delete del;//?return true;}}Find
循环 bool Find(const K key){Node* cur _root;while (cur){if (cur-_left key){cur cur-_left;}else if (cur-_left key){cur cur-_right;}else{return false;}return true;}}递归 bool FindR(Node* _root, const K key)//递归版本{return _FindR(_root, key);}private:bool _FindR(Node* root, const K key){//结束条件if (root nullptr){return false;}if (root-_key key){return _FindR(root-_left, key);}else if (root-_key key){return _FindR(root-_right, key);}else{return true;}}二叉搜索树的应用
K模型
K模型即只有key作为关键码结构中只需存储key即可关键码即为需要搜索到的值。
比如给定一个单词判断该单词是否拼写正确。具体方式如下 void TestBSTree1(){BSTreestring, string dict;dict.InsertR(insert, 插入);dict.InsertR(sort, 排序);dict.InsertR(right, 右边);dict.InsertR(date, 日期);string str;while (cinstr){auto * ret dict.FindR(str);//auto ret dict.FindR(str);if (ret){cout ret-_value endl;}else{cout 无此单词 endl;}}}KV模型
KV模型对于每一个关键码key都有与之对应的值value即key, value的键值对。
英汉词典就是英文与中文的对应关系即word, Chinese就构成一种键值对。具体方式如下
1、以单词, 中文含义为键值对构建一棵二叉搜索树。注意二叉搜索树需要进行比较键值对比较时只比较key。 2、查询英文单词时只需给出英文单词就可以快速找到与其对应的中文含义。
完整代码
普通版本
#pragma once template class Kstruct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr),_right(nullptr),_key(key){}
};template class K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTree():_root(nullptr){}bool Insert(const K key ){//空树if (_root nullptr){_root new Node(key);return true;}//不是空树Node* parent nullptr;//找到父节点Node* cur _root;while (cur){//比较if (cur-_key key){//往右子树走parent cur;cur cur-_right;}else if (cur-_key key){//往左子树走parent cur;cur cur-_left;}else{return false;}}//插入节点cur new Node(key);//不知道parent在那一边,需要进一步判断if (parent-_key key){//parent在左边parent-_left cur;}else if (parent-_key key){//parent在右边parent-_right cur;}else{return false;}return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_left key){cur cur-_left;}else if (cur-_left key){cur cur-_right;}else{return false;}return true;}}bool Erase(const K key){Node* parent nullptr;//待删除节点的父节点Node* cur _root;//待删除的节点//不是空树while (cur){//往左边走if (cur-_key key){parent cur;cur cur-_left;}//往右边走else if (cur-_key key){parent cur;cur cur-_right;}//找到待删除的节点else{//待删除节点的左子树为空 ,即一个孩子的情况if (cur-_left nullptr){//待删除节点是根节点if (cur _root){//将根节点改为待删除节点的右孩子_root cur-_right;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent-_right cur){parent-_right cur-_right;}else//parent-_left cur{parent-_left cur-_right;}}}//待删除节点的右子树为空 ,即一个孩子的情况else if (cur-_right nullptr){//待删除节点是根节点if (cur _root){//将根节点改为待删除节点的左孩子_root cur-_left;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent-_right cur){parent-_right cur-_left;}else//parent-_leftcur{parent-_left cur-_left;}}} else //待删除的节点的左右孩子都不为空 替换法左子树的最大节点即最右节点或者右子树的最小节点即最左节点,并且将替换的节点删除{//替换法//找替代节点Node* parent cur;//找左子树的最大节点Node* leftMax cur-_left;while (leftMax-_right){parent leftMax; //记录leftMax的父节点防止删除leftMax时找不到该节点位置 //一直往右子树找leftMax leftMax-_right;}//左子树的最大节点和待删除节点替换swap(cur-_key, leftMax-_key);//重新改变链接关系//特殊情况 if (parent-_left leftMax){parent-_left leftMax-_left;}else//普通情况 {parent-_right leftMax-_left;//parent-_right nullptr;}cur leftMax;}//删除左子树的最大节点delete cur;return true;}}return false;}//中序遍历void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node *root ){if (root nullptr){return; }_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root;
};void TestBSTree1()
{int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTreeint t;for (auto e : a){t.Insert(e);}t.InOrder();t.Erase(4);t.InOrder();t.Erase(6);t.InOrder();t.Erase(7);t.InOrder();t.Erase(3);t.InOrder();for (auto e : a){t.Erase(e);}t.InOrder();}递归版本
#pragma once
#includestring
using namespace std;
namespace key
{template class Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};template class Kclass BSTree{public:typedef BSTreeNodeK Node;public:BSTree():_root(nullptr){}~BSTree(){Destroy(_root);}//拷贝构造BSTree(const BSTreeK t)//BSTree( BSTreeK *this , const BSTreeK t)//t1 t {_root Copy(t._root);}//赋值重载 BSTreeK operator (BSTreeK t)//t1 t{swap(_root, t._root);return *this;}bool EraseR(Node* _root, const K key)//递归版本{return _EraseR(_root, key);}bool InsertR(const K key)//递归版本{return _InsertR(_root, key);}bool FindR(Node* _root, const K key)//递归版本{return _FindR(_root, key);}private:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* copyNode new Node(root-_key);//递归 copyNode-_left Copy(root-_left);copyNode-_right Copy(root-_right);return copyNode;}void Destroy(Node* root) //引用的目的将每个节点释放后同时置空{//后序遍历 if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}bool _InsertR(Node* root, const K key) //引用的目的不用找父节点不需要用父节点比较大小{//结束条件if (root nullptr){root new Node(key);return true;}//往左子树走if (root-_key key){return _InsertR(root-_left, key);}//往右子树走else if (root-_key key){return _InsertR(root-_right, key);}else{return false;}}bool _EraseR(Node* root, const K key)//引用的目的不用找父节点不需要用父节点比较大小{//结束条件if (root nullptr){return false;}//往左树找if (root-_key key){return _EraseR(root-_left, key);}//往右树找else if (root-_key key){return _EraseR(root-_right, key);}else//找到开始删除{Node* del root;//待删除节点的左子树为空 ,即一个孩子的情况if (root-_left nullptr){root root-_right;}//待删除节点的右子树为空 ,即一个孩子的情况else if (root-_right nullptr){root root-_left;}//待删除的节点的左右孩子都不为空 替换法左子树的最大节点即最右节点或者右子树的最小节点即最左节点,并且将替换的节点删除else{//找左子树最大节点Node* leftMax root-_left;//一直往左边找直到找到左子树最大节点while (root-_left){root root-_left;}//将左子树最大节点与被删除节点替换swap(leftMax-_key, root-_key);return _EraseR(root, key);}delete del;//?return true;}}bool _FindR(Node* root, const K key){//结束条件if (root nullptr){return false;}if (root-_key key){return _FindR(root-_left, key);}else if (root-_key key){return _FindR(root-_right, key);}else{return true;}}public://中序遍历void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}public:Node* _root;};void TestBSTree1(){int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTreeint t;for (auto e : a){t.InsertR(e);}t.InOrder();//没有引用释放了只是指针没有置空尤其是根节点_root我们还能通过他找到/*t.Destroy(t._root);*/t.EraseR(t._root, 4);t.InOrder();t.EraseR(t._root, 6);t.InOrder();t.EraseR(t._root, 7);t.InOrder();t.EraseR(t._root, 3);t.InOrder();for (auto e : a){t.EraseR(t._root, e);}t.InOrder();}void TestBSTree2(){int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTreeint t;for (auto e : a){t.InsertR(e);}t.InOrder();BSTreeint t1(t);t.InOrder();t1.InOrder();}
}namespace key_value
{templateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass K, class Vclass BSTree{public:typedef BSTreeNodeK, V Node;public:BSTree():_root(nullptr){}void InOrder(){_InOrder(_root);cout endl;}Node* FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key, const V value){return _InsertR(_root, key, value);}bool EraseR(const K key){return _EraseR(_root, key);}private:bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;// 1、左为空// 2、右为空// 3、左右都不为空if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Node* leftMax root-_left;while (leftMax-_right){leftMax leftMax-_right;}swap(root-_key, leftMax-_key);return _EraseR(root-_left, key);}delete del;return true;}}bool _InsertR(Node* root, const K key, const V value){if (root nullptr){root new Node(key, value);return true;}if (root-_key key){return _InsertR(root-_right, key, value);}else if (root-_key key){return _InsertR(root-_left, key, value);}else{return false;}}Node* _FindR(Node* root, const K key){if (root nullptr)return nullptr;if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return root;}}void _InOrder(Node* root){if (root NULL){return;}_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root;};void TestBSTree1(){BSTreestring, string dict;dict.InsertR(insert, 插入);dict.InsertR(sort, 排序);dict.InsertR(right, 右边);dict.InsertR(date, 日期);string str;while (cinstr){auto * ret dict.FindR(str);//auto ret dict.FindR(str);if (ret){cout ret-_value endl;}else{cout 无此单词 endl;}}}void TestBSTree2(){string arr[] {西瓜, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };BSTreestring, int countTree;for (auto str : arr){auto ret countTree.FindR(str);if (ret nullptr){countTree.InsertR(str,1);}else{ret-_value;}}countTree.InOrder();}}
如果你觉得这篇文章对你有帮助不妨动动手指给点赞收藏加转发给鄃鳕一个大大的关注你们的每一次支持都将转化为我前进的动力
