刪除二進制搜索樹中的一個節點

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（或類似），因爲它們提供刪除節點的更有效的手段，也保留了樹的平衡。