HELP Huffman Tree Traversal 
Author Message
 HELP Huffman Tree Traversal

below is a program that builds a Huffman Tree. it seems like the program
is building the tree correctly, it's just that the recursive functions
that traverse the tree is giving some problems...  they are located near
the end above the main..

they are:

void makeCode()
void printCode()
int byteCount()
int bitCount()

====================================

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int to,difBytes; /*total amount of chars,amount of different bytes*/

void sort(int n[],int m[]); /*sorts n and m from greatest to least*/
int total(int o[]);  /*calculates the sum of values in o */
void print(int n[], int m[]);  /*prints the arrays*/

struct node{
        int byteValue; /*ascii value*/
        int count;  /*frequency*/
        char code[20]; /*path*/

        struct node *left;
        struct node *right;

Quote:
};

struct node *tinit(int n, int m);/*makes a node*/
void makeNodes(struct node *t[],int n[],int m[]); /*makes nodes from n and
m*/
struct node *makeHuffNode(struct node *a,struct node *b);/*combines 2
nodes*/
struct node *makeHuffTree(struct node *t[]);/*builds the tree*/
void sortTree(struct node *t[],struct node *p,int size);/*adds in the new
node
                                                       deletes used
nodes*/

int isLeaf(struct node *p);/*determines if p is a leaf*/
void makeCode(struct node *head);/*makes the code for each node*/
void printCode(struct node *head);/*prints the leaves of the tree*/
int byteCount(struct node *head);/*counts the number of leaf nodes*/
int bitCount(struct node *head);/*counts the amount of bits needed to
compress
                                  this file*/

/*************  assignment 3 functions  *******************************/

/*sorts n in decreasing order*/
void sort(int n[],int m[]) {
   int i,j,nTemp,mTemp;
   i=1;

   for(i;i<256;i++) {
      for(j=1;j<256;j++) {

         if(n[j-1]<n[j]) {  /*puts the smaller number at the end*/

            nTemp=n[j-1];
            n[j-1]=n[j];
            n[j]=nTemp;

                mTemp=m[j-1];
            m[j-1]=m[j];
            m[j]=mTemp;
         }
      }
   }

Quote:
}

/*meant to be called after sorting.*/
int total(int o[]) {
   int i=0,t=0;

   for(i;i<256;i++) {
           if(o[i]!=0) t+=o[i];
           else break;
   }
   return t;

Quote:
}

void print(int n[], int m[]) {
   int p,lineCount;

   p=0;
   lineCount=0;

   for(p;p<256;p++)
   {
      if(n[p]!=0) {
         difBytes+=1; /*find the amount of different bytes*/

         if(m[p]<32 || m[p]>126) printf("%3d    %-6d  ",m[p],n[p]);

         else
            printf("%3d(%c) %-6d  ",m[p],m[p],n[p]);

         if(lineCount==3) {   /*prints 4 things per line*/
            printf("\n");
            lineCount=0;
         }
         else lineCount++;
      }
      else break;
   }
   printf("\nTotal number of characters = %d.\n",to);

Quote:
}

/**************** builds a huffman tree **********************/

/* makes a new node and allocates memory for it */
struct node *tinit(int n,int m){
        struct node *p;
        p=(struct node *) malloc(sizeof(struct node));
        p->byteValue=m;
        p->count=n;
        return p;

Quote:
}

/*makes nodes from n and m and puts them in t.
n and m are arranged from greatest to least
this fucntion puts it in t from least to greatest...
*/
void makeNodes(struct node *t[],int n[],int m[]){
        int i,s;
        i=0;

        while(n[i]!=0){

                t[i]=tinit(n[i],m[i]);
                i++;
        }

Quote:
}

/*makes a new node with two previous nodes.. it allocates memory
  for new node*/
struct node *makeHuffNode(struct node *a,struct node *b){
        struct node *p;

        p=(struct node *) malloc(sizeof(struct node));
        p->left=a;
        p->right=b;
        p->count=a->count+b->count;

        return p;

Quote:
}

/*get array t, and a node p, size is the size of t[]
  finds where p belongs in t and puts it there*/
void sortTree(struct node *t[],struct node *p,int size){
        int i=size-3;

        p=makeHuffNode(t[size-2],t[size-1]);/*make a new node*/
        t[size-1]=NULL;
        t[size-2]=NULL;

        while(i>=0){ /*go through the rest of the array*/
                if(t[i]->count>=p->count){
                        t[i+1]=p;
                        break;
                }
                else if(i==0&&t[i]->count<p->count){/*put at end*/
                        t[i+1]=t[i];
                        t[i]=NULL;
                        t[i]=p;
                }

                else{/*else shift it*/
                        t[i+1]=t[i];
                        t[i]=NULL;
                }
                i--;
        }

Quote:
}

/*builds the huffman tree from t[]*/
struct node *makeHuffTree(struct node *t[]){
        struct node *p;
        int size=difBytes;

        while(size>=2){
                if(size>2){/*while there is more than 2 nodes*/
                        sortTree(t,p,size);
                }
                else if(size==2){/*if there are 2 nodes left*/
                        p=makeHuffNode(t[1],t[0]);
                }
                size--;
        }
        return p;

Quote:
}

/********             assignment 5 stuff     *******/

/*checks if p is a leaf
  returns a 1 if p is a leaf or 0 if p isn't*/
int isLeaf(struct node *p){
        int i;

        if((p->left == NULL) && (p->right == NULL)) i=1; /*if p is a
leaf*/
        else i=0; /*if it isn't*/

        return i;

Quote:
}

/*traverses the tree pre order and puts in the code for each node*/
void makeCode(struct node *head){

        /*copy the heads code and add either a 1 or 0 to right or left
node*/
        if(head->left!=NULL){
                strcat(strcpy(head->left->code,head->code),"0");
                makeCode(head->left);
        }

        if(head->right!=NULL){
                strcat(strcpy(head->right->code,head->code),"1");
                makeCode(head->right);
        }

Quote:
}

/*traverses the tree pre order and prints only the leaves*/
void printCode(struct node *head){

        if(isLeaf(head)==1){

                printf("%x",head -> byteValue);

            if(head->byteValue < 32 || head->byteValue > 126) printf("
");
                else printf("(%c)",head->byteValue);

                printf("%6d",head->count);
                printf("  %-s\n",head->code);
        }

        if(head->left!=NULL) printCode(head->left);

        if(head->right!=NULL) printCode(head->right);

Quote:
}

/*traverses the tree pre order
  adds 1 to c if a leaf node comes up*/
int byteCount(struct node *head){
        int c;
        c=0;

        if(isLeaf(head)==1) c=1;

        if(head->left!=NULL) c+=byteCount(head->left);

        if(head->right!=NULL) c+=byteCount(head->right);

        return c;

Quote:
}

/*gets the amount of bits needed to encode the file*/
int bitCount(struct node *head){
        int bit;
        bit=0;

        if(isLeaf(head)==1) bit=(head->count*strlen(head->code));

        if(head->left!=NULL) bit+=bitCount(head->left);

        if(head->right!=NULL) bit+=bitCount(head->right);

        return bit;

Quote:
}

/********************    main     ***************************/

void main(int argc, char *argv[]) {

   int c,i;
   int n[256],m[256];
   FILE *infp;

   struct node *t[256];
   struct node *head;

   int tC,dB,fL,fLB; /*total char, average bits,
                          file length, file length in bits*/
   float aB;/*average bits*/

   for(i=0;i<256; i++) { /*initialize all values of n and m */
       n[i]=0;
       m[i]=i;
   }

   infp = fopen(argv[1], "rb");

   /*reads in each char in file */
   while((c = getc(infp))!=EOF) {  
      n[c]++;
   }      

   fclose(infp);
   sort(n,m);  
   to=total(n);  /*get total amount of chars*/
   print(n,m);

   makeNodes(t,n,m);
   head=makeHuffTree(t);

   printf("%d\n",head->count);
   printf("%d\n",head->left->count);
   printf("%d\n",head->right->count);
   printf("%d\n",head->left->left->count);

   /*
   if(isLeaf(head)==0) printf("hello\n");

   makeCode(head);
   printCode(head);

   dB=byteCount(head);
   fL=bitCount(head);
   fLB=(fL+7)/8;
   aB=fL/tC;

   printf("No. of characters = %d .  ",tC);
   printf("Average bits per character = %0.6f.\n",aB);
   printf("No. of different bytes = %d.\n",dB);
   printf("File length = %d bits (%d bytes)",fL,fLB);
*/
   }

--
March's Quote
"Ancient wisdom proclaims the reason farts have an obnoxious odor is
 so that the deaf may enjoy them also."
-Bill Donohue, PSM

February's Quote
"One language that all programmers know is profanity."
-Unknown

January's Quote
"I loathe people who keep dogs. They are cowards who haven't got
 the guts to bite people themselves."
-August Strindberg

               ==========================================
               |                                        |
               |                  YAWN                  |
               |       http://www.*-*-*.com/ ~kuom      |
               |                                        |
               ==========================================



Mon, 19 Aug 2002 03:00:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. HELP with Huffman Tree Traversal - huff2.c (1/1)

2. HELP with Huffman Tree Traversal - huff2.c (1/1)

3. HELP with Huffman Tree Traversal - huff2.c (0/1)

4. Huffman coding/huffman tree

5. Binary tree traversal - a complex case - Help!

6. HELP!: non-recursive binary tree inorder traversal algorithm

7. HELP with Huffman Tree

8. Help on Huffman trees 2

9. Help on Huffman trees

10. Level order Traversal of a Binary Tree ??

11. given preorder and postorder traversals of a binary tree How can we find inorder

12. binary tree traversal

 

 
Powered by phpBB® Forum Software