Построение двоичного дерева из обхода порядка: ошибка переполнения стека

Question

У меня есть дерево, где листья отмечены символом L, а нелистовые узлы отмечены значком I. Мне дается обход предлога по дереву. Примером может служить IIILLILILLIIILLLIILILLL. Я должен построить дерево huffman для этой включенной строки. Я изначально перешел в новый Root(), 0 и мой treeString для моих аргументов. TreeString будет строкой с надписью I и L, вставленной выше. По какой-то причине мой код вызывает исключение StackOverflow. Мой код выглядит следующим образом для метода makeTree:

public static void makeTree (BinaryNodeInterface<Character> root, int start, String treeString) 
{ 
    if (treeString.charAt(start)=='L'){ 

     root.setLeftChild(null); 
     root.setRightChild(null); 
     return; 
    } 
    BinaryNodeInterface<Character> leftSide = new BinaryNode<Character>(); 
    root.setLeftChild(leftSide); 
    makeTree(root.getLeftChild(), start++, treeString); 
    BinaryNodeInterface<Character> rightSide = new BinaryNode<Character>(); 
    root.setRightChild(rightSide); 
    makeTree(root.getRightChild(), start++, treeString); 
} 

Я понятия не имею, что является причиной StackOverflow исключения быть выброшен. Я бы подумал, что мой базовый случай в начале вернется и обработает его.

Answer 1

Я считаю, что это проблема:

makeTree(root.getLeftChild(), start++, treeString); 

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

Причина бесконечной рекурсии состоит в том, что start++ является оператором после инкремента, а это означает, что он дает текущее значение start, а затем увеличивает его. Таким образом, каждый раз, когда makeTree вызывает себя, он вызывает себя с той же версией start и, таким образом, смотрит на то же I во входной строке.

Однако замена его на ++start не заставит себя работать. (Это может привести к переполнению стека, но это не сработает правильно.) Причина в том, что когда вы вызываете makeTree, вы хотите дать ему начальное местоположение строки, в которой вы хотите, чтобы рекурсивный вызов начал искать - но вам также нужен рекурсивный вызов, чтобы рассказать ему, сколько из потребляемой им строки. Это необходимо, потому что после того, как makeTree называет себя рекурсивно на getLeftChild, вы назовете его снова на getRightChild, и вам нужно позвонить ему с правильной отправной точкой.

Обратите внимание, что каждый рекурсивный вызов имеет свою собственную копию start. Таким образом, когда makeTree называет себя, а второй makeTree увеличивает start, это не влияет на start, что видно из первого makeTree.

Вам понадобится каждый рекурсивный makeTree, чтобы сообщить своему абоненту, сколько его потребляемой струны. Вероятно, самый простой способ сделать это - изменить тип возврата на int; вы можете решить, хотите ли вы, чтобы результатом функции было количество потребляемых символов, или индекс, где он прекратил сканирование, или что-то подобное. Затем, после рекурсивного вызова makeTree, используйте результат функции для настройки параметра start. Удостоверьтесь, что makeTree возвращает правильный результат, как в листовой, так и в нелистовой форме. Будьте осторожны, чтобы избежать ошибок при каждом запуске.

Answer 2

Вы не можете создать дерево только из списка preOrder. По крайней мере, вам нужно обходить порядок, а также, если это полное дерево, вы также можете использовать posrorder.