老师，你好，我想问下，关于二分搜索树的删除任意元素，左右孩子均不为空(JS实现)
来源：6-8 深入理解二分搜索树的前中后序遍历
慕标8212032
2018-11-25
老师，你好，我想问下，关于二分搜索树的删除任意元素那里，如果删除的元素左右孩子均不为空的情况下，找到右孩子中的最小值，然后将这个最小值的left指向左孩子，这样也能够实现删除的效果，相比你的思路是将右孩子的最小节点去替代删除的节点来说，我的这个想法有哪些弊端呢，或者说这个想法能不能行得通呢（我测试了好像可以=，=，）
let rightNode = node.right;
let rightMin = this.searchMinimum(node.right); // 找到右节点中最小的节点
rightMin.left = node.left; // 将左节点拼接到右节点最小的节点上
node.left = null;
node.right = null;
return rightNode;
写回答
2回答
-
慕标8212032
提问者
2018-11-25
老师，这个是我的思路，删除53这个元素，跟你讲的思路有点区别032018-11-25 -
liuyubobobo
2018-11-25
我没有实际测试，但猛地看这样是有问题的。我没有看到哪里将rightMin的父亲节点和rightMin断开联系？而原先node的右子树似乎丢失了？
可以尝试用一组随机数据（小数据即可，8-10个元素）创建BST，然后不断删除最小值，不断用中序遍历打印整个树中的所有节点，验证一下整个过程是否正确？
加油！：）
00
相似问题