Рекурсивный обход дерева, возвращающий переменную для каждого листа дерева

Question

У меня есть двоичное дерево huffman. Мне нужно пройти по дереву, пока не дойду до каждого листа, и для каждого листа мне нужно «сохранить» элемент этого листового узла и сохранить все эти переменные в массиве вне дерева.

Скажем, у меня есть это дерево:

  3\65 

     6\-1 

      3\70 

    9\-1 

      2\66 

     3\-1 

      1\67 
16\-1 

    7\68 

Каждый лист (7/68, 1/67, 2/66, 7/70, 3/65) имеет элемент под названием "кодирование", который это строка.

(т.е. каждый узел имеет node-> влево, node-> правый и node-> кодирование)

Скажем, кодироаки следующим образом:

7/68 got an encoding of 0 
1/67 got an encoding of 100 
2/66 got an encoding of 101 
3/70 got an encoding of 110 
3/65 got an encoding of 111 

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

Я не могу придумать, как сохранить их за пределами дерева.

Answer 1

«Сохраните эти строки в массиве за пределами дерева».

Комментарий: Вы уверены, что вам нужно хранить строки? Это намного чище, если вы просто сохраняете целые числа и создаете строки после завершения рекурсии.

ОК, так или иначе (и не давая исходников, далеко) вы просто:

• создать достаточно большой (*) массив, прежде чем начать рекурсии

• создать указатель, который будет используемый для записи в разные части массива, инициализирует этот указатель на начало массива.

Дайте указателю на этот указатель в свою рекурсию как новый/дополнительный аргумент функции. Каждый раз, когда лист достигается в рекурсии вас

• записи в указатель, что вы нашли на листе
• увеличивает указатель (вы можете сделать это, потому что у вас есть указатель на указатель

Answer 2

Насколько я помню, в реализации кода хаффмана вам не нужно использовать внешний массив. Самый простой способ реализовать его - добавить к вашей структуре еще один указатель ('next'). Каждый элемент связан дважды. Один раз в качестве члена дерева и один раз в качестве члена связанного списка. Таким образом, новая структура не требуется.