4.3.1 Implementation

Next: 4.3.2 Sketch of Huffman Tree Construction Up: 4.3 An Application of Binary Trees: Huffman Code Construction Previous: 4.3 An Application of Binary Trees: Huffman Code Construction

We use three arrays, tree, alphabet, and forest.

Each element in the array ``tree'' has 3 fields: lchild, rchild, parent, and represents a node of a tree. This array has information about all nodes in all trees in the forest.
The array ``alphabet'' associates with each symbol of the alphabet being encoded, its corresponding leaf.
The array ``forest'' represents the collection of all trees. Initial values of these arrays are shown as follows:
Figure 4.10 shows the above three data structures for our example.

Figure 4.10: Initial state of data structures
$\begin{figure}\centerline{\psfig{figure=figures/Fhuffman3.ps,width=5in}} \end{figure}$

**Figure 4.10:** Initial state of data structures
$\begin{figure}\centerline{\psfig{figure=figures/Fhuffman3.ps,width=5in}} \end{figure}$

**Figure 4.11:** Step 1
$\begin{figure} \centerline{\psfig{figure=figures/Fhuffman4.ps,width=5in}} \end{figure}$

eEL,CSA_Dept,IISc,Bangalore