如何修复递归getHeight方法的Stack Overflow

Question

当我为计算二叉搜索树的高度的方法运行我的代码时，它会导致堆栈溢出错误，但仅适用于具有多个节点的树（我的程序中的BSTElements）。我已经读过这是由于错误的递归调用，但无法识别我的代码中的问题。

public int getHeight() {

    return getHeight(this.getRoot());
}

private int getHeight(BSTElement<String,MorseCharacter> element) {

    int height=0;

    if (element == null) {
        return -1;
    }

    int leftHeight = getHeight(element.getLeft());
    int rightHeight = getHeight(element.getRight());

    if (leftHeight > rightHeight) {
        height = leftHeight;
    } else {
        height = rightHeight;
    }

    return height +1;
}

这是完整的代码：

public class MorseCodeTree {

private static BSTElement<String, MorseCharacter> rootElement;



public BSTElement<String, MorseCharacter> getRoot() {
    return rootElement;
}

public static void setRoot(BSTElement<String, MorseCharacter> newRoot) {
    rootElement = newRoot;
}



public MorseCodeTree(BSTElement<String,MorseCharacter> element) {
    rootElement = element;
}

public MorseCodeTree() {
    rootElement = new BSTElement("Root",  "", new MorseCharacter('\0', null));
}
    public int getHeight() {

    return getHeight(this.getRoot());
}

private int getHeight(BSTElement<String,MorseCharacter> element) {

    if (element == null) {
        return -1;
    } else {
        int leftHeight = getHeight(element.getLeft());
        int rightHeight = getHeight(element.getRight());


    if (leftHeight < rightHeight) {
        return rightHeight + 1;
    } else {
        return leftHeight + 1;
    }
    }
}
public static boolean isEmpty() {
        return (rootElement == null);   
}

public void clear() {
    rootElement = null;
}

public static void add(BSTElement<String,MorseCharacter> newElement) {

        BSTElement<String, MorseCharacter> target = rootElement;
        String path = "";
        String code = newElement.getKey();

        for (int i=0; i<code.length(); i++) {
            if (code.charAt(i)== '.') {
                if (target.getLeft()!=null) {
                    target=target.getLeft();
                } else {
                    target.setLeft(newElement);
                    target=target.getLeft();
                }

            } else {
                if (target.getRight()!=null) {
                    target=target.getRight();
                } else {
                    target.setRight(newElement);
                    target=target.getRight();
                }   
            }
        }
        MorseCharacter newMorseChar = newElement.getValue();

        newElement.setLabel(Character.toString(newMorseChar.getLetter()));
        newElement.setKey(Character.toString(newMorseChar.getLetter()));
        newElement.setValue(newMorseChar);

}

    public static void main(String[] args) {
    MorseCodeTree tree = new MorseCodeTree();
        BufferedReader reader;

    try {
        reader = new BufferedReader(new FileReader(file));
        String line = reader.readLine();


        while (line != null) {

            String[] output = line.split(" ");
            String letter = output[0];
            MorseCharacter morseCharacter = new MorseCharacter(letter.charAt(0), output[1]);

            BSTElement<String, MorseCharacter> bstElement = new BSTElement(letter, output[1], morseCharacter);

            tree.add(bstElement);

            line = reader.readLine();

            System.out.println(tree.getHeight());
        }
        reader.close();




    } catch (IOException e) {
    System.out.println("Exception" + e);
    }

Answer 1

您向我们展示的代码似乎没有任何明显的错误1。

如果此代码为小树提供StackOverflowException，则很可能意味着您的树已被错误地创建并且其中有一个循环（循环）。如果递归算法遇到“树”中的循环，它将循环直到堆栈溢出2。

为了确保这种诊断，我们需要看到一个MVCE，其中包含构建展示该行为的示例树所需的所有代码。

---

1 - 高度计算中可能存在“off by one”错误，但这不会导致堆栈溢出。

2 - 当前的Java实现不进行尾调用优化。

Answer 2

请首先检查您的树是否创建错误。

否则，很可能是因为你的身高变量。当您的程序执行递归调用时，它始终启动为0，从而导致无法输出。

如果您创建了自己的节点类，就像这样：

/* Class containing left and right child of current
node and key value*/

class Node {
    int element;
    Node left, right;

    Node(int item) {
        element = item;
        left = right = null;
    }

    Node(int item, Node left, Node right) {
        element = item;
        this.left = left;
        this.right = right;
    }
}

然后，你的getHeight类应该是这样的：

int nodesHeightFinder(Node n) {

    if(n == null) return -1; /*As, if a tree has no nodes, it should not have any height.*/
    else {

        int heightOfLeftSubtree = nodesHeightFinder(n.left);
        int heightOfRightSubtree = nodesHeightFinder(n.right);

        if(heightOfLeftSubtree < heightOfRightSubtree) {
            return heightOfRightSubtree + 1;
        } else {
            return heightOfLeftSubtree + 1;
        }
    }
}

希望能帮助到你！