wordpress默认的h1标签放在哪里,西安seo,深圳网站建设公司服务流程,建筑工程完工证明格式序言#xff1a;
构造一棵二叉排序树的目的并不是为了排序#xff0c;而是为了提高查找效率、插入和删除关键字的速度#xff0c;同时二叉搜索树的这种非线性结构也有利于插入和删除的实现。 目录
#xff08;一#xff09;BST的定义
#xff08;二#xff09;二叉搜…序言
构造一棵二叉排序树的目的并不是为了排序而是为了提高查找效率、插入和删除关键字的速度同时二叉搜索树的这种非线性结构也有利于插入和删除的实现。 目录
一BST的定义
二二叉搜索树操作
1、BST的查找
2、BST的插入
3、BST的删除
三二叉排序树的实现非递归
1、查找实现
2、插入实现
3、删除实现
四二叉排序树的实现递归
1、查找操作
2、插入操作
3、删除操作
五其他操作
1、析构
2、构造和拷贝构造
3、赋值重载
六总结 一BST的定义
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二二叉搜索树操作
我以下图这棵二叉树为例给大家进行有关二叉树操作的讲解 1、BST的查找
思想
二叉搜索树的查找是从根节点开始的沿某个分支逐层的向下比较的过程若二叉排序树非空先将给定值与根节点的关键字进行比较若相等则查找成功若不等如果小于根节点的关键字则在根节点的左子树上进行查找否则就在根节点的右侧进行查找。这显然是一个递归的过程
举例
例如对于上述二叉树我想要查找值为【6】的结点。首先 6 与根节点 8 进行比较由于 68 因此需要在根节点8的左子树中继续查找由于 36因此在结点 3 的右子树中进行查找最后查询成功。 2、BST的插入
二叉排序树作为一种动态树表其特点是树的结构通常不是一次生成的而是在查找过程中存在关键字值等于给定值的结点时再进行插入的。
插入结点的过程如下
若原二叉排序树为空则直接插入否则若关键字 k 小于根结点值左子树若关键字 k 大于根结点值则插入到右子树
插入的结点一定是一个新添加且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。 3、BST的删除
在二叉排序树中删除一个结点时不能把以该结点为根的子树上的结点都删除必须先删除结点从存储二叉排序树的链表上摘下将因删除结点而断开的二叉链表重新链接起来确保二叉排序树的性质不会丢失。
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况
a.要删除的结点无孩子结点b. 要删除的结点只有左孩子结点c. 要删除的结点只有右孩子结点d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下
情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除 三二叉排序树的实现非递归
1、查找实现
代码如下:
//查找操作bool Find(const K key){Newnode* 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、插入实现
代码如下: //插入操作bool Insert(const K key){if (_root nullptr){_root new Newnode(key);return true;}Newnode* parent nullptr;Newnode* 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 Newnode(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;} 3、删除实现
代码如下:
//删除操作bool Erase(const K key){Newnode* parent nullptr;Newnode* 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 (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}//不存在右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;}//左右均存在else {// 找右树最小节点替代也可以是左树最大节点替代Newnode* pminRight cur;Newnode* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight) {pminRight-_left minRight-_right;}else {pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;} 四二叉排序树的实现递归 递归实现都比较容易只要大家掌握到了思想我相信实现起来就是很容易的。 1、查找操作 //查找操作bool _FindR(Newnode* root, const K key){if (root nullptr)return false;if (root-_key key)return true;if (root-_key key)return _FindR(root-_right, key);elsereturn _FindR(root-_left, key);}
2、插入操作 //插入操作bool _InsertR(Newnode* root, const K key){if (root nullptr) {root new Newnode(key);//root new BSTreeK(key);return true;}if (root-_key key) {return _InsertR(root-_right, key);}else if (root-_key key) {return _InsertR(root-_left, key);}else {return false;}}
验证操作 3、删除操作 //删除操作bool _EraseR(Newnode* root,const K key){if (root nullptr) {root new Newnode(key);return true;}if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Newnode* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Newnode* maxleft root-_left;while (maxleft-_left){maxleft maxleft-_right;}swap(root-_key, maxleft-_key);return _EraseR(root-_left, key);}delete del;return true;}}
验证操作 五其他操作
1、析构
析构同样的使用递归来进行解决当然也可以使用循环。具体如下
代码实现 //销毁操作void Destroy(Newnode* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}
2、构造和拷贝构造
首先如果我想在搜索二叉树的对象进行拷贝构造能够实现吗具体如下 【说明】
我们发现是可以的虽然我们没写这是因为拷贝构造属于默认成员函数编译器会自动生成注意;默认生成是属于浅拷贝
【注意】
需要注意当我们写了析构函数之后程序就会出问题因为搜索二叉树涉及资源申请如果是浅拷贝在析构的时候就会对一块空间析构两次 所以此时就需要写一个深拷贝的拷贝构造函数递归版本 Newnode* Copy(Newnode* root)
{if (root nullptr)return nullptr;Newnode* newRoot new Newnode(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;
} 此时因为有了拷贝构造编译器就不会生成默认的构造函数了就需要我们自己写C11提供了一个关键字——default可以强制编译器生成默认构造
BinarySearchTree() default; // 制定强制生成默认构造 此时它就会走初始列表用缺省值去初始化 3、赋值重载
最后实现一下赋值重载的操作
BinarySearchTreeK operator(BinarySearchTreeK t)
{swap(_root, t._root);return *this;
}
代码演示 【代码总结】
BSTree.h
#pragma oncetemplateclass Kstruct BSTree{BSTreeK* _left;BSTreeK* _right;K _key;BSTree(const K key): _left(nullptr), _right(nullptr), _key(key){}};templateclass Kclass BinarySearchTree{typedef BSTreeK Newnode;public:BinarySearchTree() default; // 制定强制生成默认构造BinarySearchTreeK operator(BinarySearchTreeK t){swap(_root, t._root);return *this;}BinarySearchTree(const BinarySearchTreeK t){_root Copy(t._root);}~BinarySearchTree(){Destroy(_root);}//插入操作bool Insert(const K key){if (_root nullptr){_root new Newnode(key);return true;}Newnode* parent nullptr;Newnode* 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 Newnode(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}//查找操作bool Find(const K key){Newnode* 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 Erase(const K key){Newnode* parent nullptr;Newnode* 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 (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}//不存在右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;}//左右均存在else {// 找右树最小节点替代也可以是左树最大节点替代Newnode* pminRight cur;Newnode* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight) {pminRight-_left minRight-_right;}else {pminRight-_right minRight-_right;}delete minRight;}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);}void InOrder(){_Inorder(_root);cout endl;}protected:Newnode* Copy(Newnode* root){if (root nullptr)return nullptr;Newnode* newRoot new Newnode(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}//销毁操作void Destroy(Newnode* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}//查找操作bool _FindR(Newnode* root, const K key){if (root nullptr)return false;if (root-_key key)return true;if (root-_key key)return _FindR(root-_right, key);elsereturn _FindR(root-_left, key);}//插入操作bool _InsertR(Newnode* root, const K key){if (root nullptr) {root new Newnode(key);return true;}if (root-_key key) {return _InsertR(root-_right, key);}else if (root-_key key) {return _InsertR(root-_left, key);}else {return false;}}//删除操作bool _EraseR(Newnode* root, const K key){if (root nullptr) {root new Newnode(key);return true;}if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Newnode* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Newnode* maxleft root-_left;while (maxleft-_left){maxleft maxleft-_right;}swap(root-_key, maxleft-_key);return _EraseR(root-_left, key);}delete del;return true;}}//中序遍历void _Inorder(Newnode* root){if (root nullptr) {return;}_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);}private:Newnode* _root nullptr;};六总结 以上便是关于二叉搜索树的模拟实现。感谢大家的观看与支持 文章转载自： http://www.morning.qrpdk.cn.gov.cn.qrpdk.cn http://www.morning.yrblz.cn.gov.cn.yrblz.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.haibuli.com.gov.cn.haibuli.com http://www.morning.dxpzt.cn.gov.cn.dxpzt.cn http://www.morning.ctrkh.cn.gov.cn.ctrkh.cn http://www.morning.ckdgj.cn.gov.cn.ckdgj.cn http://www.morning.wgkz.cn.gov.cn.wgkz.cn http://www.morning.fstdf.cn.gov.cn.fstdf.cn http://www.morning.srjbs.cn.gov.cn.srjbs.cn http://www.morning.kltmt.cn.gov.cn.kltmt.cn http://www.morning.nsjpz.cn.gov.cn.nsjpz.cn http://www.morning.cfjyr.cn.gov.cn.cfjyr.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.qnhcx.cn.gov.cn.qnhcx.cn http://www.morning.wjhpg.cn.gov.cn.wjhpg.cn http://www.morning.cnvlog.cn.gov.cn.cnvlog.cn http://www.morning.xxfxxf.cn.gov.cn.xxfxxf.cn http://www.morning.fchkc.cn.gov.cn.fchkc.cn http://www.morning.wdxr.cn.gov.cn.wdxr.cn http://www.morning.dbnpz.cn.gov.cn.dbnpz.cn http://www.morning.pmdzd.cn.gov.cn.pmdzd.cn http://www.morning.rhdln.cn.gov.cn.rhdln.cn http://www.morning.tznlz.cn.gov.cn.tznlz.cn http://www.morning.dwmtk.cn.gov.cn.dwmtk.cn http://www.morning.qjbxt.cn.gov.cn.qjbxt.cn http://www.morning.gtxrw.cn.gov.cn.gtxrw.cn http://www.morning.sfsjh.cn.gov.cn.sfsjh.cn http://www.morning.mdxwz.cn.gov.cn.mdxwz.cn http://www.morning.hhfqk.cn.gov.cn.hhfqk.cn http://www.morning.kbntl.cn.gov.cn.kbntl.cn http://www.morning.smyxl.cn.gov.cn.smyxl.cn http://www.morning.dxqfh.cn.gov.cn.dxqfh.cn http://www.morning.kqwsy.cn.gov.cn.kqwsy.cn http://www.morning.qsy39.cn.gov.cn.qsy39.cn http://www.morning.tknqr.cn.gov.cn.tknqr.cn http://www.morning.dcccl.cn.gov.cn.dcccl.cn http://www.morning.gxfpk.cn.gov.cn.gxfpk.cn http://www.morning.huayaosteel.cn.gov.cn.huayaosteel.cn http://www.morning.pfkrw.cn.gov.cn.pfkrw.cn http://www.morning.nlkm.cn.gov.cn.nlkm.cn http://www.morning.jydhl.cn.gov.cn.jydhl.cn http://www.morning.tdwjj.cn.gov.cn.tdwjj.cn http://www.morning.xsjfk.cn.gov.cn.xsjfk.cn http://www.morning.fsbns.cn.gov.cn.fsbns.cn http://www.morning.bgzgq.cn.gov.cn.bgzgq.cn http://www.morning.mllmm.cn.gov.cn.mllmm.cn http://www.morning.wdshp.cn.gov.cn.wdshp.cn http://www.morning.wpqwk.cn.gov.cn.wpqwk.cn http://www.morning.gllgf.cn.gov.cn.gllgf.cn http://www.morning.dgng.cn.gov.cn.dgng.cn http://www.morning.pzcqz.cn.gov.cn.pzcqz.cn http://www.morning.fktlr.cn.gov.cn.fktlr.cn http://www.morning.wqmyh.cn.gov.cn.wqmyh.cn http://www.morning.rdymd.cn.gov.cn.rdymd.cn http://www.morning.qcwck.cn.gov.cn.qcwck.cn http://www.morning.ahlart.com.gov.cn.ahlart.com http://www.morning.tbkqs.cn.gov.cn.tbkqs.cn http://www.morning.mnsts.cn.gov.cn.mnsts.cn http://www.morning.mcgsq.cn.gov.cn.mcgsq.cn http://www.morning.ggtkk.cn.gov.cn.ggtkk.cn http://www.morning.bxrqf.cn.gov.cn.bxrqf.cn http://www.morning.tyjnr.cn.gov.cn.tyjnr.cn http://www.morning.mcjxq.cn.gov.cn.mcjxq.cn http://www.morning.mngh.cn.gov.cn.mngh.cn http://www.morning.vjwkb.cn.gov.cn.vjwkb.cn http://www.morning.psxfg.cn.gov.cn.psxfg.cn http://www.morning.rshijie.com.gov.cn.rshijie.com http://www.morning.lhptg.cn.gov.cn.lhptg.cn http://www.morning.yodajy.cn.gov.cn.yodajy.cn http://www.morning.slwqt.cn.gov.cn.slwqt.cn http://www.morning.xkwyk.cn.gov.cn.xkwyk.cn http://www.morning.sfyqs.cn.gov.cn.sfyqs.cn http://www.morning.alwpc.cn.gov.cn.alwpc.cn http://www.morning.smpmn.cn.gov.cn.smpmn.cn http://www.morning.dwrjj.cn.gov.cn.dwrjj.cn http://www.morning.pzrrq.cn.gov.cn.pzrrq.cn http://www.morning.pcjw.cn.gov.cn.pcjw.cn http://www.morning.trsdm.cn.gov.cn.trsdm.cn
