java - 为什么这个方法会导致无限递归调用？

Question

我很难理解为什么这个类不起作用。这是数据结构类(class)作业的一部分(编辑:作业的截止日期已经过去，我只是想弄清楚......)。该节点是基于 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)

Answer 1

我建议要么你的树变形了，要么太大了。代码看起来没有问题。

如果您的树变形，导致您在同一棵树中插入了两次Node，那么此代码将会损坏。

添加 - 您消耗的堆栈比您需要的多一点 - 将 p.left.getHeight() 替换为 getHeight(p.left) code> 等将避免每次递归一次堆栈推送。如果您的问题仅仅是大树，那么这可能会让您陷入困境，但这只会推迟问题的解决。