大家好，我是Lampard~~
很高兴又能和大家见面了，接下来准备系列更新的是算法题，一日一练，早日升仙！
今天的问题是：
构造二叉搜索树并且实现删除功能。
解题思路：
首先我们要理解删除分多少种情况，每一种情况要如何处理。那我也不卖关子了，请看图：
并把其父亲的子结点设为NULL，又因为不知道被选中结点时其父亲的左孩子还是右孩子，所以我们需要进行判断。
// 如果寻找的是叶子结点，则直接删除 if (node->isLeaf()) { if (node->isLeftChild() == true) { // 是左孩子则把其父亲的左孩子置空 node->getFather()->DeleteLeftChild(); delete node; } else if (node->isLeftChild() == false) { // 同理是右孩子则把其父亲的右孩子置空 node->getFather()->DeleteRightChild(); delete node; } }并且把被选中结点的孩子和其父亲联起来就可以了。这时候有四种情况！！！！！！
被选中结点是父亲的左孩子，结点的左孩子为空。被选中结点是父亲的左孩子，结点的右孩子为空 被选中结点是父亲的右孩子，结点的左孩子为空。被选中结点是父亲的右孩子，结点的右孩子为空
// 如果寻找的结点是单支(只有一个孩子) // 分四种情况(我是父亲的左孩子，我的左孩子为空。我是父亲的左孩子，我的右孩子为空) // (我是父亲的右孩子，我的左孩子为空。我是父亲的右孩子，我的右孩子为空) // 第一种情况 else if (node->getLeftChild() == NULL && node->isLeftChild()==true) { node->getFather()->setLeftChild(node->getRightChild()); // 把我父亲的左孩子(我原来的位置)更改为我的右孩子 node->getRightChild()->setFather(node->getFather()); // 把我的右孩子的父亲改为我父亲 delete node; } // 第二种情况 else if (node->getRightChild() == NULL && node->isLeftChild()== true) { node->getFather()->setLeftChild(node->getLeftChild()); node->getLeftChild()->setFather(node->getFather()); delete node; } //第三种情况 else if (node->getLeftChild() == NULL && node->isLeftChild() == false) { node->getFather()->setRightChild(node->getRightChild()); node->getRightChild()->setFather(node->getFather()); delete node; } // 第四种情况 else if (node->getRightChild() == NULL && node->isLeftChild() == false) { node->getFather()->setRightChild(node->getLeftChild()); node->getLeftChild()->setFather(node->getFather()); delete node; }
如果被选中结点有2个孩子，那么需要把右子树中最小，或者左子树中最大的结点（我称为幸运儿），然后把幸运儿的值赋值给被选中结点，接着删除幸运儿。记住了！是删除幸运儿，而不是被选中结点，不要搞混！！！
我们为什么这样做呢？
因为，左子树最大或者右子树最小的值放在被删除的位置上，
才不会违背二叉搜索树的原则（左子树的所有元素都比自己小，右子树所有都比自己大）
我以选择右子树最小结点举例，假如你选择的不是最小，而是倒数第二小会怎么样？
那是不是就在右子树中存在着一个比自己小的家伙？
那我是不是就违反了二叉搜索树的原则？
所以我们只能选择这两种情况。OK我们接着往下说，
那么既然把值赋给了被删除的结点之后，我们要怎么删除这个幸运儿呢？
（1）如果这个幸运儿是叶子结点，我们就回归到1的情况
（2）如果这个幸运儿是单支结点（只有一个子树），就回到我们2的情况
什么？你问我幸运儿有没有可能有两个子树？根本不可能，因为如果有两个子树的话，自己的最值就不能取到了
else if (node->getLeftChild() != NULL && node->getRightChild() != NULL) { // 自己是父亲的左孩子 getSmallRightChild(node->getRightChild()); // 把第一个进队列的取出，然后清空队列 BinaryTreeNode* theNode = NodeQueue.front(); while (!NodeQueue.empty()) { NodeQueue.pop(); } if (theNode->isLeaf()) // 是叶子 { node->setData(theNode->getData()); theNode->getFather()->DeleteLeftChild(); } else if (theNode->isLeaf() == false) //证明它有右子树 { theNode->getFather()->setLeftChild(theNode->getRightChild()); theNode->getRightChild()->setFather(theNode->getFather()); node->setData(theNode->getData()); } }
那么我们怎么找到幸运儿呢？我们以找右子树最小值为例，
只需要用一个队列存起中序遍历的输出数据，，然后第一个就是了嘻嘻
不过记得队列每次用完要清0哦
最后我们看看测试结果：
树长这样
