滨海做网站价格,呼和浩特市网站公司电话,京东短链接生成器,表格制作教程入门视频文章目录 二叉搜索树概念二叉搜索树的操作查找插入删除 二叉搜索树的应用 二叉搜索树
概念 什么是二叉搜索树#xff0c;二叉搜索树就是指左孩子永远比根小右孩子永远比根大。这个规则适用于所有的子树。 上面的就是一棵二叉搜索树#xff0c;我们还可以发现这棵树走一个中… 文章目录 二叉搜索树概念二叉搜索树的操作查找插入删除 二叉搜索树的应用 二叉搜索树
概念 什么是二叉搜索树二叉搜索树就是指左孩子永远比根小右孩子永远比根大。这个规则适用于所有的子树。 上面的就是一棵二叉搜索树我们还可以发现这棵树走一个中序遍历序列是有序的所以它又被称为二叉排序树。 二叉搜索树的操作
二叉搜索树的操作主要分为以下几点查找 插入删除。
查找
算法思想二叉搜索树的查找算法是这样的从根的地方开始找如果要找的key比根大就到右子树去找如果比根小就到左子树找。时间复杂度最差为O(N)最优为O(logn)如果一棵树走完了还没有找到说明这个数字不在这棵树内。 O(N)时间复杂度是下面这棵树的查找产生的。 我们要使树的高度保持为logN就必须引入平衡二叉搜索树的概念这个部分我们在后面的AVL和红黑树部分讲解。 非递归算法 bool Find(const K key){Node* cur _root;while (cur ! nullptr){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;}}return false;}递归算法 key小于就递归找左树大于就递归找右树 bool _FindR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){_FindR(root-_right, key);}else if (root-_key key){_FindR(root-_left, key);}else{return true;}}插入
插入分为两种情况 1、如果树为空则直接新增节点赋值给_root指针。 2、树不为空按二叉搜索树性质查找插入位置插入新节点。 非递归算法
bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;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-_right cur;}else{parent-_left cur;}return true;}递归算法 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;}}删除
首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的节点可能分下面四种情况 a.要删除的节点无孩子节点 b.要删除的节点只有左孩子节点 c.要删除的节点只有右孩子节点 d.要删除的节点有左右孩子节点 情况bc可以合成一个情况那就是只有一个孩子节点。 情况b删除该节点且是被删除节点的双亲节点指向被删除节点的左孩子节点—直接删除
情况c删除该节点且是被删除节点的双亲节点指向被删除节点的右孩子节点—直接删除
情况d在它的左子树中寻找最大节点用它的值填补到被删除节点中再来处理该节点的删除问题—替换法删除。 非递归算法
bool Erase(const K key){Node* cur _root;Node* parent nullptr;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;}else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}}else{//左右都不为空//找到左树中的最大值为替代节点Node* parent cur;Node* leftmax _root-_left;while (leftmax-_right ! nullptr){parent leftmax;leftmax leftmax-_right;}swap(cur-_key, leftmax-_key);if (parent-_left leftmax){parent-_left leftmax-_left;}else{parent-_right leftmax-_left;}cur leftmax;}delete cur;return true;}}return false;}非递归算法
//Node* 引用是关键没有引用就不会链接起来不用引用也可以用二级指针。
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-_left){leftMax leftMax-_right;}swap(root-_key, leftMax-_key);return _EraseR(root-_left, key);}delete del;return true;}}完整代码
namespace name
{templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};template class Kclass BSTree{typedef BSTreeNodeK Node;public://构造函数BSTree():_root(nullptr){}BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);}bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;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-_right cur;}else{parent-_left cur;}return true;}bool Find(const K key){Node* cur _root;while (cur ! nullptr){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;}}return false;}bool Erase(const K key){Node* cur _root;Node* parent nullptr;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;}else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}}else{//左右都不为空//找到左树中的最大值为替代节点Node* parent cur;Node* leftmax _root-_left;while (leftmax-_right ! nullptr){parent leftmax;leftmax leftmax-_right;}swap(cur-_key, leftmax-_key);if (parent-_left leftmax){parent-_left leftmax-_left;}else{parent-_right leftmax-_left;}cur leftmax;}delete cur;return true;}}return false;}void Inorder(){_Inorder(_root);cout endl;}bool FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key){return _InsertR(_root, key);}bool EraseR(const K key){return _EraseR(_root, key);}private:void Destory(Node* root){if (root nullptr){return;}Destory(root-_left);Destory(root-_right);delete root;root nullptr;}Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* copyroot new Node(root-_key);copyroot-_left Copy(root-_left);copyroot-_right Copy(root-_right);return copyroot;}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 _FindR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){_FindR(root-_right, key);}else if (root-_key key){_FindR(root-_left, key);}else{return true;}}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-_left){leftMax leftMax-_right;}swap(root-_key, leftMax-_key);return _EraseR(root-_left, key);}delete del;return true;}}void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);}Node* _root;};
}
二叉搜索树的应用 应用主要是分为了K模型和KV模型后面的set为K模型map为KV模型具体是这样的 K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文word,chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word,count就构成一种键值对。 上面的代码时K模型的下面的代码时KV模型的。 namespace name1
{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){}};template class K,class Vclass BSTree{typedef BSTreeNodeK,V Node;public://构造函数BSTree():_root(nullptr){}BSTree(const BSTreeK,V t){_root Copy(t._root);}BSTreeK,V operator(BSTreeK,V t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);}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:void Destory(Node* root){if (root nullptr){return;}Destory(root-_left);Destory(root-_right);delete root;root nullptr;}Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* copyroot new Node(root-_key);copyroot-_left Copy(root-_left);copyroot-_right Copy(root-_right);return copyroot;}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-_left, key, value);}else if (root-_key key){return _InsertR(root-_right, 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;}}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-_left){leftMax leftMax-_right;}swap(root-_key, leftMax-_key);return _EraseR(root-_left, key);}delete del;return true;}}void _Inorder(Node* root){if (rootnullptr){return;}_Inorder(root-_left);cout root-_key : root-_value endl;_Inorder(root-_right);}Node* _root;};
}KV模型的测试
void Test_BSTree7()
{string arr[] { 西瓜, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };name1::BSTreestring, int countTree;for (auto str : arr){//没有找到证明是第一次出现auto ret countTree.FindR(str);if (ret nullptr){countTree.InsertR(str, 1);}else{ret-_value;}}countTree.Inorder();
}
int main()
{//Test_BSTree();//Test_BSTree1();//Test_BSTree2();//Test_BSTree3();//Test_BSTree4();//Test_BSTree5();//Test_BSTree6();Test_BSTree7();return 0;
}好的我们下一篇再见
