Thread: Traversing a binary tree with pointers

Hi guys,
Alright ya'll I need your help with a project that I am developing at school for one of my classes. I need to do a Huffman encoder. Basically my program reads a text file that analyzes the frequency of each character. and places them into STL maps as nodes. It then constructs a binary tree with the assistance of a heap(with a vector as its container). At the end, I have to traverse this tree that I have constructed. At this point, I have no idea have to traverse the tree and all the resources only give me object based implementations. The poscondition of the binary tree construction is that I have the pointer to the parent node and its children nodes. I was thinking about recursive functions but I do not know where to begin. Any feedback would be much appreciated. Here's what I have so far:

Code:

....
 // Huffman Encoding scheme                                                                    
  while(!v.empty()){                                                                            
    // 1) Read and then pop the two lowest nodes in the vector(heap)                            
    lchild = v.front();                                                                         
    pop_heap(v.begin(), v.end(), lt);                                                           
    v.pop_back();                                                                               
                                                                                                
    // NOTE: if vector is not empty at this point                                               
    // pop the rchild and set the parent num to both                                            
    // numbers, else if vector is empty, pop the vector                                         
    // and set that pointer as the rchild                                                       
                                                                                                
    rchild = v.front();                                                                         
    pop_heap(v.begin(), v.end(), lt);                                                           
    v.pop_back();                                                                               
                                                                                                
                                                                                                
    cout << "lchild value: " << *lchild << endl;                                                
                                                                                                
    cout << "rchild value: " << *rchild << endl;                                                
                                                                                                
                                                                                                
                                                                                                
    // 2) Create a new node which is the parent of the two lowest probability nodes.            
    parent = new Node(lchild->getNum() + rchild->getNum());                                     
    parent->set_lchild(lchild);                                                                 
    parent->set_rchild(rchild);
    cout << "parent: " << *parent << endl;                                                      
                                                                                                
    // 3) Assign the new node the sum of its children and push the parent node into the heap    
    v.push_back(parent);                                                                        
    push_heap(v.begin(),v.end(), lt);                                                           
                                                                                                
  } // end while.huffman                                                                        
                                                                                                
                                                                                                
  // Postcondition: We have emptied out the vector v and have the                               
  // pointer to the root of our newly constructed binary tree!! Yay!!                           
                                                                                                
                                                                                                
  cout << "Final Parent Value: " << *parent << endl;                                            
  cout << "Node of lchild: " << *parent->get_lchild() << endl;                                  
  cout << "Node of rchild: " << *parent->get_rchild() << endl;
....

If you guys have any questions, please let me know. Thank you so much for your help.

There are lots of ways of doing this, easyest is with recursion. The basic traversals are pre-order, post-order and in-order.

Here's an in-order traversal to print the tree.

Code:

void print(const node *n, int d=0) {
    if(n) {
        print(n->left(),d+1);
        for(int i=0;i<d;i++) std::cout << "    ";
        print(n->right(),d+1);
    }
}

turn it sideways and you got something sort of tree like.

Here is an elegant, but wastefull post-order solution to your next question.

Code:

void print(const node *n, std::string s="") {
    if(n) {
        if(n->leaf()) {
            std::cout << s << ':' << *n << std::endl;
        } else {
            print(n->left(),s+'0');
            print(n->right(),s+'1');
        }
    }            
}

Thank you so much for your code grib, actually I had already implemented a way for my code to print out all the vertices in a preorder format.

Code:

void preorder(Node* ptr){                                                                       
  if (ptr == 0)                                                                                 
    return;                                                                                     
                                                                                                
  // process current node                                                                       
  cout << *ptr << endl;                                                                         
  preorder(ptr->get_lchild());                                                                  
  preorder(ptr->get_rchild());                                                                  
}

As you can see printing out the vertices in preorder format is relatively simple. My problem lies in the fact that we need to get the huffman code for each character. In other words, assuming you already have a fully constructed binary tree,every left path you take, you should store a '0' somewhere, every right path you take should store a '1' somwhere, you continue in this fashion until you reach a node with a character in it. Once you've arrived at a character(that has not been visited) before, print out the unique path from the root in terms of '0' and '1'. That's my obstacle. I just do not know how to store the '0' and '1' until you get to a character...
If you want to get a graphical understanding I am attaching a bmp file to this post.

Pass another reference parameter into preorder() and use it to "record" what path is being taken.
For example, if you use a string, then whenever you traverse left you += '0' and when you traverse right you += '1'.
When the function is done recursing, the string will contain a "recording" of the path it took.

gg

Not to be rude but does your browser have a scrollbar? I answered your next question in string format. This should have been enough to figure out how to get the huffman code as an int. I used strings both to make them easy to print, so you could see what was going on, and also so that you could have a tree of arbitrary depth. You can do the same thing with shifts and adds, though I recommend having a depth paramiter as well as passing both the depth and code by value, rather than reference. You can use reference if you want, but it makes life more complicated.

Originally posted by grib
Not to be rude but does your browser have a scrollbar?

No

gg

codeplug: wasn't actually talking to you I miss lynx.

grib, I apologize for not seeing the second piece of code. I must not have viewed it properly on my browser. Thank you for all your help in this matter.

Not a problem, I just found it funny that it started out "and to answer your next question..." and guess what your next question was.