二叉搜索树 - C++ 实现( 二 ) _生活百科

(光这样子讲可能有点抽象, 想象一下把一颗 BST 拍扁, 得到的序列就是中序遍历的序列, 容易得到以上结论)
基于上面的结论, 请考虑以下这两种 case.

case 01/ 有左子树. 所有有可能的 node 的均在左子树
那就意味着, 我们只需要找到 node 左子树中最大的那个节点即可.
case 02/ 无左子树. 需要一直向祖先追溯. 直到找到第一个比 node 小的节点.
第一个找到的节点就是在中序遍历中最接近 node 节点的节点. 也就是 node 的前驱结点.
若找不到, 就说明 node 就是中序遍历中最小的元素, 返回 nil 节点.

具体代码实现如下.

TreeNode *p_pred(int item){TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->left){return p_max(itemNode->left);}else{TreeNode *scan = itemNode->parent;while (scan && scan->left == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;}}

while 退出时, 变量满足: scan == nullptr.(无前驱) 或 node != prev.left ( 等价于 node->data < item) (有前驱)
对应上文提到的两种 case.
查找后继同理, 代码也大差不差. 这里不再赘述. 直接给出代码.

TreeNode *p_succ(int item){TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->right){return p_min(itemNode->right);}else{TreeNode *scan = itemNode->parent;while (scan && scan->right == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;}}

? 插入 Insertion本文给出的是迭代的实现方法, 递归的方法应该很好想, 依据 BST 的定义来写就好了, 这里就省略不写了(偷懒 :p)
依据二叉搜索树的定义查找.
待插入的元素比当前扫描到的元素小就继续扫描左子树, 反之则继续扫描右子树, 直到扫描到nil节点就插入待插入的元素.
给出代码如下.
注意树为空的时候需要特殊处理哈.

void insert(const int item){TreeNode *scan = root;TreeNode *prev = root;while (scan != nullptr){prev = scan;scan = item < scan->data ? scan->left : scan->right;}TreeNode *newNode = new TreeNode(item);if (root){(item < prev->data ? prev->left : prev->right) = newNode;newNode->parent = prev;}else{root = newNode;}return;}

删除 Deletion / Removal删除的情况就相对比较多比较复杂了. BST 的删除需要考虑以下三种情况:

左右子树皆空.
删除节点是叶节点, 将对应的节点置为 nil.
左右子树中只有其中一个非空.
将节点的非空子树重新链接到节点的父节点即可.
左右子树均非空.
这种情况是最棘手的情况. 我们做详细讨论.

情况三很麻烦.
如果也像前两种情况直接删除掉节点, 会出现两个无父节点的子树, 和原节点对应的父节点. 如果这个父节点原本还有两个子树的话, 那就意味着我们要面对三个子树, 和两个待链接的指针, 就必须要合并其中两个子树, 这会使问题会变得相当困难.
我们能不能把第三种情况也转换成前两种情况呢?
我们再仔细揣摩一下前驱和后继的定义.
也许你已经发现了这个性质, BST 中某个节点的前驱和后继一定是满足 case1 或 case2 的. (可以用反证法和前驱后继定义证明. 如果是case3 那么他就不是前驱或后继, 因为还有比该节点更大/小的节点, 不符合定义中的"最")
要是不可以直接删除, 可以做到用替换节点做到等效的删除吗? 怎样替换才可以保持 BST 的性质呢?
保持 BST 结构上的性质也可以说是使树的中序遍历序列结果不变.
我们想到可以用这个节点的前驱或后继来替换掉这个待删除节点. (在后文代码中使用后继, 两个方案都可以实现, 留给读者自行思考~)