的二叉搜索树删除树节点不起作用

Question

我有我的treeNode的设定这样的Java实现：

public class BTreeNode { 
    private int data; 
    private BTreeNode left; 
    private BTreeNode right; 

    public BTreeNode(){} 
    public BTreeNode(int dataValue){ 
    this(dataValue, null, null); 
    } 
    public BTreeNode(int dataValue, BTreeNode leftValue, BTreeNode rightValue){ 
    data = dataValue; 
    left = leftValue; 
    right = rightValue; 
    } 
    public void setData(int dataValue){ 
    data = dataValue; 
    } 
    public int getData(){ 
    return data; 
    } 
    public void setLeft(BTreeNode leftValue){ 
    left = leftValue; 
    } 
    public BTreeNode getLeft(){ 
    return left; 
    } 
    public void setRight(BTreeNode rightValue){ 
    right = rightValue; 
    } 
    public BTreeNode getRight(){ 
    return right; 
    } 
    public String toString(){ 
    return Integer.toString(getData()); 
    } 
} 

和我的二叉搜索树代码：

public class BinarySearchTree { 

private BTreeNode root; 

public BinarySearchTree(){} 

public void add(int n){ 
    if (root == null) { 
     root = new BTreeNode(n); 
     return; 
    }else{ 
     BTreeNode current = root; 
     while(current != null){ 
      if(n <= current.getData()){ 
       if (current.getLeft() == null) { 
        current.setLeft(new BTreeNode(n)); 
        return; 
       } 
       current = current.getLeft(); 
      }else{ 
       if (current.getRight() == null) { 
        current.setRight(new BTreeNode(n)); 
        return; 
       } 
       current = current.getRight(); 
      } 
     } 
    } 
} 

public void remove(int n){ 
    remove(root, n); 
} 

private BTreeNode remove(BTreeNode root, int n){ 
    if(root == null) return root; 
    int value = root.getData(); 
    BTreeNode left = root.getLeft(); 
    BTreeNode right = root.getRight(); 
    if(n > value) root.setRight(remove(right, n)); 
    else if(n < value) root.setLeft(remove(left, n)); 
    else { 
     //case 1: no children at all 
     if (left == null && right == null) { 
      return null; 
     } 
     //case 2: one child 
     else if (left == null && right != null) { 
      return right; 


     } else if (right == null && left != null) { 
      return left; 
     } 
     //case 3: two child 
     else { 
      int min = findRightMin(right); 
      root.setData(min); 
      remove(right, min); 
      return root; 
     } 
    } 
    return root; 
} 



private int findRightMin(BTreeNode root){ 
    if (root.getLeft() == null) return root.getData(); 
    else return findRightMin(root.getLeft()); 
} 


public int getHeight(){ 
    return getHeight(root); 
} 

private int getHeight(BTreeNode root){ 
    if(root == null) return 0; 
    return 1 + Math.max(getHeight(root.getLeft()), getHeight(root.getRight())); 
} 

public String toString(){ 
    return "{" + toString(root) + "}"; 
} 

private String toString(BTreeNode root){ 

    if(root == null){ 
     return ""; 
    }else{ 

     String left = toString(root.getLeft()); 
     String rootNode = Integer.toString(root.getData()) + ", "; 
     String right = toString(root.getRight()); 

     return left + rootNode + right; 
    } 

} 

public static void main(String[] args){ 

    BinarySearchTree tree = new BinarySearchTree(); 
    tree.add(10); 
    tree.add(8); 
    tree.add(9); 
    tree.add(12); 
    tree.add(15); 
    tree.add(1); 
    tree.add(5); 
    tree.add(7); 
    tree.add(6); 

    System.out.println(tree.toString()); 
    System.out.println(tree.getHeight()); 
    tree.remove(8); 
    System.out.println(tree.toString()); 
} 

} 

当我运行这段代码，控制台输出是

{1, 5, 6, 7, 8, 9, 10, 12, 15, } 
6 
{1, 5, 6, 7, 9, 9, 10, 12, 15, } 

该代码找到了我想要删除和替换的节点的右侧子节点的最小值编辑它，但没有删除该节点。我找不到哪个部分是错的。请帮忙！

Answer 1

你忘记设置right为root的情况下3：

 // case 3: two child 
      else { 
       int min = findRightMin(right); 
       root.setData(min); 
       root.setRight(remove(right, min)); //this one 
       return root; 
      } 
     } 

输出：

{1, 5, 6, 7, 8, 9, 10, 12, 15, } 
6 
{1, 5, 6, 7, 9, 10, 12, 15, } 

请再次测试。我没有测试其他情况。

Answer 2

你错过了root.setRight

//case 3: two child 
else { 
    int min = findRightMin(right); 
    root.setData(min); 
    root.setRight(remove(right, min)); 
    return root; 
}