从解决问题的角度从零实现二插树

引言二叉树是自我学习c以来学习的第一个数据结构其复杂程度与顺序表链表等数据结构不是一个量级学习顺序表时我感觉如鱼得水甚至产生编程也没什么大不了的的想法,即使我忘记也可以通过查看源代码很快想起;但这次二叉树的实现狠狠打了我的脸为了实现这份让我头大的数据结构我甚至不得不研究了一份解决问题的方法。我意识到了编程比我想的复杂得多我不过井底之蛙罢了。我必须将我遇到的困难解决的方法记录下来由此我的第一份技术博客诞生了。解决问题的方法:遇到问题-将抽象问题具体化-将具体的问题拆分为多个简单问题-逐个击破-复盘结合二叉树谈谈我是如何运用方法的1.抽象问题具体化从具体到抽象是我们理解一件事的根本二叉树也是这样因此在我们了解二叉搜索树的概念根左边的子树全部小于根节点跟右边的子树全部大于根节点图1通过画图的方式我们成功将抽象的方式具体化了2.将具体的复杂问题拆分为多个简单问题需要实现的结构有A 树的节点 B树通过以上图我们可以发现可以实现的树的功能有:a 插入数据 b 打印数据 c寻找数据 d 删除数据3.逐个击破结构A 树的节点templateclass K class BSTnode { using node BSTnodeK; public: BSTnode(const K key) { _key key; } node* _rightnullptr; node* _left nullptr; K _key; };B 树templateclass K class BSTtree {a 插入数据逻辑将要插入的数据与二叉树的节点值数据对比小于节点值向左大于节点值向右等于不插入直到当前指针指向的下一个指针为空我们将值插到空指针public: using node BSTnodeK; void Insert(const K key) { if (_root nullptr)特殊:无根树此时直接插入{ _root new node(key);//_root是根节点在b步骤中代码 return; } node* prve nullptr; node* cur _root;//用于试探下一次是否为空 while (cur) { if (cur-_key key) { prve cur; cur cur-_left; } else if (cur-_key key) { prve cur; cur cur-_right; } else { return; } }//此时cur使我们要插入的节点1 /*cur new node(key); if (cur-_key key) //我的第一个错误将要插入值的cur用于比较,此时cur- _key key恒成立 { prve-_left newnode; } else if (cur-_key key) { prve-_right newnode; }*/正确做法将代插入值的上一节点prve与key比较 node* newnode new node(key); if (prve-_key key) { prve-_left newnode; } else if (prve-_key key) { prve-_right newnode; }b 打印数据为了验证实现的功能打印作为第二步是最合理的 打印逻辑传入根并利用中序遍历迭代 中序遍历一直向左遍历直到下一节点指向空打印当前节点并回退到上一节点并继续向左遍历循环此动作直到全部遍历完成private: void _BSTprint(node* root) { if (root nullptr) { return; } _BSTprint(root-_left); cout root-_key ; _BSTprint(root-_right); } node* _root nullptr; };public:void BSTprint() { _BSTprint(_root);//只能在类内访问该类的private cout endl; }由于不能在对象中访问private的—_root却可以在类内部访问,因此我在类内部写一个函数用于调用_BSTprintc寻找数据由于搜索二叉树本身性质的限制其不可以修改因此寻找基本为删除服务 逻辑将传入的值与树结点的值比较小于节点值向左大于节点值向右等于便找到了如果下节点指向空便没有找到bool find(const K key) { //node* prve nullptr; 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; }d 删除数据通过绘制的图可以发现删除数据会遇到的情况有: 1.待删除数据左右都为空 2.待删除数据左右一边为空特例单叉树如图2此时我们如果想要删除根节点需要将根12变成133.待删除数据两边都不为空 可以发现 两边都为空其根无论是左边还是右边接入的都是空插入哪一边都不会影响树的结构 一边为空我们只需要将它的根插入待删除节点的另一边两边都不为空由于二叉树的特性我们不能直接删除会破坏结构此时我们需要使用到替换法替换法将待删除节点右边的最左节点或左边的最右节点的数据替换为待删除数据再将用于替换的节点删除 这两个节点有个特点一定比待删除节点的左子节点大并且比其右子节点小替换后不会影响树的结构特例将待删除节点右边的最左节点或左边的最右节点为空指针如图1节点8此外我们还要考虑待删除节点的父节点与待删除节点的关系父节点在待删除节点的左边还是右边bool erease(const K key) { node* prve nullptr; node* cur _root; while (cur) { if (cur-_key key) { prve cur; cur cur-_left; } else if (cur-_key key) { prve cur; cur cur-_right; } else { if (cur-_right nullptr) { //单叉树 if (prve nullptr) { _root cur-_left; } //正常情况,无双子,右边为空 else { if (prve-_left cur) { prve-_left cur-_left; } else if (prve-_right cur) { prve-_right cur-_left; } } delete cur; return true; } else if (cur-_left nullptr) { //单叉树 if (prve nullptr) { _root cur-_right; } //正常情况,无双子,左边为空 else { if (prve-_left cur) { prve-_left cur-_right; } else if (prve-_right cur) { prve-_right cur-_right; } } delete cur; return true; } //双子,替换法,左右都不为空 else { node* RPlaceParent cur; node* RPlace cur-_right; while (RPlace-_left)//出循环后左边指向空 { RPlaceParent RPlace; RPlace RPlace-_left; } cur-_key RPlace-_key; //赋值到右边 if (RPlaceParent-_left RPlace) { RPlaceParent-_left RPlace-_right; } else if (RPlaceParent-_right RPlace) { RPlaceParent-_right RPlace-_right; } delete RPlace; return true; } } }return false; }我相信许多人在使用替换法时回想将RPlaceParentnullptr,我最开始也是此时会有什么问题 以我的图1为例假如删除根节点8此时发生什么 答案最终RPlaceParentnullptr可实际上RPlaceParent10因此我们将RPlaceParentcur,防止出现这种情况 }自此二叉树代码实现完成但这篇博客还未结束最关键的复盘没有就违背了我写这篇博客的初衷4.错误复盘二叉树实现过程我的错误有a.将RPlaceParent赋值为空b.delete了prve,RPlaceParent父节点这会导致逻辑混乱c.将用于试探的值cur,RPlace当成了要删除的值实际应该用它们的父节点比较这三个错误其实都能归因为c,由此次经验我明白了试探法的核心方法论将抽象问题具体化-将具体的问题拆分为多个简单问题-逐个击破-复盘由此我的第一篇博客完成