在BST中刪除節點

Question

我正在從BST中刪除節點的方法。在同樣的方法中，我遞歸搜索要刪除的節點以及保存該節點的父節點。但是，唯一的問題是，我不確定如何在case2中使根節點等於父節點（因爲刪除發生在父節點中）。

public Node delete(Node root, int data) 
{ 

    // base case - if tree is empty 
    if (root == null) 
     return root; 

    // find the node to be deleted and keep track of parent 
    if (data < root.data) 
    { 
     parent = root; 
     System.out.println("parent node: " + parent.data); 
     root.left = delete(root.left, data); 
    } 
    else if (data > root.data) 
    { 
     parent = root; 
     System.out.println("parent node: " + parent.data); 
     root.right = delete(root.right, data); 


    // delete node 
    } 
    else 
    { 
     // case 1: deletion node has no subtrees 
     if (root.left == null && root.right == null) 
     { 
      System.out.println(data + " successfully deleted from tree (case1)"); 
      root = null; 
     } 

     // case 2: deletion node has only one subtree 
     else if (root.left != null && root.right == null) 
     { 
      Node temp = root.left; 
      if(parent.left.data == root.left.data) 
      { 
       parent.left = null; 
       System.out.println(data + " successfully deleted from tree (case2)"); 
       parent.left = temp; 
       root = parent; // parent was sent when searching for the node 

      } 
      else if(parent.right.data == root.data) 
      { 
       parent.right = null; 
       System.out.println(data + " successfully deleted from tree (case2)"); 
       parent.left = temp; 
       root = parent; // parent was sent when searching for the node 
      } 

     } 
     else if (root.left == null && root.right != null) 
     { 
      // same logic 
     } 
    } 

    return root; 

} 

Answer 1

您應該添加另一個函數來調用你的刪除功能爲

​​

這是可行的，但THRE的更好的方式做刪除。這裏：http://www.algolist.net/Data_structures/Binary_search_tree/Removal