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

引言：二叉树是自我学习c++以来学习的第一个数据结构，其复杂程度与顺序表，链表等数据结构不是一个量级，学习顺序表时，我感觉如鱼得水，甚至产生"编程也没什么大不了的"的想法,即使我忘记，也可以通过查看源代码很快想起;但这次二叉树的实现，狠狠打了我的脸，为了实现这份让我头大的数据结构，我甚至不得不研究了一份解决问题的方法。我意识到了编程比我想的复杂得多，我不过井底之蛙罢了。我必须将我遇到的困难，解决的方法记录下来，由此，我的第一份技术博客诞生了。

解决问题的方法:

遇到问题->将抽象问题具体化->将具体的问题拆分为多个简单问题->逐个击破->复盘

结合二叉树，谈谈我是如何运用方法的

1.抽象问题具体化

从具体到抽象，是我们理解一件事的根本，二叉树也是这样，因此，在我们了解二叉搜索树的概念：根左边的子树全部小于根节点，跟右边的子树全部大于根节点

图1

通过画图的方式，我们成功将抽象的方式具体化了

2.将具体的复杂问题拆分为多个简单问题

需要实现的结构有

A 树的节点 B树

通过以上图，我们可以发现可以实现的树的功能有:

a 插入数据 b 打印数据 c寻找数据 d 删除数据

3.逐个击破

结构：

A 树的节点

template<class K> class BSTnode { using node = BSTnode<K>; public: BSTnode(const K& key) { _key = key; } node* _right=nullptr; node* _left = nullptr; K _key; };

B 树

template<class K> class BSTtree {

a 插入数据

逻辑：将要插入的数据与二叉树的节点值数据对比，小于节点值向左，大于节点值向右，等于不插入，直到当前指针指向的下一个指针为空，我们将值插到空指针

public: using node = BSTnode<K>; 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，却可以在类内部访问,因此，我在类内部写一个函数用于调用_BSTprint

c寻找数据由于搜索二叉树本身性质的限制，其不可以修改，因此，寻找基本为删除服务 逻辑：将传入的值与树结点的值比较，小于节点值向左，大于节点值向右，等于便找到了，如果下节点指向空，便没有找到

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变成13

3.待删除数据两边都不为空 可以发现： 两边都为空，其根无论是左边还是右边接入的都是空，插入哪一边都不会影响树的结构 一边为空，我们只需要将它的根插入待删除节点的另一边两边都不为空，由于二叉树的特性，我们不能直接删除，会破坏结构，此时我们需要使用到替换法替换法：将待删除节点右边的最左节点或左边的最右节点的数据替换为待删除数据，再将用于替换的节点删除 这两个节点有个特点：一定比待删除节点的左子节点大并且比其右子节点小，替换后不会影响树的结构特例：将待删除节点右边的最左节点或左边的最右节点为空指针，如图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; }

我相信，许多人在使用替换法时回想将RPlaceParent=nullptr,我最开始也是，此时会有什么问题？ 以我的图1为例，假如删除根节点8，此时发生什么？ 答案：最终RPlaceParent=nullptr，可实际上RPlaceParent=10，因此，我们将RPlaceParent=cur,防止出现这种情况 }

自此，二叉树代码实现完成，但这篇博客还未结束，最关键的复盘没有，就违背了我写这篇博客的初衷

4.错误复盘

二叉树实现过程，我的错误有

a.将RPlaceParent赋值为空

b.delete了prve,RPlaceParent父节点，这会导致逻辑混乱

c.将用于试探的值cur,RPlace当成了要删除的值，实际应该用它们的父节点比较

这三个错误，其实都能归因为c,由此次经验，我明白了试探法的核心

方法论

将抽象问题具体化->将具体的问题拆分为多个简单问题->逐个击破->复盘

由此，我的第一篇博客完成