湛江网站建设费用,我想找电商合作,网站设计模板代码,wordpress发广告二叉搜索树 概念二叉搜索树的应用二叉搜索树的实现K模型基本结构和函数声明接口实现①find——查找关键码②Insert——插入关键码③Erase——删除关键码#xff08;重点#xff09;时间复杂度 源码#xff08;整体#xff09;非递归递归 KV模型 在使用C语言写数据结构阶段时… 二叉搜索树 概念二叉搜索树的应用二叉搜索树的实现K模型基本结构和函数声明接口实现①find——查找关键码②Insert——插入关键码③Erase——删除关键码重点时间复杂度 源码整体非递归递归 KV模型 在使用C语言写数据结构阶段时对二叉树进行了讲解。本节内容是对二叉树的深入探索也是二叉树部分的收尾
概念
二叉搜索树也称二叉排序树BSTBinary Search Tree 空树非空树要具有以下性质 若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 注意 二叉搜索树的key值互不相同
eg:下图就属于二叉搜索树
二叉搜索树的应用 K模型即只有key作为关键码结构中只需要存储key。关键码就是要搜索到的值 eg: 给一个单词word判断该单词是否拼写正确具体步骤1. 以词库中所有单词为基础每个单词都是key构建一颗搜索二叉树2. 在二叉树中搜索该单词是否存在存在则返回true否则返回falseKV模型每一个关键码key都有与之对应的value即Key, Value的键值对 eg1: 英汉词典 - 就是中文与英文的对应关系。通过英文可以快速找到与其对应的中文英文单词和与其对应的中文word, chinese就构成键值对。eg2: 统计单词次数统计成功后给定单词就可以找到单词出现得次数。单词与其出现次数就是word, count就构成一种键值对二叉搜索树的实现
注意 通过二叉搜索树的应用了解到其有两个模型接下来对这两个模型分别进行实现。因为两个模型的接口都相似所以仅对一个模型的接口进行详细介绍。
K模型
K模型的实现分为递归和非递归两种但是接口的实现逻辑是一样的。为了便于理解把基本结构和函数声明先附上然后对接口进行讲解最后在贴上完整的源码
基本结构和函数声明
//二叉树节点
//节点使用struct默认public访问
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public://默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTreeK t);//赋值运算符重载BSTreeK operator(BSTreeK t);//析构函数~BSTree();//插入bool Insert(const K key);//查找bool Find(const K key);//删除bool Erase(const K key);//中序遍历void InOrder();private:Node* _root;
};接口实现
①find——查找关键码
功能查找关键码是否在树中是返回真否则返回假。 原理
从根开始比较比根大则往右边查找比根小往左边查找最多查找高度次走到nullptr则这个值不存在
实现代码
非递归版本
templateclass K
bool BSTreeK::Find(const K key)
{Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;}}return false;
}递归版本
bool Find(const K key)
{Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;}}return false;
}②Insert——插入关键码
原理
树为空直接把要插入的节点赋值给root树不为空通过查找的思路找到要插入的合适位置。插入成功返回true 注意如果要插入的值和树中的值冲突则返回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-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{return false;}}cur new Node(key);if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;
}递归版本
bool InsertR(const K key)
{return _InsertR(_root, key);
}
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);elsereturn true;
}③Erase——删除关键码重点
原理
查找关键码是否在二叉搜索树中不存在直接返回false存在则要分为四种情况
情况 在考虑树的所有情况时要把根节点的情况和普通情况分离开来。哪怕最后根节点的情况和普通情况一样。仅代表博主个人观点 要删除的节点无孩子节点 要删除的节点无左孩子节点 要删除的节点无右孩子节点 要删除的节点左右都不为空 采用的方法 一 替换法 替换法找到删除节点左子树的最大值节点(leftMax)然后与删除节点交换再删除现在的leftMax。也可以找删除节点右子树的最小值节点(rightMin)原理相同 实现代码
非递归版本
//删除
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 //找到了要删除的值{//分情况//1.左为空if (cur-_left nullptr){if (cur _root)_root cur-_right;else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}//2.右为空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;}}} //3.左右都不为空else{parent cur;Node* leftMax cur-_left;while (leftMax-_right){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;cur nullptr;return true;}}return false;
}递归版本
//删除
bool EraseR(const K key)
{return _EraseR(_root, key);
}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;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;del nullptr;return true;}
}时间复杂度
二叉搜索树的操作时间复杂度在O(logN)和O(N)之间。 画图解释时间复杂度
源码整体
非递归
//非递归
namespace key
{//二叉树节点//节点使用struct默认public访问templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};templateclass 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(){Destroy(_root);}//插入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-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{return false;}}cur new Node(key);if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;}//查找bool Find(const K key){Node* cur _root;while (cur){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* 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 //找到了要删除的值{//分情况//1.左为空if (cur-_left nullptr){if (cur _root)_root cur-_right;else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}//2.右为空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;}}} //3.左右都不为空else{parent cur;Node* leftMax cur-_left;while (leftMax-_right){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;cur nullptr;return true;}}return false;}//中序遍历void InOrder(){_InOrder(_root);cout endl;}private:Node* Copy(Node* root){if (root nullptr)return nullptr;Node* copyRoot new Node(root-_key);copyRoot-_left Copy(root-_left);copyRoot-_right Copy(root-_tight);return copyRoot;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root;};
}递归
//递归
namespace keyR
{//二叉树节点//节点使用struct默认public访问templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};templateclass 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(){Destroy(_root);}//插入bool InsertR(const K key){return _InsertR(_root, key);}//查找bool FindR(const K key){return _FindR(_root, key);}//删除bool EraseR(const K key){return _EraseR(_root, key);}//中序遍历void InOrder(){_InOrder(_root);cout endl;}private://在root添加引用很关键要不然得是二级指针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);elsereturn false;}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;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;del nullptr;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);elsereturn true;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* copyRoot new Node(root-_key);copyRoot-_left CopyRoot(root-_left);copyRoot-_right CopyRoot(root-_right);return copyRoot;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root;};
}KV模型
直接贴出源码
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{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(){Destroy(_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: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;if (root-_left nullptr){//这个root的引用非常好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;}}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* copyRoot new Node(root-_key, root-_value);copyRoot-_left Copy(root-_left);copyRoot-_right Copy(root-_right);return copyRoot;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}Node* _FindR(Node* root, const K key){if (root nullptr)return nullptr;if (root-_key key){return _FindR(root-_left, key);}else if (root-_key key){return _FindR(root-_right, key);}else{return root;}}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;}}private:Node* _root;};}
文章转载自： http://www.morning.cjmmn.cn.gov.cn.cjmmn.cn http://www.morning.qjxxc.cn.gov.cn.qjxxc.cn http://www.morning.fcxt.cn.gov.cn.fcxt.cn http://www.morning.mgnrc.cn.gov.cn.mgnrc.cn http://www.morning.kntbk.cn.gov.cn.kntbk.cn http://www.morning.kxscs.cn.gov.cn.kxscs.cn http://www.morning.smzr.cn.gov.cn.smzr.cn http://www.morning.yrskc.cn.gov.cn.yrskc.cn http://www.morning.mbmh.cn.gov.cn.mbmh.cn http://www.morning.bfbl.cn.gov.cn.bfbl.cn http://www.morning.plydc.cn.gov.cn.plydc.cn http://www.morning.xqcst.cn.gov.cn.xqcst.cn http://www.morning.mlmwl.cn.gov.cn.mlmwl.cn http://www.morning.xkpjl.cn.gov.cn.xkpjl.cn http://www.morning.zlwg.cn.gov.cn.zlwg.cn http://www.morning.ympcj.cn.gov.cn.ympcj.cn http://www.morning.dzdtj.cn.gov.cn.dzdtj.cn http://www.morning.srjgz.cn.gov.cn.srjgz.cn http://www.morning.gmysq.cn.gov.cn.gmysq.cn http://www.morning.nqnqz.cn.gov.cn.nqnqz.cn http://www.morning.wrtxk.cn.gov.cn.wrtxk.cn http://www.morning.hcszr.cn.gov.cn.hcszr.cn http://www.morning.elbae.cn.gov.cn.elbae.cn http://www.morning.rfycj.cn.gov.cn.rfycj.cn http://www.morning.pqwjh.cn.gov.cn.pqwjh.cn http://www.morning.pnntx.cn.gov.cn.pnntx.cn http://www.morning.gpcy.cn.gov.cn.gpcy.cn http://www.morning.dwzwm.cn.gov.cn.dwzwm.cn http://www.morning.fksrg.cn.gov.cn.fksrg.cn http://www.morning.tjndb.cn.gov.cn.tjndb.cn http://www.morning.tbjb.cn.gov.cn.tbjb.cn http://www.morning.mgwdp.cn.gov.cn.mgwdp.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.xykst.cn.gov.cn.xykst.cn http://www.morning.krjyq.cn.gov.cn.krjyq.cn http://www.morning.hrpbq.cn.gov.cn.hrpbq.cn http://www.morning.rlbc.cn.gov.cn.rlbc.cn http://www.morning.rksnk.cn.gov.cn.rksnk.cn http://www.morning.trjr.cn.gov.cn.trjr.cn http://www.morning.lgpzq.cn.gov.cn.lgpzq.cn http://www.morning.mqbdb.cn.gov.cn.mqbdb.cn http://www.morning.ktmnq.cn.gov.cn.ktmnq.cn http://www.morning.cwyrp.cn.gov.cn.cwyrp.cn http://www.morning.fnzbx.cn.gov.cn.fnzbx.cn http://www.morning.dtgjt.cn.gov.cn.dtgjt.cn http://www.morning.qcdtzk.cn.gov.cn.qcdtzk.cn http://www.morning.kfqzd.cn.gov.cn.kfqzd.cn http://www.morning.geledi.com.gov.cn.geledi.com http://www.morning.zztkt.cn.gov.cn.zztkt.cn http://www.morning.hdscx.cn.gov.cn.hdscx.cn http://www.morning.gbjxj.cn.gov.cn.gbjxj.cn http://www.morning.dhqzc.cn.gov.cn.dhqzc.cn http://www.morning.tjsxx.cn.gov.cn.tjsxx.cn http://www.morning.kyytt.cn.gov.cn.kyytt.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.paxkhqq.cn.gov.cn.paxkhqq.cn http://www.morning.qqzdr.cn.gov.cn.qqzdr.cn http://www.morning.lbcbq.cn.gov.cn.lbcbq.cn http://www.morning.fbfnk.cn.gov.cn.fbfnk.cn http://www.morning.dnwlb.cn.gov.cn.dnwlb.cn http://www.morning.fxzlg.cn.gov.cn.fxzlg.cn http://www.morning.rtpw.cn.gov.cn.rtpw.cn http://www.morning.ldcsw.cn.gov.cn.ldcsw.cn http://www.morning.rlbfp.cn.gov.cn.rlbfp.cn http://www.morning.080203.cn.gov.cn.080203.cn http://www.morning.txrq.cn.gov.cn.txrq.cn http://www.morning.nnjq.cn.gov.cn.nnjq.cn http://www.morning.njpny.cn.gov.cn.njpny.cn http://www.morning.sftrt.cn.gov.cn.sftrt.cn http://www.morning.zrlwl.cn.gov.cn.zrlwl.cn http://www.morning.yrrnx.cn.gov.cn.yrrnx.cn http://www.morning.zlnkq.cn.gov.cn.zlnkq.cn http://www.morning.bpwfr.cn.gov.cn.bpwfr.cn http://www.morning.tbkqs.cn.gov.cn.tbkqs.cn http://www.morning.wglhz.cn.gov.cn.wglhz.cn http://www.morning.qhkx.cn.gov.cn.qhkx.cn http://www.morning.c7625.cn.gov.cn.c7625.cn http://www.morning.supera.com.cn.gov.cn.supera.com.cn http://www.morning.qqtzn.cn.gov.cn.qqtzn.cn http://www.morning.gwqkk.cn.gov.cn.gwqkk.cn
