Как исправить переполнение стека из рекурсивного метода getHeight - PullRequest
Новая
       23

Как исправить переполнение стека из рекурсивного метода getHeight

0 голосов
/ 29 апреля 2019

Когда я запускаю свой код для метода, вычисляющего высоту дерева двоичного поиска, это приводит к ошибке переполнения стека, но только для деревьев с более чем одним узлом (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);
    }

Ответы [ 2 ]

2 голосов
/ 29 апреля 2019

Похоже, что ничего существенного не так 1 с кодом, который вы нам показали.

Если этот код дает StackOverflowException для небольшого дерева, то , наиболее вероятно, означает, что ваше дерево было создано неправильно и в нем есть цикл (цикл). Если ваш рекурсивный алгоритм встречает цикл в «дереве», он будет зацикливаться, пока стек не переполнится 2 .

Чтобы быть уверенным в этом диагнозе, нам нужно увидеть MVCE, который включает в себя весь код, необходимый для построения дерева примеров, демонстрирующего их поведение.

1 - Возможно, в вычислении высоты есть ошибка «off by one», но это не приведет к переполнению стека.

2 - Текущие реализации Java не выполняют оптимизацию хвостового вызова.

0 голосов
/ 29 апреля 2019

Пожалуйста, сначала проверьте, правильно ли создано ваше дерево.

Иначе, скорее всего, это из-за вашей переменной height .Когда ваша программа выполняет рекурсивный вызов, она всегда инициализируется как 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;
        }
    }
}

Надеюсь, это поможет!

...