[已解决]二叉树删除有左右儿子的节点，是如何实现的？

我是一个椭圆

从二叉树中删除一个元素
        先获取 待删除节点 item 的父节点
        如果父节点不为空，
            判断 item 的左右子树
            如果左子树为空，那么判断 item 是父节点的左孩子，还是右孩子，如果是左孩子，将父节点的左指针指向 item 的右子树，反之将父节点的右指针指向 item 的右子树
            如果右子树为空，那么判断 item 是父节点的左孩子，还是右孩子，如果是左孩子，将父节点的左指针指向 item 的左子树，反之将父节点的右指针指向 item 的左子树
            如果左右子树均不为空，寻找右子树中的最左叶子节点 x ，将 x 替代要删除的节点。
        删除成功，返回 True
        删除失败, 返回 False
在加粗下划线这里，为什么要用右儿子书中最左子叶节点来替换？？？

最佳答案

月排行榜 / 总排行榜

19304270021304

2020-2-23 19:06:20

如果这是一棵普通二叉树，只要任意一个叶节点来替换就可以了。这里应该是针对排序二叉树（搜索二叉树），以下面这种情况为例：对于每颗子树，左儿子值<根节点值<右儿子值，这样构建起来的二叉树执行删除操作同时又保证构建规则不变，就要按楼主划线的操作进行。原因是：我们期望找到一个叶节点 （设值为x），来替换待删除节点，使得待删除节点的左儿子值<x<右儿子值，那这样的首先必须满足大于待删除节点的左儿子值，也就意味着它必定在待删除节点的右子树中，而x还要小于待删除节点的右儿子值，那它一定是右子树中最小的节点，也就是最左节点（实际上并不一定是叶节点，如果不是，把它的右子树接到它原来的位置就可以）。那么同理，也可以寻找待删除节点左子树中的最右节点来进行替换，道理都是一样的。

跳转到最佳答案楼层

19304270021304

如果这是一棵普通二叉树，只要任意一个叶节点来替换就可以了。这里应该是针对排序二叉树（搜索二叉树），以下面这种情况为例：对于每颗子树，左儿子值<根节点值<右儿子值，这样构建起来的二叉树执行删除操作同时又保证构建规则不变，就要按楼主划线的操作进行。原因是：我们期望找到一个叶节点 （设值为x），来替换待删除节点，使得待删除节点的左儿子值<x<右儿子值，那这样的首先必须满足大于待删除节点的左儿子值，也就意味着它必定在待删除节点的右子树中，而x还要小于待删除节点的右儿子值，那它一定是右子树中最小的节点，也就是最左节点（实际上并不一定是叶节点，如果不是，把它的右子树接到它原来的位置就可以）。那么同理，也可以寻找待删除节点左子树中的最右节点来进行替换，道理都是一样的。

我是一个椭圆

19304270021304 发表于 2020-2-25 00:21
如果这是一棵普通二叉树，只要任意一个叶节点来替换就可以了。这里应该是针对排序二叉树（搜索二叉树），以 ...

我用的是实验楼网站的课程，跟着学习数据结构，里面很多东西都不讲详细的，写这个二叉树也没说什么指定的二叉树，我以为就是普通二叉树，那个网站有些坑

Max472

19304270021304 发表于 2020-2-23 19:06
如果这是一棵普通二叉树，只要任意一个叶节点来替换就可以了。这里应该是针对排序二叉树（搜索二叉树），以 ...

我还奇怪为什么不是左子树的最右节点呢 原来都可以