我很难理解为什么这个类不起作用。这是数据结构课程作业的一部分(编辑:作业的截止日期已经过去,我只是想弄清楚......)。该节点是基于 BST 构建的 AVL 树的一部分,我选择实现它的方式是在我的 Node 类中创建方法来查找平衡因子和高度。
该类的结构如下:
public class Node<T extends Comparable<? super T>> {
public T data;
public Node left;
public Node right;
public Node(T IN) {
data = IN;
}
public Node(T IN, Node L, Node R) {
this(IN);
left = L;
right = R;
}
@Override
public String toString() {
return data.toString();
}
@Override
public Node clone() {
return new Node(this.data) ;
}
public int getHeight() {
return getHeight(this) ;
}
public int getBF() {
//Calculate BF
int balanceFactor = 0;
if (right != null && left != null)
balanceFactor = getHeight(right) - getHeight(left);
else if (left != null) {
balanceFactor = 0 - getHeight(left) ;
}
else if (right != null) {
balanceFactor = getHeight(right) ;
}
else
balanceFactor = 0 ;
return balanceFactor ;
}
private int getHeight(Node p) {
if (p.left == null && p.right == null ) {
return 0 ;
}
else if (p.left != null && p.right != null) {
return 1 + max(p.left.getHeight(), p.right.getHeight());
}
else if (p.left != null) {
return 1 + p.left.getHeight() ;
}
else if (p.right != null) {
return 1 + p.right.getHeight() ;
}
else {
return 0;
}
}
private int max(int x, int y) {
if (x >= y) {
return x;
} else {
return y;
}
}
}
调用该方法的函数是:
@Override
public boolean insert(T el) {
boolean test = super.insert(el) ;
if (test) {
return checkBalance(root) ;
}
else
return false ;
}
我收到的例外是重复:
Exception in thread "main" java.lang.StackOverflowError
at Node.getHeight(Node.java:54)
at Node.getHeight(Node.java:33)
at Node.getHeight(Node.java:58)