Java二叉搜索樹刪除

Question

我正在寫一個二叉搜索樹的刪除方法，它不是完整的，但我填充了一棵樹，這樣我至少可以測試我想刪除的節點是葉的情況但它似乎並沒有工作。我的邏輯中有任何明顯的錯誤？

public void delete(E d) 
{ 
    delete(d, root); 
} 

private void delete(E d, Node<E> T) 
{ 
    if(T == null) 
    { 
     return; 
    } 
    else if(d.equals(T.getData())) 
    { 
     System.out.println("it found the node at least"); 
     if(T.getRight() == null && T.getLeft() == null) 
     { 
      T.setData(null); 
     } 
     //do alot) 
    } 
    else if(d.compareTo(T.getData()) > 0) 
    { 
     System.out.println("going right"); 
     delete(d, T.getRight()); 
    } 
    //s is less than T, insert on left subtree 
    else 
    {System.out.println("going left"); 
     delete(d,T.getLeft()); 
    } 

} 

Answer 1

您的代碼不會刪除節點。它只是清除它們。
爲了實現刪除你必須改變你的函數不爲無效，但：

private Node delete(E d, Node<E> T)

而且你的代碼應該是這樣的：

public void delete(E d) { 
    root = delete(d, root); 
} 

private void delete(E d, Node<E> T) 
{ 
    if(T == null) 
    { 
     return; 
    } 
    else if(d.equals(T.getData())) 
    { 
     System.out.println("it found the node at least"); 
     if(T.getRight() == null && T.getLeft() == null) 
     { 
      return null; 
     } 
     //do alot) 
    } 
    else if(d.compareTo(T.getData()) > 0) 
    { 
     System.out.println("going right"); 
     T.right = delete(d, T.getRight()); 
    } 
    //s is less than T, insert on left subtree 
    else 
    { 
     System.out.println("going left"); 
     T.left = delete(d,T.getLeft()); 
    } 

} 

你的想法..