Traversing a binary tree with pointers

This is a discussion on Traversing a binary tree with pointers within the C++ Programming forums, part of the General Programming Boards category; Hi guys, Alright ya'll I need your help with a project that I am developing at school for one of ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    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.

  2. #2
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    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');
            }
        }            
    }

  3. #3
    Registered User
    Join Date
    Sep 2002
    Posts
    92
    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.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,702
    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

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    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.

  6. #6
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,702
    Originally posted by grib
    Not to be rude but does your browser have a scrollbar?
    No

    gg

  7. #7
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    codeplug: wasn't actually talking to you I miss lynx.

  8. #8
    Registered User
    Join Date
    Sep 2002
    Posts
    92
    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.

  9. #9
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree
    By Ideswa in forum C Programming
    Replies: 12
    Last Post: 10-25-2007, 01:24 PM
  2. Binary Taxonomy Tree
    By jk1998 in forum C++ Programming
    Replies: 2
    Last Post: 09-02-2007, 05:18 PM
  3. binary tree complete check
    By ichijoji in forum C++ Programming
    Replies: 5
    Last Post: 11-12-2004, 05:48 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21