二叉排序树的删除操作的实现(思路分析)

二叉排序树的删除操作的实现(思路分析)

这里我们先给出一个示意图:(我们就根据这个示意图中的内容进行删除)

二叉排序树的删除情况比较复杂, 有下面三种情况要进行考虑:

• 因为我们的二叉排序树删除结点之后肯定是要求还要是一个二叉排序树, 所以删除操作就会比较复杂, 但是其实对于数据结构我们只要理清思路, 只要考虑的足够准确和深入一般是没有什么问题的

1. 删除叶子结点 ( 比如: 2 , 5 , 9 ,12 )
2. 删除只有一个子树的结点 ( 比如: 1 )
3. 删除有两颗子树的结点 (比如: 7 3 10)

第一种情况(删除叶子结点):

思路分析:

1. 需要先找到要删除的结点targetNode
2. 要找到target结点的父节点parent
3. 确定targetNode是parent结点的左子结点还是右子节点
4. 根据前面的情况来对应删除
   1. 如果targetNode是parent结点的左子结点
      • parent.left = null;
   2. 如果targetNode是parent结点的右子节点
      • parent.right = null;

难点分析:

之前我们讲解链表的时候对于链表这种链式结构删除结点操作的时候我们只用找到待删除结点的父节点就可以了, 但是这个时候对于树结构为什么删除的时候不仅仅要找到带删除结点的父节点, 还要找到待删除结点?

• 这其实就是因为我们链表是一个单分支结构, 我们删除的时候只要找到待删除的父节点之后让父节点指向待删除结点的下一个节点即可, 但是此时我们是在执行二叉树结构的删除操作, 我们二叉树删除结点的因为不仅仅一个分支, 二叉树有两个分支, 所以删除之前我们要先确定我们当前结点是做父节点的左子节点还是右子节点, 判断之后我们还要知道我们当前结点是否有子节点, 就要继续遍历判断, 所以要判断待删除结点是否有子节点, 如果有的话升值要判断是左子节点还是右子节点, 又或者是两个子节点都有, 我们要使用待删除结点执行很多判断, 所以我们就要将待删除结点使用一个引用保存下来

  • 如果不使用targetNode引用将待删除结点保存下来的话也是可以解决这个问题, 但是解决的时候就会复杂很多

第二种情况(删除只有一颗子树的结点)

思路分析:

1. 要先找到待删除的结点targetNode

2. 找到targetNode的父节点parent

3. 确定targetNode的子节点是一个左子节点还是右子节点

4. 判断targetNode是parent的左子节点还是右子节点

5. 如果targetNode有左子节点

   5.1 并且如果targetNode是parent结点的左子节点

   • parent.left = target.left

   5.2 并且如果targetNode是parent结点的右子节点

   • parent.right = target.left

6. 如果targetNode有右子节点

   6.1 并且如果targetNode是parent结点的左子节点

   • parent.left = targetNode.right

   6.2. 并且如果targetNode是parent结点的右子节点

   • parent.right = targetNode.right

第三种情况(删除有两颗子树的结点)

思路分析:

1. 先找到待删除结点targetNode
2. 找到targetNode的父节点parent
3. 从targetNode结点的右子树上找到值最小的结点
   • 这个时候其实我们还可以是寻找左子树上最大的值的结点
4. 用一个临时变量temp将最小结点的值保存下来
5. 删除该最小的结点
6. 执行targetNode.value = temp

难点分析:

1. 为什么我们是要找targetNode结点的右子树上的最小值的结点?
   • 因为这个时候我们删除的结点的位置将要补充的结点的值一定是要大于所有的左子树上的结点, 一定是要小于所有的右子树上的结点, 所以这时候我们要么就去找右子树上最小的结点, 将这个右子树上最小的结点删除之后并将这个值赋给我们待删除结点, 这样我们其实就等价于我们删除了我们的待删除结点, 或者同样的我们也就可以是删除一个左子树上的最大的结点, 因为左子树上最大的结点不上之后肯定就会是大于其余的所有的左子树上的结点

我们可以发现删除二叉排序树中的结点的时候不管是删除叶子节点还是删除有一个子树的结点又或者是删除有两个子树的结点的时候都要查找到待删除结点targetNode ,和待删除结点的父节点parent