遞歸二進制搜索樹刪除

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; 
    } 
}