欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 文化 > 450.删除二叉搜索树中的节点

450.删除二叉搜索树中的节点

2025/9/19 11:16:18 来源:https://blog.csdn.net/weixin_62906298/article/details/147373078  浏览:    关键词:450.删除二叉搜索树中的节点

思路:根据目标值不断向左或向右递归,找到目标节点(或者最后没找到)之后对节点进行删除操作

有以下五种情况:(这些都算是终止条件里的操作)

  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
    • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
    • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
    • 第五种情况:左右孩子节点都不为空:
      根据二叉搜索树的性质,右子树每个节点的值都比该目标节点值大,也大于左子树的根节点。
      右子树最左边的节点是右子树最小值,因此将左子树根节点放在右子树最左边节点的左孩子节点位置即可(左右子树逻辑一样,处理一种即可)
      将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。

还是跟上题一样,通过返回值接收来达到父节点与孩子节点(或者树)之间的绑定关系。

增加节点和删除节点的区别:

二叉搜索树添加节点只需要在叶子上添加就可以的,不涉及到结构的调整,而删除节点操作涉及到结构的调整

依然使用递归函数的返回值来完成把节点从二叉树中移除的操作。

这里最关键的逻辑就是第五种情况(删除一个左右孩子都不为空的节点)。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词