1 /* ------------------- htree.c -------------------- */
10 /* ------ build a Huffman tree from a frequency array ------ */
11 void DfBuildTree(void)
16 /* ---- preset node pointers to -1 ---- */
17 for (i
= 0; i
< treect
; i
++) {
22 /* ---- build the huffman tree ----- */
25 /* ---- find the two lowest frequencies ---- */
26 for (i
= 0; i
< treect
; i
++) {
28 struct DfHTree
*htt
= ht
+i
;
29 /* --- find a node without a parent --- */
30 if (htt
->cnt
> 0 && htt
->parent
== -1) {
31 /* ---- h1 & h2 -> lowest nodes ---- */
32 if (h1
== -1 || htt
->cnt
< ht
[h1
].cnt
) {
33 if (h2
== -1 || ht
[h1
].cnt
< ht
[h2
].cnt
)
37 else if (h2
== -1 || htt
->cnt
< ht
[h2
].cnt
)
42 /* --- if only h1 -> a node, that's the root --- */
47 /* --- combine two nodes and add one --- */
48 ht
[h1
].parent
= treect
;
49 ht
[h2
].parent
= treect
;
50 ht
= realloc(ht
, (treect
+1) * sizeof(struct DfHTree
));
53 /* --- the new node's frequency is the sum of the two
54 nodes with the lowest frequencies --- */
55 ht
[treect
].cnt
= ht
[h1
].cnt
+ ht
[h2
].cnt
;
56 /* - the new node points to the two that it combines */
57 ht
[treect
].right
= h1
;
59 /* --- the new node has no parent (yet) --- */
60 ht
[treect
].parent
= -1;