个人网站怎么建设,西安个人做企业网站,毕业设计做系统网站,规模以上工业企业主营业务收入1.二叉搜索树
1.1.二叉搜索树概念
二叉搜索树又称二叉排序树#xff0c;它或者是一颗空树#xff0c;或者是具有一下性质的二叉树。
若它的左子树不为空#xff0c;则左子树上的所有节点的值都小于根节点的值。若它的右子树不为空#xff0c;则右子树上的所有节点的值都…1.二叉搜索树
1.1.二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一颗空树或者是具有一下性质的二叉树。
若它的左子树不为空则左子树上的所有节点的值都小于根节点的值。若它的右子树不为空则右子树上的所有节点的值都大于根节点的值。它的左右子树也分别为二叉搜索树。
1.2.二叉搜索树操作
二叉搜索树的查找 a. 从根开始比较查找比根大则往右边查找比跟小则往左边走查找。b. 最多查找高度次走到空还没找到这个值不存在。 二叉搜索树的插入 树为空则直接增加节点赋值给root指针树不为空按二叉搜索树性质查找插入位置插入新节点。 二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的节点可能分下面四种情况。
要删除的节点无孩子节点要删除的节点只有左孩子节点要删除的节点只有右孩子节点要删除的节点有左右孩子节点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正删除过程如下:
情况b:删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点-直接删除。情况c:删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点-直接删除。情况d:在它的右子树中寻找中序下第一个节点(关键码最小),用它的值填补到被删除节点中再来处理该节点的删除问题–替换法删除。
1.3.二叉搜索树的模拟实现
template class K
struct BSTreeNode
{struct BSTreeNode* left;struct BSTreeNode* right;K key;BSTreeNode(const K key):key(key),left(nullptr),right(nullptr){}
};template class K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTree():_root(nullptr){}BSTree(const BSTreeK t){_root Copyt(t._root);}BSTreeK operator(BSTree 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* parent _root;Node* cur _root;while (cur ! nullptr){if (cur-key key){parent cur;cur cur-right;}else if (cur-key key){parent cur;cur cur-left;}elsereturn false;}if (parent-key key){parent-right new Node(key);}else{parent-left new Node(key);}return true;}void InOrder(){_InOrder(_root);cout endl;}bool Find(const K key){if (_root nullptr)return false;Node* cur _root;while (cur ! nullptr){if (cur-key key){cur cur-right;}else if (cur-key key){cur cur-left;}elsereturn true;}return false;}bool Erase(const K key){Node* parent _root;Node* cur _root;while (cur ! nullptr){if (cur-key key){parent cur;cur cur-left;}else if (cur-key key){parent cur;cur cur-right;}else{Node* del cur;//到这里成功的找到这个元素,删除的情况分三种//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{Node* minRight cur-right;//minRight就是右最大while (minRight-left ! nullptr){parent minRight;minRight minRight-left;}swap(cur-key, minRight-key);if (parent-left minRight){parent-left minRight-right;}else{parent-right minRight-right;}cur minRight;}delete cur;return true;}}return false;}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;}Node* Copyt(const Node* root){if (root nullptr){return nullptr;}Node* parent new Node(root-key);parent-left Copyt(root-left);parent-right Copyt(root-right);return parent;}void _InOrder(Node* _root){if (_root nullptr)return;_InOrder(_root-left);cout _root-key ;_InOrder(_root-right);}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{//三种情况//1.左为空Node* del root;if (root-left nullptr){root root-right;}//2.右为空else if (root-right nullptr){root root-left;}//3.左右都不为空else{Node* minRight root-right;while (minRight-left ! nullptr){minRight minRight-left;}swap(root-key, minRight-key);return _EraseR(root-right, key);}delete del;return true;}}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 _InsertR(Node* root,const K key){if (root nullptr){root new Node(key);return true;}if (root-key key){_InsertR(root-right, key);}else if (root-key key){_InsertR(root-left, key);}else{return false;}return false;}//bool _InsertR(Node* root, const K key)//{// if (_root nullptr)// {// _root new Node(key);// return true;// }// if (root-key key) {// if (root-right nullptr)// {// root-right new Node(key);// return true;// }// _InsertR(root-right, key);// }// else if (root-key key) {// if (root-left nullptr)// {// root-left new Node(key);// return true;// }// _InsertR(root-left, key);// }// else// return false;// return true;//}protected:Node* _root nullptr;
};2.二叉搜索树的应用
K模型:K模型即只有key作为关键码结构体只需要存储key即可关键码即为需要搜索到的值。
比如给一个单词Word判断该单词是否拼写正确。 在二叉搜索树中检查该单词是否存在存在则拼写正确不存在则拼写错误。
KV模型:每一个关键码key都有与之对应的值Value即KeyValue的键值对这种方式在现实生活中非常常见。
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文WordChinese就构成一种键值对再比如统计单调次数统计成功后给定单词就可快速找到出现的次数单词与其出现次数就是word,count就构成一种键值对。
namespace KV
{template class K,class Vstruct BSTreeNode{struct BSTreeNode* left;struct BSTreeNode* right;K key;V value;BSTreeNode(const K key,const V value):key(key),value(value), left(nullptr), right(nullptr){}};template class 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 _root;Node* cur _root;while (cur ! nullptr){if (cur-key key){parent cur;cur cur-right;}else if (cur-key key){parent cur;cur cur-left;}elsereturn false;}if (parent-key key){parent-right new Node(key,value);}else{parent-left new Node(key,value);}return true;}Node* Find(const K key){Node* cur _root;while (cur ! nullptr){if (cur-key key){cur cur-right;}else if (cur-key key){cur cur-left;}elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);cout endl;}private:void _InOrder(Node* _root){if (_root nullptr)return;_InOrder(_root-left);cout _root-key :_root-value;_InOrder(_root-right);}protected:Node* _root nullptr;};
}void Test4()
{KV::BSTreestring, int b;string arr[] { 苹果,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉 };for (auto e : arr){auto ret b.Find(e);if (ret){ret-value;}else{b.Insert(e, 1);}}b.InOrder();
}int main()
{Test4();
}3.二叉搜索树的性能分析
插入和删除操作必须先查找查找效率代表了二叉搜索树中的各个操作的性能。 对于n个节点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数即插入节点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树。 最优情况下:二叉搜索树为完全二叉树或者接近完全二叉树其平均比较次数log2Nlog_2Nlog2N 最差情况下二叉搜索树退化为单支树其平均比较次数为:N2\frac{N}{2}2N 文章转载自： http://www.morning.pjxw.cn.gov.cn.pjxw.cn http://www.morning.lblsx.cn.gov.cn.lblsx.cn http://www.morning.jwwfk.cn.gov.cn.jwwfk.cn http://www.morning.lrflh.cn.gov.cn.lrflh.cn http://www.morning.kttbx.cn.gov.cn.kttbx.cn http://www.morning.mfxcg.cn.gov.cn.mfxcg.cn http://www.morning.benqc.com.gov.cn.benqc.com http://www.morning.fbhmn.cn.gov.cn.fbhmn.cn http://www.morning.dthyq.cn.gov.cn.dthyq.cn http://www.morning.0small.cn.gov.cn.0small.cn http://www.morning.gwkwt.cn.gov.cn.gwkwt.cn http://www.morning.dighk.com.gov.cn.dighk.com http://www.morning.rmdwp.cn.gov.cn.rmdwp.cn http://www.morning.wnbqy.cn.gov.cn.wnbqy.cn http://www.morning.stflb.cn.gov.cn.stflb.cn http://www.morning.c7629.cn.gov.cn.c7629.cn http://www.morning.wpydf.cn.gov.cn.wpydf.cn http://www.morning.sfzwm.cn.gov.cn.sfzwm.cn http://www.morning.qxkcx.cn.gov.cn.qxkcx.cn http://www.morning.qzzmc.cn.gov.cn.qzzmc.cn http://www.morning.qhtlq.cn.gov.cn.qhtlq.cn http://www.morning.joinyun.com.gov.cn.joinyun.com http://www.morning.fksrg.cn.gov.cn.fksrg.cn http://www.morning.wspjn.cn.gov.cn.wspjn.cn http://www.morning.znknj.cn.gov.cn.znknj.cn http://www.morning.dsmwy.cn.gov.cn.dsmwy.cn http://www.morning.caswellintl.com.gov.cn.caswellintl.com http://www.morning.qynpw.cn.gov.cn.qynpw.cn http://www.morning.hbhnh.cn.gov.cn.hbhnh.cn http://www.morning.mqmxg.cn.gov.cn.mqmxg.cn http://www.morning.tbknh.cn.gov.cn.tbknh.cn http://www.morning.yrcxg.cn.gov.cn.yrcxg.cn http://www.morning.tsyny.cn.gov.cn.tsyny.cn http://www.morning.mqpdl.cn.gov.cn.mqpdl.cn http://www.morning.bnjnp.cn.gov.cn.bnjnp.cn http://www.morning.tjwfk.cn.gov.cn.tjwfk.cn http://www.morning.rrgm.cn.gov.cn.rrgm.cn http://www.morning.jcffp.cn.gov.cn.jcffp.cn http://www.morning.lslin.com.gov.cn.lslin.com http://www.morning.nfbkz.cn.gov.cn.nfbkz.cn http://www.morning.rwcw.cn.gov.cn.rwcw.cn http://www.morning.jqpq.cn.gov.cn.jqpq.cn http://www.morning.zrhhb.cn.gov.cn.zrhhb.cn http://www.morning.plqsz.cn.gov.cn.plqsz.cn http://www.morning.jzlkq.cn.gov.cn.jzlkq.cn http://www.morning.brsgw.cn.gov.cn.brsgw.cn http://www.morning.rqrh.cn.gov.cn.rqrh.cn http://www.morning.rkdw.cn.gov.cn.rkdw.cn http://www.morning.dschz.cn.gov.cn.dschz.cn http://www.morning.xptkl.cn.gov.cn.xptkl.cn http://www.morning.nkdmd.cn.gov.cn.nkdmd.cn http://www.morning.zcnfm.cn.gov.cn.zcnfm.cn http://www.morning.plfrk.cn.gov.cn.plfrk.cn http://www.morning.mxhys.cn.gov.cn.mxhys.cn http://www.morning.pxtgf.cn.gov.cn.pxtgf.cn http://www.morning.pqnps.cn.gov.cn.pqnps.cn http://www.morning.pbgnx.cn.gov.cn.pbgnx.cn http://www.morning.rqdx.cn.gov.cn.rqdx.cn http://www.morning.yrhpg.cn.gov.cn.yrhpg.cn http://www.morning.hmmtx.cn.gov.cn.hmmtx.cn http://www.morning.yszrk.cn.gov.cn.yszrk.cn http://www.morning.kcdts.cn.gov.cn.kcdts.cn http://www.morning.hqwxm.cn.gov.cn.hqwxm.cn http://www.morning.kntbk.cn.gov.cn.kntbk.cn http://www.morning.yrmpz.cn.gov.cn.yrmpz.cn http://www.morning.czcbl.cn.gov.cn.czcbl.cn http://www.morning.pxjp.cn.gov.cn.pxjp.cn http://www.morning.rpgdd.cn.gov.cn.rpgdd.cn http://www.morning.sthgm.cn.gov.cn.sthgm.cn http://www.morning.hpprx.cn.gov.cn.hpprx.cn http://www.morning.mstrb.cn.gov.cn.mstrb.cn http://www.morning.zrkws.cn.gov.cn.zrkws.cn http://www.morning.gnghp.cn.gov.cn.gnghp.cn http://www.morning.kjdxh.cn.gov.cn.kjdxh.cn http://www.morning.ljwyc.cn.gov.cn.ljwyc.cn http://www.morning.ysfj.cn.gov.cn.ysfj.cn http://www.morning.mbfkt.cn.gov.cn.mbfkt.cn http://www.morning.ymqrc.cn.gov.cn.ymqrc.cn http://www.morning.rhsg.cn.gov.cn.rhsg.cn http://www.morning.lwmxk.cn.gov.cn.lwmxk.cn
