從BST

Question

刪除節點，我認爲我得到了大多數情況下，除了2的情況下工作（刪除節點只有一個子樹）。我的測試用例是下面沒有1,2,3和4節點的樹：

這個程序告訴我從樹中刪除了6個，但是當我嘗試打印樹時，它仍然顯示6是在那個樹。

public class RandomNode { 

static int size; 

public static class Node { 

    int data; 
    Node left; 
    Node right; 

    public Node(int data) { 

     this.data = data; 
     left = null; 
     right = null; 
     size++; 
    } 

} 

// delete node in right subtree 
public Node delete(Node root, int data) { 
    // base case - if tree is empty 
    if (root == null) 
     return root; 

    // search for deletion node 
    else if (data < root.data) 
     root.left = delete(root.left, data); 
    else if (data > root.data) { 
     root.right = delete(root.right, data); 

    } else { 

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

      // case 2: deletion node has only one subtree 
     } else if (root.left != null && root.right == null) { 
      root = root.left; 
      size--; 
      System.out.println(data + " successfully deleted from tree (case2a)"); 
     } else if (root.left == null && root.right != null) { 
      root = root.left; 
      size--; 
      System.out.println(data + " successfully deleted from tree (case2b)"); 

      // case 3: deletion node has two subtrees 
      // *find min value in right subtree 
      // *replace deletion node with min value 
      // *remove the min value from right subtree or else there'll be 
      // a duplicate 
     } else if (root.left != null && root.right != null) { 

      Node temp; 
      if (root.right.right == null && root.right.left == null) 
       temp = findMinNode(root.left); 
      else 
       temp = findMinNode(root.right); 

      System.out.println(root.data + " replaced with " + temp.data); 
      root.data = temp.data; 

      if (root.right.right == null || root.left.left == null) 
       root.left = delete(root.left, root.data); 
      else 
       root.right = delete(root.right, root.data); 

      size--; 
      System.out.println(temp.data + " succesfuly deleted from tree (case3)"); 

     } 
    } 

    return root; 

} 

// find min value in tree 
public Node findMinNode(Node root) { 

    while (root.left != null) 
     root = root.left; 
    System.out.println("min value: " + root.data); 
    return root; 

} 

public void preOrderTraversal(Node root) { 

    if (root == null) 
     return; 

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

} 

public static void main(String[] args) { 

    RandomNode r = new RandomNode(); 

    Node root = new Node(6); 
    //root.left = new Node(2); 
    root.right = new Node(9); 
    //root.left.left = new Node(1); 
    //root.left.right = new Node(5); 
    //root.left.right.left = new Node(4); 
    //root.left.right.left.left = new Node(3); 
    root.right.left = new Node(8); 
    root.right.right = new Node(13); 
    root.right.left.left = new Node(7); 
    root.right.right.left = new Node(11); 
    root.right.right.right = new Node(18); 

    r.delete(root, 6); 
    r.preOrderTraversal(root); 

} 

}

Answer 1

這是相當困難的我跟着，因爲我想它在功能上寫。
然而，

if (root.right.right == null || root.left.left == null) 
    root.left = delete(root.left, root.data); 
else 
    root.right = delete(root.right, root.data); 

也許是錯誤的，因爲它應該反映你剛纔findMinNode()調用，從而可能應該

if(root.right.right == null && root.right.left == null) 
    root.left = delete(root.left, root.data); 

調試時，它還有更多的錯誤。

首先，Java是按值傳遞，所以，如果你刪除頂級節點（根），您的指針也應該被更新。因此，調用應該是root = r.delete(root, 6);

其次，還有另一個錯誤。情況2a將根分配給root.left ...，其爲空。它應該是root.right。

在作出這些改動之後，輸出則變爲：

6 successfully deleted from tree (case2b) 
7 
8 
9 
11 
13 
18 

Answer 2

當你的root = root.left;和大小 - ，您還必須使root.left = null。

在這裏，你只能使root作爲root.left但不做root.left爲空。