原创

二叉排序树

温馨提示:
本文最后更新于 2022年06月18日,已超过 8 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

二叉排序树

二叉排序树的特点:左子节点的值要小于父节点的值,右子节点的值要大于父节点的值

特别的:如果两个子节点的值都相同,那就不用

二叉排序树的删除

  1. 如果待删除的节点只有一个子节点
  2. 如果待删除的节点有两个子节点
  3. 如果删除的是叶子节点

分析

删除的是叶子节点

找到需要删除的节点的父节点,将待删除的节点置空

删除的节点有一个子节点

  • 待删除节点是父节点的左子节点

    • 待删除节点的左子节点上存在节点

      parent.left = parent.left.left;

    • 待删除节点的右子节点上存在节点

      parent.left = parent.left.right;

  • 待删除节点是父节点的右子节点

    • 待删除节点的左子节点上存在节点

      parent.right = parent.left.left;

    • 待删除节点的右子节点上存在节点

      parent.right = parent.left.right;

删除的节点上存在两个节点

  • 向左边找到最大的节点,或者向右边找到最小的节点将此节点赋给一个临时变量,将该节点删除,之后再将该临时节点赋值给待删除的节点
正文到此结束