Building a tree from preorder in C++

Question

I am working on a compression/decompression assignment. I'm trying to write a C++ method to build a tree using the following preorder traversal from the header of my compressed file: 001c1b01a01e1d 0 represents an internal node while 1 represents a leaf. Every time I create a node, I set the code of that node to either 0 or 1, because I will be using another method to decode the tree and it must know how to traverse down different sides by using these codes. Whenever I reach a 1 in the preorder traversal string, I set the node's "symbol" field to the following character in the preorder string. I can't get it to work though. Can anyone help? Here is my code ("bitsToRead" just represents the length of the preorder string so the method knows when to stop) Thanks!

void HCTree::buildFromHeader(ifstream& in, HCNode* n, int codeToUse) {

   if( bitsToRead > 0) {
      char c = in.get();
      bitsToRead--;
      if(c == '0') {
         n = new HCNode(0, 0, 0, 0, 0, codeToUse);
         if(rootSet == 0) {
            root = n;
            rootSet = true;
         }
         HCNode* left;
         n->c0 = left;
         HCNode* right;
         n->c1 = right;
         buildFromHeader(in, left, 0);
         buildFromHeader(in, right, 1);
      }
      else { 
         byte symbol = in.get();
         n = new HCNode(0, symbol, 0, 0, 0, codeToUse);
         bitsToRead--;
         n->c0 = n->c1 = NULL;
      }
   }
}

Xiangyan Sun Xiangyan Sun · Accepted Answer · 2013-11-18T02:32:15

It seems changing

void HCTree::buildFromHeader(ifstream& in, HCNode* n, int codeToUse) {

to

void HCTree::buildFromHeader(ifstream& in, HCNode* &n, int codeToUse) {

will do the work.

Plus the rootSet logic can be omitted. You just call

buildFromHeader(in, root, codeToUse)

from the caller.

EDIT:

I misread your code in the first place. n = new HCNode(0, symbol, 0, 0, 0, codeToUse); is the code made me suggests to use a reference. Because what you want to do here is the changing the pointer passed from the leaf's ancestor (the n->c0 = left and n->c1 = right stuff). To make the whold thing work, in addition to the change above, change

HCNode* left;
n->c0 = left;
HCNode* right;
n->c1 = right;
buildFromHeader(in, left, 0);
buildFromHeader(in, right, 1);

to

buildFromHeader(in, n->c0, 0);
buildFromHeader(in, n->c1, 0);

This will let the callee to assign values transparently to pointers inside struct using references.

Building a tree from preorder in C++

1 Answers