Java二進制搜索樹沒有子項的刪除節點

Question

我正在處理要刪除的節點是節點的情況。我不確定是否需要跟蹤父項，以便當我找到要刪除的節點時，可以將它的父項指針設置爲null。但是，我怎麼知道要刪除的節點是哪個孩子？我是否需要更多的陳述？

任何幫助表示讚賞，我覺得它不是太複雜，但我只是困惑如何實際擺脫節點。

這是我到目前爲止有：

public void insert(E s) 
{ 
    root = insert(s, root); 
} 

private Node<E> insert(E s, Node<E> T) 
{ 
    //easiest case, empty tree, create new tree 
    if(T == null) 
    { 
     T = new Node<E>(s); 
    } 
    //easiest case, found s 
    else if(s.compareTo(T.getData()) == 0) 
    { 
     System.out.println("Item already present."); 
    } 
    //s is greater than T, insert on right subtree 
    else if(s.compareTo(T.getData()) > 0) 
    { 
     T.setRight(insert(s, T.getRight())); 
    } 
    //s is less than T, insert on left subtree 
    else 
    { 
     T.setLeft(insert(s,T.getLeft())); 
    } 
    return T; 
} 

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

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

    if(T == null) 
    { 

    } 
    else if(d.equals(T.getData())) 
    { 
     System.out.println("it found the node at least"); 
     if(T.getRight() == null && T.getLeft() == null) 
     { 

     } 
     //code other cases for a node with one child and node with two  children 
    } 
    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

public Node<E> search(Node<E> node, E d) 
{ 
    while(node!=null && ((node.getLeft()!=null && !node.getLeft().getData().equals(d)) || (node.getRight()!=null && !node.getRight().getData().equals(d))) 
    { 
     if(d.compareTo(node.getData()) < 0) 
     { 
      node = node.getLeft(); 
     } 
     else 
     { 
      node = node.getRight(); 
     } 
    } 

    return node; 
} 

private void delete(E d) 
{ 
    // Search the node 
    Node parent = search(root, d); 

    // parent is the parent node under which the required node is present 
    // Now check which child it is - left or right 
    if(parent == null) 
    { 
     System.out.println("Element not found"); 
     return; 
    } 

    if(parent.getLeft().getData().equals(d)) 
    { 
     // Left child 
     parent.setLeft(null); 
    } 
    else 
    { 
     // Right child 
     parent.setRight(null); 
    } 
} 

注：如果你想在Node<E>有parent節點那就已經很不容易。

Answer 2

如果您不想更改節點結構，則像這樣遍歷樹來跟蹤父節點。

private Node<E> parent; 
public void insert(E s) 
{ 
    root = insert(s, root); 
} 

private Node<E> insert(E s, Node<E> T) 
{ 
    //easiest case, empty tree, create new tree 
    if(T == null) 
    { 
     T = new Node<E>(s); 
    } 
    //easiest case, found s 
    else if(s.compareTo(T.getData()) == 0) 
    { 
     System.out.println("Item already present."); 
    } 
    //s is greater than T, insert on right subtree 
    else if(s.compareTo(T.getData()) > 0) 
    { 
     T.setRight(insert(s, T.getRight())); 
    } 
    //s is less than T, insert on left subtree 
    else 
    { 
     T.setLeft(insert(s,T.getLeft())); 
    } 
    return T; 
} 

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

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

    if(T == null) 
    { 

    } 
    else if(d.equals(T.getData())) 
    { 
     System.out.println("it found the node at least"); 
     if(T.getRight() == null && T.getLeft() == null) 
     { 
      if (parent != null){//For the first node, parent will be null 
        if (d.equals(parent.getRight().getData())){//Data matches with the right node of parent 
         parent.setRight(null); 
        }else{//Data matches with the left node of parent 
         parent.setLeft(null); 
        } 
        //Reset parent node 
        parent = null; 
      } 
     } 
     //code other cases for a node with one child and node with two  children 
    } 
    else if(d.compareTo(T.getData()) > 0) 
    { 
     parent = T;// Make the current node as parent 
     System.out.println("going right"); 
     delete(d, T.getRight()); 
    } 
    //s is less than T, insert on left subtree 
    else 
    { 
     parent = T;// Make the current node as parent 
     System.out.println("going left"); 
     delete(d,T.getLeft()); 
    } 

}