0

我有 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
4

1 回答 1

1

root = null;不做你认为它做的事。它仅更改局部变量的值。它不会改变树。简要比喻：

想想一个学生的教室。学生是树中的节点。它们相互指向，这定义了树中的父母身份。现在，如果另一个学生（比如约翰，即函数的参数）出现并指向“树”中的一个学生（比如莎拉），说root = null;将等同于约翰现在没有指向任何地方，它不会改变莎拉，也没有任何其他学生所指的东西。

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

相反，您需要执行类似node.setLeft(null);或node.setRight(null);实际更改树的操作。

这将需要进行相当多的更改，我将留给您弄清楚（这个或这个可能会有所帮助），但请注意，为此您显然必须检查左右孩子而不是（只是） 根。

我还建议您查看红黑树（或类似树），因为它们提供了更有效的删除节点的方法并保持树的平衡。

于 2013-07-17T16:44:54.197 回答