Consider a rooted binary tree, where each internal (intermediate) node has 2 chi
ID: 3582500 • Letter: C
Question
Consider a rooted binary tree, where each internal (intermediate) node has 2 children. Assume each node, in particular, the leaves, has a symbol or variable associated with it. For the edges from each node to its children, associate a value 1 to one edge, and a value 0 to the other edge. A special case of such trees is the Huffman tree, or Huffman coding tree. Another special case is binary decision trees. One goal is to determine the code or sequence of 0’s and 1’s that result when one traverses a path from the root to each leaf of the tree. Devise an algorithm, pseudo-code or source code to implement the generation of such root-toleaf codes, using each of the following approaches. (Hint: in case of difficulty handling the general case for arbitrary binary trees, try to first devise solutions for concrete examples of the weighted binary trees of depths 1, 2, 3, 4, 5, 6, 7, 8, and then try to tackle the general case). (Hint: use concepts and tools of procedures, functions and recursion to achieve modularity)
d. Attribute grammar based evaluation
Explanation / Answer
Code:
// Include libraries
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
//Define constant
#define lMAX_TREE_HT 100
//Define structure
struct MinHeapNode
{
//Define variables
char ldata;
unsigned lfreq;
struct MinHeapNode *lLeft, *lright;
};
//Define structure
struct MinHeap
{
//Define variables
unsigned lsize;
unsigned lcapacity;
struct MinHeapNode **larray;
};
//Define lnewNode()
struct MinHeapNode* lnewNode(char ldata, unsigned lfreq)
{
//Define ltemp
struct MinHeapNode* ltemp =
(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
ltemp->lLeft = ltemp->lright = NULL;
ltemp->ldata = ldata;
ltemp->lfreq = lfreq;
//Return ltemp
return ltemp;
}
// Define lcreateMinHeap()
struct MinHeap* lcreateMinHeap(unsigned lcapacity)
{
//Define lminHeap
struct MinHeap* lminHeap =
(struct MinHeap*) malloc(sizeof(struct MinHeap));
//Set variables
lminHeap->lsize = 0;
lminHeap->lcapacity = lcapacity;
lminHeap->larray =
(struct MinHeapNode**)malloc(lminHeap->lcapacity * sizeof(struct MinHeapNode*));
//Return lminHeap
return lminHeap;
}
//Define lswapMinHeapNode()
void lswapMinHeapNode(struct MinHeapNode** la, struct MinHeapNode** lb)
{
//Set values
struct MinHeapNode* t = *la;
*la = *lb;
*lb = t;
}
//Define lminHeapify()
void lminHeapify(struct MinHeap* lminHeap, int lIdx)
{
int lsmallest = lIdx;
int lLeft = 2 * lIdx + 1;
int lright = 2 * lIdx + 2;
if (lLeft < lminHeap->lsize &&
lminHeap->larray[lLeft]->lfreq < lminHeap->larray[lsmallest]->lfreq)
lsmallest = lLeft;
if (lright < lminHeap->lsize &&
lminHeap->larray[lright]->lfreq < lminHeap->larray[lsmallest]->lfreq)
lsmallest = lright;
if (lsmallest != lIdx)
{
lswapMinHeapNode(&lminHeap->larray[lsmallest], &lminHeap->larray[lIdx]);
lminHeapify(lminHeap, lsmallest);
}
}
//Define lIsSizeOne()
int lIsSizeOne(struct MinHeap* lminHeap)
{
return (lminHeap->lsize == 1);
}
//Define lextractMin()
struct MinHeapNode* lextractMin(struct MinHeap* lminHeap)
{
struct MinHeapNode* ltemp = lminHeap->larray[0];
lminHeap->larray[0] = lminHeap->larray[lminHeap->lsize - 1];
--lminHeap->lsize;
lminHeapify(lminHeap, 0);
return ltemp;
}
//Define linsertMinHeap()
void linsertMinHeap(struct MinHeap* lminHeap, struct MinHeapNode* lminHeapNode)
{
++lminHeap->lsize;
int li = lminHeap->lsize - 1;
while (li && lminHeapNode->lfreq < lminHeap->larray[(li - 1)/2]->lfreq)
{
lminHeap->larray[li] = lminHeap->larray[(li - 1)/2];
li = (li - 1)/2;
}
lminHeap->larray[li] = lminHeapNode;
}
//Define lbuildMinHeap()
void lbuildMinHeap(struct MinHeap* lminHeap)
{
int n = lminHeap->lsize - 1;
int li;
for (li = (n - 1) / 2; li >= 0; --li)
lminHeapify(lminHeap, li);
}
//Define lprintArr()
void lprintArr(int larr[], int n)
{
int li;
for (li = 0; li < n; ++li)
printf("%d", larr[li]);
printf(" ");
}
//Define isLeaf()
int isLeaf(struct MinHeapNode* lroot)
{
return !(lroot->lLeft) && !(lroot->lright) ;
}
//Define lcreateAndBuildMinHeap()
struct MinHeap* lcreateAndBuildMinHeap(char ldata[], int lfreq[], int lsize)
{
struct MinHeap* lminHeap = lcreateMinHeap(lsize);
for (int li = 0; li < lsize; ++li)
lminHeap->larray[li] = lnewNode(ldata[li], lfreq[li]);
lminHeap->lsize = lsize;
lbuildMinHeap(lminHeap);
return lminHeap;
}
//Define lbuildHuffmanTree()
struct MinHeapNode* lbuildHuffmanTree(char ldata[], int lfreq[], int lsize)
{
struct MinHeapNode *lLeft, *lright, *ltop;
//Create min heap
struct MinHeap* lminHeap = lcreateAndBuildMinHeap(ldata, lfreq, lsize);
// Iterate while lsize of heap doesn't become 1
while (!lIsSizeOne(lminHeap))
{
// Extract 2 items from min heap
lLeft = lextractMin(lminHeap);
lright = lextractMin(lminHeap);
//Create new internal node
ltop = lnewNode('$', lLeft->lfreq + lright->lfreq);
ltop->lLeft = lLeft;
ltop->lright = lright;
linsertMinHeap(lminHeap, ltop);
}
//Return minimum
return lextractMin(lminHeap);
}
//Define lprintCodes()
void lprintCodes(struct MinHeapNode* lroot, int larr[], int ltop)
{
// Assign 0 to lLeft edge & recur
if (lroot->lLeft)
{
larr[ltop] = 0;
lprintCodes(lroot->lLeft, larr, ltop + 1);
}
// Assign 1 to lright edge & recur
if (lroot->lright)
{
larr[ltop] = 1;
lprintCodes(lroot->lright, larr, ltop + 1);
}
//If node is leaf
if (isLeaf(lroot))
{
printf("%c: ", lroot->ldata);
lprintArr(larr, ltop);
}
}
//Define lHuffmanCodes()
void lHuffmanCodes(char ldata[], int lfreq[], int lsize)
{
// Construct Huffman Tree
struct MinHeapNode* lroot = lbuildHuffmanTree(ldata, lfreq, lsize);
//Declare variables
int larr[lMAX_TREE_HT], ltop = 0;
//Call lprintCodes()
lprintCodes(lroot, larr, ltop);
}
//Define main function
int main()
{
//Define larray
char larr[] = {'la', 'lb', 'c', 'd', 'e', 'f'};
int lfreq[] = {5, 9, 12, 13, 16, 45};
//Define lsize
int lsize = sizeof(larr)/sizeof(larr[0]);
//Call lHuffmanCodes()
lHuffmanCodes(larr, lfreq, lsize);
//Pause console window
system("pause");
//Return 0
return 0;
}
Sample Output:
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
Press any key to continue . . .