ノードをBSTから削除する

Question

ケース2（削除ノードにはサブツリーが1つしかない）以外のほとんどのケースが機能すると思います。私のテストケースは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

私はそれを機能的に書いているので、私が従うのはむしろ難しいです。それをデバッグするとき
はしかし、それはあなたの以前のfindMinNode()通話を反映する必要があり、したがって、おそらく

if(root.right.right == null && root.right.left == null) 
    root.left = delete(root.left, root.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); 

は、おそらく間違っているより多くの間違っあります。

まず、javaは値渡しであるため、トップノード（ルート）を削除する場合は、ポインタも更新する必要があります。したがって、コールはroot = r.delete(root, 6);

でなければなりません。もう1つのバグがあります。ケース2aはroot.left ...にrootを割り当てます。これはnullです。それはroot.rightでなければなりません。

これらの変更を行った、出力は次のようになります。あなたの答えのための

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

Answer 2

ルート= root.leftを行います。とsize - の場合は、root.left = nullにする必要があります。

ここでは、単にroot.leftとしてrootを作っていますが、root.leftをnullにしていません。