Thread: How can I traverse a huffman tree

  1. #1
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56

    How can I traverse a huffman tree

    Ok, I realize I probably did this the hard way, but I'm having a small problem with this huffman tree thing. I wrote a program that reads in a char and it's frequency count, puts each in a linked list, sorts it, then combines elements until a tree is built.

    Looking at various examples, I have perfected it to build trees that correspond with the examples.

    Now I need to know, how the heck do I traverse the thing? For example, if I want to find the node containg 'a', how do I get to it wihtout searchign the whole tree (which could be VERY time consuming). Any ideas?

  2. #2
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56
    Here is the function I am using to find the node containing the char searched for, however when I call the function (called via list = findchar(list, c) I just get trash returned, supposing that the pointer is perhaps somehow refrencing a memory location outside of the tree?

    Code:
    node_ptr find_char(node_ptr &p, char x) 
    	{
    	
        	if (p != NULL) 
    		{ 
    		if (p->key == x)
    			{
    			cout << p->key << endl;  // here, it prints the key that is the same a sx
    			cout << p->val << endl;
    			return p;
    			}
    		else
            		{
    			find_char(p->left, x);  // take left subtree            		
    			find_char(p->right, x); // take right subtree
    			}
    }
    }
    I am Error. When all else fails, use fire.

    My Current Screenshot

  3. #3
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    I don't know how orthodox my approach is, but I just did some huffman stuff recently and this is how I did the compressing end of it:
    Code:
    // allow easy indexing (with no searching) to any node  
    NODEP *allNodes = new NODEP[UCHAR_MAX + 1];  
    for (int i = 0; i < (UCHAR_MAX + 1); ++i)
      allNodes[i] = NULL;
    
    for (NodeDequeItr itr = _deque.begin(); itr != _deque.end(); ++itr) {
      if ((*itr)->isLeaf())
        allNodes[(*itr)->cc.ch] = *itr;
    }
    Create an array of 256 node pointers and initialize each to NULL. Then I go through my deque of Node pointers and when I hit a leaf, I set the pointer in the array (with the index of the character) to the leaf. For example, if I hit a leaf and the character of the node is "m" then I set the node* at index 'm' to the leaf (allNodes['m'] = *itr).
    Then when I'm reading a character at a time from the source file, I can easily get the corresponding node by using the character itself as the index to the node* array.

    Food for thought maybe...

    [EDIT]
    one other thing to note if you use my method is that when indexing, make sure it's an unsigned char you are subscripting with ; )
    Last edited by LuckY; 04-28-2003 at 12:51 PM.

  4. #4
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56
    Well, I changed my mind on how I was going to traverse the tree. This impementation is really quite long, and I feel like an idiot because after slaving over all this code, I discovered the simple, two page way to do it.

    So view it and roll on the floor laughing!

    Code:
    /************************************* 
     * Filename: CSC310-Assignment5.cpp
     * Description: Prompts the user for an input file, which is
     * assumed to contain one character (including ' '), followed
     * by a blank space, followed by a frequency number, on each
     * line. A Huffman tree is then built from these values. Finally
     * the user is prompted for an output file, which the program
     * writes each char followed by a blank, followed by it's
     * appropriate Huffman code, in asscending alphabetical order.
     *************************************************************/
    #include<iostream>
    #include<fstream>
    #include<cstring>
    using namespace std;
    
    struct node
            {
            char key; int val;
            node *left, *right, *next, *prev;
            };
    
    typedef node* node_ptr;
    
    void add_tree(node_ptr &head, node_ptr &list);
    /**************************************************
     *	Description: Creates a parent node from two smallest adjacent nodes on
     * the list.
     *************************************************/
    
    void add_list(node_ptr &head, node_ptr &list, int value, int character);
    /**************************************************
     *	Description: Adds nodes to a list with a character and number
     * attached to each node.
     *************************************************/
    
    void sort_list(node_ptr &head, node_ptr &list);
    /**************************************************
     *	Description: Sorts the nodes on the list directly via insertion
     * sort. Ensures children links are maintained.
     *************************************************/
    
    void find_code(node_ptr &root, node_ptr &list, char matrix[][32]);
    /**************************************************
     *	Description: Finds the Huffman code for each char that was read
     * in and attached to the tree. Reads each char and it's adjacent
     * code into matrix[][32]
     *************************************************/
    
    void sort_array(char a[], int size);
    /**************************************************
     *	Description: Simply uses an insertion sort to sort a  given
     * array. In this case, the char array for refrencing when
     * printing to file in alphabetical order.
     *************************************************/
     
    void print_matrix(char matrix[][32], int count, char a[]);
    /**************************************************
     *	Description: Prints each char, followed by a space, followed
     * by it's appropriate Huffman code, to a user designated output
     * file in ascending alphabetical order.
     *************************************************/
    
    int main(void)
    	{
       node_ptr root=NULL, list=NULL;  // initialize root and list pointer
    	int v = 0,size = 0;             // v = frequency #, size = number of characters in file
    	char ifilename[15];
    	char matrix[128][32];			  // holds the chars with corresponding code for sorthing
    	char a[128];					  // index of chars stored for refrencing
    
    	ifstream read;
    
    	/************ Prompt for input file & open stream **************************/
    	cout <<"Enter a file name to read from: ";
    	cin>> ifilename;
    	read.open(ifilename);
    
    	if (read.fail())
    		{
    		cout << "File not found, exiting..." << endl;
    		exit(1);
    		}
    	/** End file input stream opening **/
    
    	/************* read from file ********************************************/
    	while(read.get(a[size]))                  // read char into array
    		{
    		sort_array(a, size);	          // keep array sorted.
    		read.get();                       // get the next char, which should be ' '
    		read >> v;                        // read the frequency number
    		add_list(root, list, v, a[size]); // add the node to the list
    		size++;   		                   // increment size
    		read.ignore(1,'\n');
    		}
    	read.close();                       // read from stream finished, close stream
    	/*************** End read from file ***************************************/
    
    	/*************** Build Huffman tree from list *****************************/
    	while(list->next != NULL)
    		{
    		sort_list(root, list);       // ensure 1st 2 nodes are the smallest on list...
    		add_tree(root,list);         // ..if two are equal, node with a char is 1st
    		if(root->next == NULL)break; // breakes when the root is the only node left
    		}
    	/*************** Huffman tree building is complete *************************/
    
       /**************  Here, find each char in the tree and encode ***************/
    	find_code(root, list, matrix);
       /***************** End encoding ********************************************/
    
    	/**************** Print to file ********************************************/
    	print_matrix(matrix, size, a);
       /**************** End of print to file *************************************/
    
       return 0;
       }
    
    void add_tree(node_ptr &head, node_ptr &list)
    	{
    	list = head;                 // set node to root
    
    	node_ptr tmp = new node;     // create node to be used as parent node
    	tmp->key = 0;                /* to avoid confusion, parent nodes will have an
       									     escape sequence char (shouldnt be in a file) */
    	tmp->val = list->val + list->next->val;  // set node's value to the sum of children
    	tmp->left = list;            // connect smallest node to the left
    	tmp->right = list->next;     /* connect the next node, which should be more or equal
                                       to the right. */
    	tmp->right->prev = tmp;      // point prev links of children nodes to parent
    	tmp->left->prev = tmp;
    
    	if(list->next->next != NULL)
    		{
          /****** Disconnect children from list ***/
    		list = list->next->next;
    		list->prev->prev->prev = tmp;
    		list->prev->prev->next = NULL;
    		list->prev->prev = tmp;
    		list->prev->next = NULL;
    		list->prev = NULL;
    		head = list;
    
          /**** cycle through list and connect parent to the end ***/
    		while(list->next != NULL)list = list->next;
    		list->next = tmp; tmp->prev = list; tmp->next = NULL;
    		}
    	else
    		{                            // case if parent is last node on list
    		list->next->prev = NULL;
    		list->next = NULL;
    		head = tmp;
    		}
    	list = head;
    	}
    
    void add_list(node_ptr &head, node_ptr &list, int value, int character)
    	{
    	if (!list)         			// if list is empty
    		{                       // set val and key, and set as head
    		list = new node;
    		list->key = character;
    		list->val = value;
    		head = list;
    		list->next = NULL;
    		list->prev = NULL;
    		}
    	else
    		{
    		while (list->next != NULL) list = list->next;  //cycle to end of list
    		node_ptr tmp = new node;                  // create new node
    		tmp->key = character;                     // set key and val
    		tmp->val = value;
    		list->next = tmp;                         // conenct previous node to new node
    		tmp->next = NULL;                         // next node == NULL
    		tmp->prev = list;                         // set prev link to previous node
    		}
    }
    
    void sort_list(node_ptr &head, node_ptr &list)
    	{
    	node_ptr temp;                             //pointer for sorting
    	node_ptr tmp = head;                       // set temp to head
       /*********************************************************
        * Begining with the 2nd node, cycle through the list until
        * a node is encounered that is greater than the previous node.
        * Then continue cycling back through the list changing links
        * until the node is in it's correct place.
        ***********************************************************/
    	for (tmp = tmp->next; tmp; tmp = tmp->next)
    		{
    		list = tmp;
    		while(list->prev->val > list->val)
    			{
    			temp = list->prev;
    			temp->next = list->next;
    			if(temp->prev != NULL)       //if temp is not at the beginning of the list
    				{
    				temp->prev->next = list;  // set the previous link to list
    				list->prev = temp->prev;  // set list's prev link to the node before temp
    				}
    			else
    				{
                list->prev = NULL;        // set list->prev to NULL
    				head = list;              // point beginning of list to node
                }
    				if(list->next != NULL) list->next->prev = temp; //sets next node prev to temp
    
                temp->prev = list;        // temp's previous link is pointing to list
    				list->next = temp;        // list's next link is pointing to temp
    
    				if(!list->prev)break;     // break if at beginning of list
    			}
    		}
    	}
    
    void find_code(node_ptr &root, node_ptr &list, char matrix[][32])
    	{
    	char code[30];        //code for character to be encoded (30 bit implementation)
    	int count = 0;		    //counts # of lines needed in output file
    
    	for (int i = 0; list; i++)
    		{
    		if(list->left != NULL)
    			{
    			code[i] = '0';       // insert 0 in code when left branch is taken
    			list = list->left;   // take left branch
    			}
    		else if(list->right != NULL) // should only evaluate to true if right is taken
    			{
    			code[i] = '1';       // insert 1 if right branch is taken
    			list = list->right;  // take right branch
    			}
    		else                    // leaf is reached
    			{
    			if(list->key != 0)   // only consider nodes containg chars other than 0
    				{
    				matrix[count][0] = list->key;    // sets 1st element to char
    				matrix[count][1] = ' ';          // sets 2nd element to blank space
    				for (int j = 2; j < i + 2; j++)
    					{
    					matrix[count][j] = code[j-2]; // adds huffman code to adjacent char
    					matrix[count][j+1] = '\0';    // ensures '/0' is in the correct position
    					}
    				count++;
    				}
    			if(code[i-1] == '0')     // delete leftmost node if it was read
    				{
    				list->prev->left = NULL;
    				delete list;
    
    				}
    			else if (list->prev == NULL)  // breaks if last node is root
    				break;
    			else                          // delete right node if it was read
    				{
    				list->prev->right = NULL;
    				delete list;
    				}
    			i = -1;  							//sets i to 0 on next run
    			list = root;                  // set list pointer to top of tree
    			}
    		}
    
    	}
    
    void sort_array(char a[], int size)
    	{
       /** Simple insertion sort to sort array of characters for file output ***/
    	int temp = 0, j = 0;
    	for (int i = 0; i < size; i++)
    		{
    		temp = a[i]; j = i;
    		while( a[j-1] > temp)
    			{
    			a[j] = a[j - 1];
    			j--;
    			}
    		a[j] = temp;
    		}
    	}
    
    void print_matrix(char matrix[][32], int count, char a[])
    	{
    	ofstream write;
    	char ofilename[15];		// output file name
    
       /**** Prompt user for output file ***/
       cout << "Enter an output file to write to: ";
    	cin >> ofilename;
       /***** End Output file prompt ******/
    
       /*** Open Output File ****/
    	write.open(ofilename);
    	if(write.fail())
    		{
    		cout << "Error encountered!" << endl;
    		exit(1);
    		}
       /*** End File Opening ****/
    
    	for (int i = 0; i < count; i++)
    		{
    		for (int j = count-1; j > -1; j--)
    			{
    			if (a[i] == matrix[j][0])      // cycle through matrix until equal to
    				{                           // a[i]. Array a[i] is sorted.
    				for (int k = 0; matrix[j][k] != '\0'; k++)
    					write << matrix[j][k]; // output <char> <blankspace> <huffman code>
    				}
    			}
    		write << endl;                  // write new line
    		}
    	write.close();                     // close output
    
    	}
    I am Error. When all else fails, use fire.

    My Current Screenshot

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM