具有2个子节点的BST删除节点未删除前任节点

Question

我正在努力从BST中删除节点。当前，它适用于没有孩子或一个孩子的所有情况。当我删除一个有2个子节点的节点时，该节点将被删除，但是由于我认为代码占该字段的原值，但前值不会更改为null，但没有任何变化。

   public Node(String w, Node p, Node l, Node r) {
         //value = v;
         word = w;
         parent = p;
         left = l;
         right = r;
      }
   public void remove(String target) {
      if (root == null) {
         return;
      }
      if (root.word.compareTo(target) == 0)
      {
         removeRoot(target);
      }
      else {
         removeNonRoot(target);
      }
   }
   private void removeNonRoot(String target) {

      Node cur = root;
      Node parent = null;

      while (cur != null) {
         if (cur.word.compareTo(target) == 0) {
            break;
         }
         if (target.compareTo(cur.word) < 0) {
            if (cur.left != null) {
               parent = cur;
               cur = cur.left;
            }
         }
         else if (target.compareTo(cur.word) > 0) {
            if (cur.right != null) {
               parent = cur;
               cur = cur.right;
            }
         }
      }
     if (cur.left == null && cur.right == null)
      {
         if (parent.left != null && parent.left.word.compareTo(target) == 0) {
            parent.left = null;
         }
         else if (parent.right != null && parent.right.word.compareTo(target) == 0)
         {  
            parent.right = null;
         }
      }
      else if (cur.left == null && cur.right != null) {
         if (parent.right != null && parent.right.word.compareTo(target) == 0) {
            parent.right = cur.right;
         }
         else if (parent.left != null && parent.left.word.compareTo(target) == 0) {
            parent.left = cur.right;
         }
      }
      else {
         Node temp = findPredecessor(target, parent);
         cur.word = temp.word;
      }
   }
private void removeRoot(String target) {
   // only root
      if (root.left == null && root.right == null)
      {
         root = null;
         return;
      }
      // right child
      else if (root.left == null)
      {
         root = root.right;
         return;
      }
      // left child
      else if (root.right == null)
      {
         root = root.left;
      }
      // 2 children
      else
      {
         Node temp = findPredecessor(target, root);
         root.word = temp.word;
         return;
      }
   }

private Node findPredecessor(String s, Node start) {
      Node parent = start;
      Node child = start.left;

      if (child == null) {
         return parent;
      }
      else if (child != null) {
         while (child.right != null) {
            child = child.right;
         }
         Node temp = child;
         child.right = null;
         return temp;
      }
      else {
         return null;
      }
}

如果我有一个bst，并且按以下顺序插入了字符：e-> f-> c-> a-> d尝试删除c的结果将返回d，其中c是，但是d的右子树也会d。

这会让我相信问题出在我的前任方法中，我称之为child.right = null。我认为实际上并没有分配值，但是不确定为什么。清除结果图：

Answer 1

遵循整个逻辑和您要实现的目标有点困难，但是，对代码进行初步验证后，我认为主要问题是您没有更新节点上的父信息。

例如：将cur.right分配给parent.right或parent.left时，还应该更新parent上的parent.right以正确反映父节点。

else if (cur.left == null && cur.right != null) {
   if (parent.right != null && parent.right.word.compareTo(target) == 0) {
      parent.right = cur.right;
   } else if (parent.left != null && parent.left.word.compareTo(target) == 0) {
      parent.left = cur.right;
   }
   // Update parent information of `cur.right`
   cur.right.parent = parent;
}

您应确保在逻辑中更新所有此类实例，以使所有子节点正确反映其父节点。