java - BST 节点删除困惑 [Java]

Question

我用 Java 创建了一个二叉搜索树。不幸的是“删除”功能不起作用。如果您能看一下，我将不胜感激。提前致谢..

问题:在删除树中的节点后，我无法按顺序打印树。

节点:

class Node {

//Properties
private Node left, right, parent;
private int key;

//Getters and Setters
public Node(int key) {
    this.key = key;
}

public int getKey() {
    return key;
}

public void setKey(int key) {
    this.key = key;
}

public Node getLeft() {
    return left;
}

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

public Node getRight() {
    return right;
}

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

public Node getParent() {
    return parent;
}

public void setParent(Node parent) {
    this.parent = parent;
}

}

二叉搜索树:

public class BinarySearchTree {

//Properties
private Node root;

//Getters and Setters
Node getRoot() {
    return root;
}

public void setRoot(Node root) {
    this.root = root;
}

//Search Method
public Node search(Node x, int k){
    if (x == null || k==x.getKey()){
        return x;
    }
    if (k<x.getKey()){
        return search(x.getLeft(), k);
    }
    else{
        return search(x.getRight(), k);
    }
}

//Insertion Method
public void insert(Node z) {
    Node y = null;
    Node x = getRoot();
    while (x != null) {
        y = x;
        if (z.getKey() < x.getKey()) {
            x = x.getLeft();
        } else {
            x = x.getRight();
        }
    }
    z.setParent(y);
    if (y == null) {
        setRoot(z);
    } else if (z.getKey() < y.getKey()) {
        y.setLeft(z);
    } else {
        y.setRight(z);
    }

}

//Printer Method
public void inorder(Node x) {

    if (x != null) {
        inorder(x.getLeft());
        System.out.print(x.getKey() + " ");
        inorder(x.getRight());
    }
}

//Transplant Method
public void transplant(Node u, Node v){
    if (u.getParent() == null){
        setRoot(v);
    }
    else if (u==u.getParent().getLeft()){
        u.getParent().setLeft(v);
    }
    else{
        u.getParent().setRight(v);
    }
    if (v!=null){
        v.setParent(u.getParent());
    }
}

//Deletion Method
public void delete(Node x) {
      if (x.getLeft() == null) {
          transplant(x, x.getRight());
      } else if (x.getRight() == null) {
          transplant(x, x.getLeft());
      } else {
          Node y = minimum(x.getRight());
          if (y.getParent() != x) {
              transplant(y, y.getRight());
              y.setRight(x.getRight());
              y.getRight().setParent(y);
          }
          transplant(x, y);
          y.setLeft(x.getLeft());
          y.getLeft().setParent(y);
      }
  }

//Maximum Finder
public Node maximum(Node x) {
    while (x.getRight() != null) {
        x = x.getRight();
    }
    return x;
}

//Minimum Finder
public Node minimum(Node x) {
    while (x.getLeft() != null) {
        x = x.getLeft();
    }
    return x;
}

//Example Tree Constructor
public void createBST(int[] a){

    for (int i=0; i<a.length; i++){
        Node nodeToBeAdded = new Node(a[i]);
        insert(nodeToBeAdded);
    }
    inorder(root);
}

}

和一个测试类:

public class Test {

public static void main(String[] args) {

    //CREATION
    System.out.println("CREATION");
    BinarySearchTree tree = new BinarySearchTree();

    int[] a = {54, 32, 76, 7, 44, 63, 99};

    tree.createBST(a);

    System.out.println();
    System.out.print("The root of the tree is: ");
    System.out.println();

    System.out.print("Maximum Node is: ");
    tree.inorder(tree.maximum(tree.getRoot()));
    System.out.println();

    System.out.print("Minimum Node is: ");
    tree.inorder(tree.minimum(tree.getRoot()));
    System.out.println();


    //INSERTION
    System.out.println("INSERTION");
    tree.insert(new Node(25));
    tree.inorder(tree.getRoot());

    tree.insert(new Node(485));
    System.out.println();
    tree.inorder(tree.getRoot());

    tree.insert(new Node(12));
    System.out.println();
    tree.inorder(tree.getRoot());

    tree.insert(new Node(5));
    System.out.println();
    tree.inorder(tree.getRoot());

    tree.insert(new Node(9985));
    System.out.println();
    tree.inorder(tree.getRoot());

    System.out.println();
    System.out.print("Maximum Node is: ");
    tree.inorder(tree.maximum(tree.getRoot()));
    System.out.println();

    System.out.print("Minimum Node is: ");
    tree.inorder(tree.minimum(tree.getRoot()));
    System.out.println();

    //SEARCH
    System.out.println("SEARCH");
    tree.inorder(tree.search(tree.getRoot(), 32));
    System.out.println();


    //DELETION
    System.out.println("DELETION");
    tree.delete(new Node(5));
    tree.inorder(tree.getRoot());
}

}

Answer 1

正如我所见，您没有重写 equals/hashCode 方法，因此您无法找到 Node(5)，因为您创建了新实例。如果您更改 Test.java 中的代码:

tree.insert(new Node(12));
System.out.println();
tree.inorder(tree.getRoot());
//  Start changes
Node node5 = new Node(5);
tree.insert(node5);
System.out.println();
tree.inorder(tree.getRoot());
//  End changes
tree.insert(new Node(9985));
// -cut some code
//DELETION
System.out.println("DELETION");
tree.delete(node5);
System.out.println();
tree.inorder(tree.getRoot());

它将打印结果