Как сохранить дерево Хаффмана в файле?

Question

Я работаю над кодировкой Хаффмана на Java. Я не понимаю, как и где хранить дерево. Я знаю, как сделать дерево, а затем сохранить его как двоичный файл, но для цели декодирования нам снова понадобится то же дерево для декодирования. Как сохранить это дерево в файле, чтобы связать его с двоичным файлом?

Answer 1

Напишите дерево как последовательность бит: 0 представляет лист, 1 представляет собой внутренний узел. Выход для двоичного дерева (Huffman или иначе) с N листовыми узлами и внутренними узлами N-1 будет представлять собой последовательность из 2N-1 бит. (Фактически вы можете сохранить два бита, поскольку вы знаете, что первый и последний узлы в дереве будут листовыми узлами, но, вероятно, не стоит усложнять алгоритм для сохранения двух бит.)

Возможно, проще всего расположить биты в предварительном порядке:

function write_tree (top_node) { 
    if is_leaf(top_node) { 
     write "0" 
     // optionally, write any date associated with the leaf node 
     // although in practice it's easier to write the leaf data 
     // to a separate output stream. That lets this stream contain 
     // actual bits rather than the characters "0"/"1" 
     } 
    else { 
     write "1" 
     write_tree (top_node.left) 
     write_tree (top_node.right) }} 

function read_tree (bit_stream) -> returns tree 
    next_bit = bit_stream.read() 
    if next_bit = "0" { 
     root = new leaf 
     // optionally read data associated with the leaf node 
     } 
    else { 
     root = new internal node 
     root.left = read_tree (bit_stream) 
     root.right = read_tree (bit_stream) } 
    return root } 

я не заметил сначала, что вы упомянули Java, так что я написал выше, в псевдо-коде, который я уверен, что у вас не будет никаких проблем переписывания в Java ,