java - 删除二叉搜索树中的节点

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; 并没有像你想象的那样做。它仅更改局部变量的值。它不会改变树。简单比喻:

Think of a classroom of students. The students are the nodes in the tree. They point at each other, which defines parenthood in the tree. Now if another student (say John, i.e. the parameter of the function) were to come along and point at one of the students in the 'tree' (say Sarah), saying root = null; would be equivalent to John now pointing nowhere, it would not change Sarah nor what any other students is pointing at.

当然，我的比喻有一些漏洞，但我希望你能明白基本的想法。

您需要执行诸如 node.setLeft(null); 或 node.setRight(null); 之类的操作来实际更改树。

这将需要相当多的更改，我将留给您来解决( this 或 this 可能会有所帮助)，但请注意，为此您显然必须检查左侧和右子节点而不是(仅)根。

我还建议您看看Red-black trees (或类似)，因为它们提供了更有效的删除节点的方法并保持树平衡。