删除二进制搜索树中的一个节点

Question

我有一个BST的测试代码。 BST已创建，但节点删除操作不正确。任何帮助建议如果下面的删除代码是正确的或任何删除方法的修改将是非常有用的。

public class BinarySearchTree { 
    public BinarySearchTree() { 
    super(); 
    } 

    private class BinarySearchTreeNode{ 
    private int data; 
    private BinarySearchTreeNode left; 
    private BinarySearchTreeNode right; 

    public BinarySearchTreeNode(){ 
    } 

    public BinarySearchTreeNode(int data){ 
     this.data = data; 
    } 

    public void setData(int data) { 
     this.data = data; 
    } 

    public int getData() { 
     return data; 
    } 

    public void setLeft(BinarySearchTree.BinarySearchTreeNode left) { 
     this.left = left; 
    } 

    public BinarySearchTree.BinarySearchTreeNode getLeft() { 
     return left; 
    } 

    public void setRight(BinarySearchTree.BinarySearchTreeNode right) { 
     this.right = right; 
    } 

    public BinarySearchTree.BinarySearchTreeNode getRight() { 
     return right; 
    } 
    } 

    public BinarySearchTreeNode insertRec(BinarySearchTreeNode root,int data){ 
    if(root == null){ 
     root = new BinarySearchTreeNode(); 
     root.setData(data); 
     root.setLeft(null); 
     root.setRight(null); 
    }else{ 
     if(data < root.getData()) 
      root.setLeft(insertRec(root.getLeft(), data)); 
     else if(data > root.getData()) 
      root.setRight(insertRec(root.getRight(), data)); 
    } 

    return root; 
    } 

    public void insertNonRec(BinarySearchTreeNode root,int data){ 
    if(root == null){ 
     root = new BinarySearchTreeNode(data); 
     root.setLeft(null); 
     root.setRight(null); 
    }else{ 
     if(data < root.getData()){ 
     if(root.getLeft() != null){ 
      insertNonRec(root.getLeft(),data); 
     }else{ 
      root.setLeft(new BinarySearchTreeNode(data)); 
     } 
     }else if(data > root.getData()){ 
     if(root.getRight() != null){ 
      insertNonRec(root.getRight(), data); 
     }else{ 
      root.setRight(new BinarySearchTreeNode(data)); 
     } 
     } 
    } 
    } 

    public void delete(BinarySearchTreeNode root,int data){ 
    BinarySearchTreeNode temp; 
    if(root == null){ 
     System.out.println("No elemets in BST."); 
    }else if(data < root.getData()){ 
     delete(root.getLeft(),data); 
    }else if(data > root.getData()){ 
     delete(root.getRight(),data); 
    }else{ 
     if((root.getLeft() != null) && (root.getRight() != null)){ 
     // Replace with largest in left subtree 
     temp = findMax(root.getLeft()); 
     root.setData(temp.getData()); 
     delete(root.getLeft(),temp.getData()); 
     }else if(root.getLeft() != null || root.getRight() != null){ 
     // One child 
     if(root.getLeft() == null){ 
      //root = root.getRight(); 
      root.setData(root.getRight().getData()); 
      root.setRight(null); 
     }else if(root.getRight() == null){ 
      //root = root.getLeft(); 
      root.setData(root.getLeft().getData()); 
      root.setLeft(null); 
     } 
     }else{ 
     root = null; 
     } 
    } 
    } 

    public BinarySearchTreeNode findMax(BinarySearchTreeNode root){ 
    if(root == null) 
     return null; 

    while(root.getRight() != null) 
     root = root.getLeft(); 

    return root; 
    } 

    public BinarySearchTreeNode findMin(BinarySearchTreeNode root){ 
    if(root == null) 
     return null; 

    while(root.getLeft() != null) 
     root = root.getLeft(); 

    return root; 
    } 

    public void inOrderRec(BinarySearchTreeNode root){ 
    if(root != null){ 
     inOrderRec(root.getLeft()); 
     System.out.print(root.getData() + " "); 
     inOrderRec(root.getRight()); 
    } 
    } 

    public static void main(String args[]){ 
    BinarySearchTree tree = new BinarySearchTree(); 
    BinarySearchTreeNode root = tree.insertRec(null, 10); 

    tree.insertNonRec(root, 5); 
    tree.insertNonRec(root, 20); 
    tree.insertNonRec(root, 4); 
    tree.insertNonRec(root, 8); 
    tree.insertNonRec(root, 12); 
    tree.insertNonRec(root, 30); 
    tree.insertNonRec(root, 11); 
    tree.insertNonRec(root, 13); 

    System.out.println("InOrder Traversal :"); 
    tree.inOrderRec(root); 

    tree.delete(root, 20); 

    System.out.println(""); 
    System.out.println("InOrder Traversal :"); 
    tree.inOrderRec(root); 
    } 
} 

输出：

InOrder Traversal : 
4 5 8 10 11 12 13 20 30 

InOrder Traversal : 
4 5 8 10 11 12 13 11 30 

Answer 1

root = null;没有做什么，你认为它。它仅改变局部变量的值。它不会更改树。简短的比喻：

认为学生的教室。学生是树中的节点。他们彼此指向，这在树上定义了父母的身份。现在，如果一个学生（说约翰，即函数的参数）均在其中一名学生在“树”一起和点来（比如萨拉），说root = null;将相当于现在John指向无处，也不会改变莎拉，也没有其他学生指着什么。

当然，在我的比喻中有一些漏洞，但我希望你能得到基本的想法。

你，而不是需要做一些像node.setLeft(null);或node.setRight(null);真正改变的树。

这将需要不少的改变，我会留给你弄清楚（this或this可能有一些帮助），但请注意，为此，您显然必须检查左侧和右侧的儿童而不是（仅）根。

我也建议你看一看Red-black trees（或类似），因为它们提供删除节点的更有效的手段，也保留了树的平衡。