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?

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 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 ; )

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 }