我正在尝试实现二叉搜索树的remove方法,但是当移除的节点同时有两个子节点时,我无法正确地移除和替换节点。我认为问题可能出在我用删除节点替换节点的代码中,或者我的顺序继承代码可能是错误的。我已经分析了很多,但没有运气,所以我需要帮助纠正我的错误。删除节点后尝试打印树时,会弹出错误。
我现在只在删除节点的时候使用顺序继承者,我想知道什么时候我也应该使用顺序继承者。 BinarySearchTree.java:
```
public class BinarySearchTree<V extends Comparable> {
public class Node<V extends Comparable<V>> {
V value;
Node<V> parent, left, right;
public Node(V value, Node<V> parent, Node<V> left, Node<V> right) {
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
}
private Node<V> root = null;
public BinarySearchTree() { this.root = null; }
public int height() { return this.height(this.root); }
private int height(Node<V> at) {
if (at != null) return 1 + Math.max(this.height(at.left), this.height(at.right));
return 0;
}
/*
--------------------------------------------------
------------------------ FIND --------------------
--------------------------------------------------
*/
public Node<V> getNode(V value) { return this.getNode(this.root, value); }
private Node<V> getNode(Node<V> at, V value) {
while (at != null) {
int c = value.compareTo(at.value);
if (c < 0) at = at.left;
else if (c > 0) at = at.right;
else return at;
}
return at;
}
private Node<V> minNode(Node<V> at) {
while (at != null) {
if (at.left == null) break;
at = at.left;
}
return at;
}
private Node<V> maxNode(Node<V> at) {
while (at != null) {
if (at.right == null) break;
at = at.right;
}
return at;
}
private Node<V> getInorderSuccessor(Node<V> at) { return this.minNode(at.right); }
private Node<V> getInorderPredecessor(Node<V> at) { return this.maxNode(at.left); }
/*
--------------------------------------------------
---------------------- INSERT --------------------
--------------------------------------------------
*/
public void insert(V value) { this.insert(this.root, new Node<V>(value,null,null,null)); }
private void insert(Node<V> at, Node<V> i) {
int c;
Node<V> p = null;
while (at != null) {
p = at;
c = i.value.compareTo(at.value);
at = (c < 0) ? at.left : at.right;
}
if (p == null) this.root = i;
else {
c = i.value.compareTo(p.value);
if (c < 0) p.left = i;
else p.right = i;
}
i.parent = p;
}
/*
--------------------------------------------------
---------------------- REMOVE --------------------
--------------------------------------------------
*/
public void remove(V value) {
if (this.height(this.root) <= 1) this.root = null;
else {
Node<V> r = getNode(value);
if (r != null) this.remove(r);
}
}
private void remove(Node<V> r) {
int c = r.value.compareTo(r.parent.value);
if (r.left == null && r.right == null) {
if (c < 0) r.parent.left = null;
else r.parent.right = null;
} else if (r.left != null && r.right == null) {
r.left.parent = r.parent;
if (c < 0) r.parent.left = r.left;
else r.parent.right = r.left;
} else if (r.left == null && r.right != null) {
r.right.parent = r.parent;
if (c < 0) r.parent.left = r.right;
else r.parent.right = r.right;
} else if (r.left != null && r.right != null) {
Node<V> s = this.getInorderSuccessor(r);
if (s.right != null) {
s.parent.left = s.right;
s.right.parent = s.parent;
}
s.parent = r.parent;
c = s.value.compareTo(s.parent.value);
if (c < 0) s.parent.left = s;
else s.parent.right = s;
s.left = r.left;
s.left.parent = s;
s.right = r.right;
s.right.parent = s;
}
r.parent = r.left = r.right = null;
r = null;
this.print();
}
/*
--------------------------------------------------
---------------------- PRINT ---------------------
--------------------------------------------------
*/
public void print() { if (this.root != null) this.print(this.root, 0); }
private void print(Node<V> at, int s) {
if (at == null) return;
s += 5;
this.print(at.right, s);
System.out.print("\n");
for (int i=5; i<s; i++) System.out.print(" ");
System.out.print(at.value + "\n");
this.print(at.left, s);
}
public String nlr() { return this.nlr(this.root); }
private String nlr(Node<V> at) {
if (at != null) {
String result = at.value.toString(),
leftResult = nlr(at.left),
rightResult = nlr(at.right);
if (!leftResult.equals("")) result += " " + leftResult;
if (!rightResult.equals("")) result += " " + rightResult;
return result;
}
return "";
}
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
tree.insert(7);
tree.insert(3);
tree.insert(1);
tree.insert(5);
tree.insert(4);
tree.insert(11);
tree.insert(10);
tree.insert(15);
System.out.println("BST construction:");
System.out.println("Your Pre-order result is: " + tree.nlr());
System.out.println(" The answer should be: 7 3 1 5 4 11 10 15 \n");
System.out.println("\nBST print:");
tree.print();
System.out.println("\nRemove items: ");
tree.remove(11);
System.out.println("Your Pre-order result is: " + tree.nlr());
System.out.println(" The answer should be: 7 3 1 15 \n");
}
}
暂无答案!
目前还没有任何答案,快来回答吧!