网站域名备案证明,西安官网优化报价,青岛seo整站优化招商电话,兔宝宝全屋定制衣柜官网troop主页#xff1a;troop 手撕二叉搜索树 1.二叉搜索树的定义2.实现#xff08;非递归#xff09;补充结构2.1查找2.2插入2.3删除#xff08;重要#xff09;情况1(无孩子一个孩子#xff09; 3.二叉搜索树的应用3.1K模型3.2KV模型3.2.1KV模型的实现 总结二叉… troop主页troop 手撕二叉搜索树 1.二叉搜索树的定义2.实现非递归补充结构2.1查找2.2插入2.3删除重要情况1(无孩子一个孩子 3.二叉搜索树的应用3.1K模型3.2KV模型3.2.1KV模型的实现 总结二叉搜索树源代码 1.二叉搜索树的定义
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树
若它的左子树不为空则左子树上的所有节点的值都小于根节点的值若它的右子树不为空则右子树上的所有节点的值都大于根节点的值 2.实现非递归
补充结构
//struct BinarySearchTreeNode
templateclass K
struct BSTreeNode
{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};/class BinarySearchTree
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTree() default;BSTree(const BSTreeK t){_root copy(t._root);}Node* copy(Node* root){if (root nullptr)return nullptr;Node* newroot new Node(root-_val);newroot-_left copy(root-_left);newroot-_right copy(root-_right);return newroot;}~BSTree(){Destroy();}void Destroy(){return _Destroy(_root);}void _Destroy(Node* root){if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete root;}
private:Node* _root;
};2.1查找
根据它的定义查找就是跟节点比比节点大就去它的右子树中寻找比他小就去它的左子树中寻找。 bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return false;}2.2插入 插入也很简单例如上图我们要插入16我们就先找到要插入的位置然后为了方便我们记录整个过程我们需要一个父节点。 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);if (parent-_key key){parent-_leftcur;}else{parent-_rightcur;}return true;}现在可以进行测试代码的正确性。 注意搜索二插入要有序它走的是中序遍历。
2.3删除重要
删除比插入麻烦的多我们删除值原则就是要保证它还是搜索二叉树它的性质不可以改变。这就挺麻烦的所以我们在删除这里用替换删除 替换删除找到一个可以替换的节点交换值转换删除它。 可以替换的节点是左子树的最大or右子树的最小。
下面我们来分析一下删除的各种情况
删除孩子节点删除只有一个孩子的节点删除两个孩子的节点 这里总结下情况1和2可以归为一类。情况3我们就要用到替换删除法
情况1(无孩子一个孩子 //找到了开始删除//第一种if (cur-_left nullptr)//我的左为空{if (cur _root){_root cur-_right;}else{if (cur parent-_left)//我是父亲的左{parent-_left cur-_right;}else//我是父亲的左{parent-_right cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;return true;}###情况二两个孩子 找到右子树的最小把它的值复制给cur就转换成了删除叶子节点 else//第二种(俩孩子)替换删除法{Node* rightMinparent cur;Node* rightMin cur-_right;while (cur-_right){rightMinparent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinparent-_left){rightMinparent-_left rightMin-_right;}else{rightMinparent-_right rightMin-_right;}delete rightMin;return true;}3.二叉搜索树的应用
3.1K模型
K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 比如给一个单词word判断该单词是否拼写正确。这个就是普通的二叉搜索树
3.2KV模型
KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。 通过key值快速查找另外一个值在不在。我们用二叉搜索树这个用的是比较多的 生活中的KV模型例如商场车库进去都可以进入记录车牌key进入时间value 出付费出通过车牌key查询进入的时间value。 还有字典查询高铁身份证进站等等。
3.2.1KV模型的实现
这个就是多加了一个对象实现直接CV上面的代码
namespace key_value
{templateclass K, class Vstruct BSTreeNode{typedef BSTreeNodeK, V Node;Node* _left;Node* _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{typedef BSTreeNodeK, V Node;public://插入bool Insert(const K key, const V value){if (_root nullptr){_root new Node(key, value);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 true;}}cur new Node(key, value);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}//Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return nullptr;}//中序遍历void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);std::cout root-_val ;_InOrder(root-_right);}void InOrder(){_InOrder(_root);cout endl;}//3.删除bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_val key){parent cur;cur cur-_right;}else if (cur-_val key){parent cur;cur cur-_left;}else{//找到了开始删除//第一种无孩子一个孩子if (cur-_left nullptr)//我的左为空{if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else//我是父亲的右节点{parent-_right cur-_right;}}delete cur;return true;}else if (cur-_right nullptr)//我的右为空{if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else//我是父亲的右节点{parent-_right cur-_left;}}delete cur;return true;}else//第二种有两个孩子替换删除法{Node* rightMinparent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinparent rightMin;rightMin rightMin-_left;}cur-_val rightMin-_val;if (rightMin rightMinparent-_left)rightMinparent-_left rightMin-_right;elserightMinparent-_right rightMin-_right;delete rightMin;return true;}}}return false;}//void InOrder()//{// _InOrder(_root);// cout endl;//}//private:// void _InOrder(Node* root)// {// if (root nullptr)// return;// _InOrder(root-_left);// cout root-_key ;// _InOrder(root-_right);// }private:Node* _root nullptr;};
}我们可以用哥个例子来玩一玩这个KV模型
void TestBSTree()
{key_value::BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(left, 左边);dict.Insert(string, 字符串);string str;while (cin str){auto ret dict.Find(str);if (ret){cout str : ret-_value endl;}else{cout 单词拼写错误 endl;}}
}总结
总的来说二叉搜索树比较难的地方就是删除部分多画图多思考。 下篇我们就要深入二叉搜索树。
二叉搜索树源代码
#pragma once
#includeiostream
using namespace std;
//struct BinarySearchTreeNode
templateclass K
struct BSTreeNode
{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};//class BinarySearchTree
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTree() default;BSTree(const BSTreeK t){_root copy(t._root);}Node* copy(Node* root){if (root nullptr)return nullptr;Node* newroot new Node(root-_val);newroot-_left copy(root-_left);newroot-_right copy(root-_right);return newroot;}~BSTree(){Destroy();}void Destroy(){return _Destroy(_root);}void _Destroy(Node* root){if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete root;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return false;}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);if (parent-_key key){parent-_leftcur;}else{parent-_rightcur;}return true;}bool Erase(const K key){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{//找到了开始删除//第一种if (cur-_left nullptr)//我的左为空{if (cur _root){_root cur-_right;}else{if (cur parent-_left)//我是父亲的左{parent-_left cur-_right;}else//我是父亲的左{parent-_right cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;return true;}else//第二种(俩孩子)替换删除法{Node* rightMinparent cur;Node* rightMin cur-_right;while (cur-_right){rightMinparent rightMin;rightMin rightMin-_left;}if (rightMinparent-_left rightMin){rightMinparent-_left rightMin-_right;}else{rightMinparent-_right rightMin-_right;}}}}return false;}void Inorder(){_Inorder(_root);cout endl;}
private:void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);}
private:Node* _rootnullptr;
};
