Problem with creating a Huffman code tree

[DSMan195276]

I haven't closely read all of your code, but it looks like you have the right idea for creating the table of character frequencies. For creating the actual Huffman tree you can just make an array of nodes, and in place of where you'd normally use pointers you just store an index into the array of nodes. Once you do that it's reasonably easy to use the typical algorithm to make the huffman tree. So it would work something like this (I didn't test this):

Code: (Select All)

' I think this is all you need

Type HuffmanNode

  Char As _Unsigned _Byte

  Count As _Unsigned Long

  Left As Long ' 0-bit path

  Right As Long ' 1-bit path

End Type



ReDim tree(20) As HuffmanNode ' I just picked a random size, in practice you'll resize this as you create more nodes



tree(2).Char = ASC("A") ' Leaf node

tree(2).Count = 10

tree(2).Left = -1 ' -1 for the indexes indicates a leaf node

tree(2).Right = -1



tree(3).Char = ASC("B")

tree(3).Count = 15

tree(3).Left = -1

tree(3).Right = -1



' This is an internal node created when creating the huffman tree

tree(1).Char = 0 ' doesn't actually have a char

tree(1).Count = 25 ' Addition of the counts of left/right

tree(1).Left = 2 ' The "A" leaf node

tree(1).Right = 3 ' The "B" leaf node



' When traversing the tree, you index the array with the .Left and .Right values

Print "0-bit path of internal node 1: "; tree(tree(1).Left)

Print "1-bit path of internal node 1: "; tree(tree(1).Right)

When creating the huffman tree you'll initialize that

tree()

array with leaf nodes created from your existing

Table()

array (and really, you could probably combine them into one array with a little work).

One catch is that you can't sort that array to find the next two nodes to handle, because sorting will change the position of the nodes in the array and make all your

.Left

and

.Right

entries wrong. To fix that you can just use another array of indexes and sort that (which is what you'd typically do in C anyway), like this:

Code: (Select All)

ReDim HuffmanQueue(256) As Long



' Assuming the starting leafnodes are entries 1 to 256 in tree()

For i = 1 To 256

  HuffmanQueue(i) = i

Next



' When sorting you do this kind of thing

If tree(HuffmanQueue(x)).Count > tree(HuffmanQueue(y)).Count Then

  ' Swapping two entries in the queue

  z = HuffmanQueue(y)

  HuffmanQueue(y) = HuffmanQueue(x)

  HuffmanQueue(x) = z

End If



' Create a new tree() node and assign it into HuffmanQueue()



tree(nextNode).Left = HuffmanQueue(1)

tree(nextNode).Right = HuffmanQueue(2)

tree(nextNode).Count = tree(HuffmanQueue(1)).Count + tree(HuffmanQueue(2)).Count



HuffmanQueue(1) = nextNode

HuffmanQueue(2) = -1

nextNode = nextNode + 1



' The above requires your sort to ignore the -1 entries.

' You could also just shift all the entries in the HuffmanQueue() array up one so that the HuffmanQueue(2) entry is gone and the array is one less in size.

To actually build the huffman tree you will sort the

HuffmanQueue()

array, then take the first two entries and build a new

HuffmanNode

that has those two entries as its

.Left

and

.Right

. Then you replace one of the

HuffmanQueue()

entries with your newly created node, remove the other one (Maybe set it to

-1

, or shift everything over and reduce the size of the array), and then sort and remove again until only one node is left in

HuffmanQueue()

(either due to reduced size, or all of them are

-1

).