Encoding Tree Output

Writing out the encoding tree is fairly straightforward. First, we can ignore the weight information, since it is only used in the initial construction of the tree from the frequency data. Also, we can take advantage of the fact that every node in the tree is either a leaf or has exactly two children.

The algorithm to write out the tree is recursive:

1.

If the root node of the tree is itself a leaf:

(a)

Write out the byte value stored in the leaf, preceded by the character ``.'' (period).

(b)

Return.

2.

Otherwise:

(a)

Recursively write out the left subtree, surrounded by parentheses.

(b)

Recursively write out the right subtree, surrounded by parentheses.