Путешествие по дереву Хаффмана

Итак, в настоящее время у меня есть программа, которая создает дерево Хаффмана. дерево состоит из «узлов» с этими полями: справа (указывает на правый дочерний элемент) левый (указывает на левый дочерний элемент) код (строка целых чисел, в идеале нули и единицы, которые будут кодом Хаффмана этого узла) символ ( символ, содержащийся в узле).

Я создал дерево Хаффмана, добавив узлы из связанного списка - я знаю, что дерево было создано правильно. Когда я создавал дерево, я сказал узлу, когда я дал ему родительский узел, что если он был родительским «правым», его кодовая строка была 1, если оставалась 0. Однако очевидно, что после создания всего дерева каждый узел становится будет только либо 0, либо 1, но еще не строка, такая как 00100101. Мой вопрос: теперь, когда у меня есть это дерево, могу ли я пройти по нему? Я понимаю, что идея заключалась бы в том, чтобы дать каждому дочернему элементу его родительский код + собственный код дочернего элемента, но я не понимаю, как выполнить цикл по дереву для достижения этой цели.

Заранее спасибо.


java huffman-code
person user990710    schedule 12.10.2011    source источник
comment
Было бы полезно привести пример вашего кода и то, как вы пытались решить эту проблему.   -  person Brendan Long    schedule 12.10.2011
comment
Опубликуйте свой код, также, если это домашнее задание, его нужно пометить соответствующим образом :).   -  person Jack    schedule 12.10.2011

Ответы (1)


arrow_upward
0
arrow_downward

Может быть, это?

  ExpandBinaryPaths(node, prefix)
  1. if node is null then return 
  2. else then
  3.    node.binary = prefix concat node.binary
  4.    ExpandBinaryPaths(node.left, node.binary)
  5.    ExpandBinaryPaths(node.right, node.binary)
  6.    return

Идея состоит в том, что вы должны вызвать это в корне без префикса ... ExpandBinaryPaths (root, "").

person Patrick87    schedule 12.10.2011