递归二进制搜索树删除

Question

注意：如果我的错误在哪里，我已经包含插入代码。

我在删除二叉搜索树中的节点时遇到了问题。我通过eclipse运行它，并且节点的“指针”似乎被重新分配，但只要我退出递归方法，它就会回到节点的方式。

我可能会误解java如何在方法之间传递树节点。

public abstract class BinaryTree<E> implements Iterable<E> { 

    protected class Node<T> { 

     protected Node(T data) { 
      this.data = data; 
     } 

     protected T data; 
     protected Node<T> left; 
     protected Node<T> right; 
    } 

    public abstract void insert(E data); 
    public abstract void remove(E data); 
    public abstract boolean search(E data); 

    protected Node<E> root; 
} 

import java.util.Iterator; 

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> { 

    private Node<E> findIOP(Node<E> curr) { 

     curr = curr.left; 

     while (curr.right != null) { 
      curr = curr.right; 
     } 

     return curr; 
    } 

public Iterator<E> iterator() { 

    return null; 
} 

public static void remove(E data) { 

    if (root != null){ 

     if (data.compareTo(root.data) == 0) { 

      if (root.left == null || root.right == null) { 

       root = root.left != null ? root.left : root.right; 


      } else { 

       Node<E> iop = findIOP(root); 
       E temp = root.data; 
       root.data = iop.data; 
       iop.data = temp; 

       if (root.left == iop) { 

        root.left = root.left.left; 

       } else { 

        Node<E> curr = root.left; 

        while (curr.right != iop) { 
         curr = curr.right; 
        } 
        curr.right = curr.right.left; 
       } 
      } 

     } else { 

      if (data.compareTo(root.data) < 0) { 

       remove(root.left ,data); 

      } else { 

       remove(root.right ,data); 

      } 
     } 

    } 
} 

private void remove (Node<E> node, E data){ 

    if (data.compareTo(node.data) == 0) { 

     if (node.left == null || node.right == null) { 


      if (node.left != null) { 
            // Problem is either here 
       node = node.left; 

      } else { 
            // or here 
       node = node.right; 
      } 


     } else { 

      Node<E> iop = findIOP(node); 
      E temp = node.data; 
      node.data = iop.data; 
      iop.data = temp; 

      if (node.left == iop) { 

       node.left = node.left.left; 

      } else { 

       Node<E> curr = node.left; 

       while (curr.right != iop) { 
        curr = curr.right; 
       } 
       curr.right = curr.right.left; 
      } 
     } 
    } else { 

     if (data.compareTo(node.data) < 0) { 

      remove(node.left ,data); 

     } else { 

      remove(node.right ,data); 

     } 
    } 

} 

} 

当我插入：

tree.insert(10); 
tree.insert(15); 
tree.insert(6); 
tree.insert(8); 
tree.insert(9); 

然后

tree.remove(8); 

System.out.println(tree.root.left.right.data); 

仍然是8而不是9.

去除的在根部和工作如果除去指针适当地重新分配从 root.left和root.right。

任何建议，将不胜感激。

编辑：我似乎已经缩小了这个问题。我实现了一个迭代版本，其中我使root = curr并更改curr.left.right = curr.left.right.right。我注意到，当我将节点= root.left.right传递给递归函数将节点更改为node.right时，此更改反映了我的根节点，而不反映根中的更改。为什么是这样？

缩小了一些。为什么node.left = node.left.left对我的树进行更改并且node = node.left什么也不做。

我通过递归重新分配父节点来修复它，而不是递归地重新分配子节点。这是由此产生的私人和公共职能。

public void remove(E data) { 

    Node<E> curr; 

    if (root != null) { 
     if (data.compareTo(root.data) == 0) { 
      if (root.left == null || root.right == null) { 
       root = root.left != null ? root.left : root.right; 
      } 
      else { 
       Node<E> iop = findIOP(root); 
       E temp = root.data; 
       root.data = iop.data; 
       iop.data = temp; 
       if (root.left == iop) { 
        root.left = root.left.left; 
       } 
       else { 
        curr = root.left; 
        while (curr.right != iop) { 
         curr = curr.right; 
        } 
        curr.right = curr.right.left; 
       } 
      } 
     } else if (data.compareTo(root.data) < 0) { 
      root.left = remove(data, root.left); 
     } else { 
      root.right = remove(data, root.right); 
     } 
    } 
} 

private Node<E> remove(E data, Node<E> node){ 

    Node<E> curr; 

    if (node != null){ 
     if (data.compareTo(node.data) == 0) { 
      if (node.left == null || node.right == null) { 
       node = node.left != null ? node.left : node.right; 
       return node; 
      } else { 

       Node<E> iop = findIOP(node); 
       E temp = node.data; 
       node.data = iop.data; 
       iop.data = temp; 
       if (node.left == iop) { 
        node.left = node.left.left; 
        return node; 
       } else { 
        curr = node.left; 
        while (curr.right != iop) { 
         curr = curr.right; 
        } 
        curr.right = curr.right.left; 
        return node; 
       } 
      } 
     } else { 
      if (data.compareTo(node.data) < 0) { 
       node.left = remove(data, node.left); 
       if (node.left != null){ 
        return node.left; 
       } 
      } else { 
       node.right = remove(data, node.right); 
       if (node.right != null){ 
        return node.right; 
       } 
      } 
      // if node.left/right not null 
      return node; 
     } 
    } 
    // if node = null; 
    return node; 
} 

Answer 1

当你说“我可能误解了java如何在方法之间传递树节点”时，你确实是对的。试想一下：

public class Ref { 
    public static void main(String args[]) { 
     Integer i = new Integer(4); 
     passByRef(i); 
     System.out.println(i); // Prints 4. 
    } 

    static void passByRef(Integer j) { 
     j = new Integer(5); 
    } 
} 

虽然i是“按引用传递”，参考i本身不被改变的方法，只有j指事。换句话说，j初始化为参考文献i的副本，即j最初是指与i（但最重要的不是i）相同的对象。指定j来引用其他内容对i所指的内容没有影响。

为了实现你想要的搜索，我建议你将新的引用返回给调用者。例如，一些类似于以下变化：

public class Ref { 
    public static void main(String args[]) { 
     Integer i = new Integer(4); 
     i = passByRef(i); 
     System.out.println(i); // Prints 5. 
    } 

    static Integer passByRef(Integer j) { 
     j = new Integer(5); 
     return j; 
    } 
}