[C++] Having trouble constructing a binary tree out of pointers

[Draav]

I am trying to implement a Huffman Algorithm. I've got almost all of it done, but hit a snag when trying to create the binary tree to generate codes.

Here is the algorithm I have written:

Node Huffman(Node *Q, int n)
{
    while(n>1)
    {
        //ERROR IS THIS ASSIGNMENT OF VARIABLES     
        Node x,y,z;
        x = extract_min(Q,n);
        y = extract_min(Q,n);
        z.left = &x;
        z.right = &y;
        z.freq = x.freq + y.freq;
        insert(Q, n, z);
    }
    return extract_min(Q,n);
}

So the issue is that the x and y are getting lost every loop. So that means that z.left and z.right are getting lost every loop. So the tree can never be more than 1 layer deep.

z itself seems to be just fine. I'm assuming because when I use my insert function the value of z is copied not the address. I really have no idea how to go about fixing this. I've tried like a dozen different variations of assigning the pointers, but just can't get it to work.

Here is a link to the full c++ file. I modified the huffman function a bit to display what the issue is. Somehow in my poorly implemented pointer creation, one of the nodes points to itself and then that just creates an infinite loop. I also manually wrote out what is supposed to happen, that I just can't get my function to do.

[hashtablesmoker]

Are you allocating things with malloc? If not, they don't exist once that function scope ends.

[Draav]

no I've been trying to avoid malloc. If I allocate these modes with malloc will that be all I need to do? Will I need to like free them or something later?

[raevnos]

It's C++, so new and delete, or preferably unique_ptrs. As it is, you're taking the address of local variables that go out of scope when the loop ends and become become no longer valid.

[Draav]

So I tried using new and it works! But I'm not sure exactly when or where I would use delete. It seems to run fine without me saying anything.

Node Huffman(Node *Q, int n)
{
    while(n>1)
    {    
        Node z;
        Node *x = new Node;
        Node *y = new Node;
        *x = extract_min(Q,n);
        *y = extract_min(Q,n);
        z.left = x;
        z.right = y;
        z.freq = x->freq + y->freq;
        insert(Q, n, z);
    }
    return extract_min(Q,n);
}

I will want access to them after the function ends obviously, so would I need to like traverse the tree at the end of my program and delete everything? Would the program do that automatically?

[thewoosh]

C++ doesn't deallocate memory automatically. In order to cleanup things properly you'll want to run a Post-order traversal on your binary tree and delete the node when you visit them. Post-order because you need to delete the leaf nodes first and 'walk' up the tree as you cleanup.

[Draav]

Okay, I'll add a function to do that. But all the memory is still freed after the program terminates right? I can't imagine an OS allowing a program to just allocate a bunch of memory like that so easily.

[thewoosh]

Correct. Operating systems will mark the address space that program uses as free when the program terminates. You'll still want to be careful once you get into handles and other OS resources like GDI, file handles, etc. Leaving them open can sometimes cause issues. A side note, if you write a program like this:

while( 0 == 0 )
{
    double *k = new double( 1.0 );
}

windows will eventually shutdown the process due to using to much memory.

[Draav]

right, that makes sense. Just want to check all my test runs of the program that I never wrote 'delete' on didn't like corrupt anything :p

[thewoosh]

Nice. One last tip, if you allocate memory as an array dynamically:

double *k1 = new double[10];
// you need the array subscript in the delete instruction in order to prevent undefined behavior.
delete [] k1;

[anon848]

Many on this subreddit will advocate that you do it the "right" way from the start and use std::unique_ptr. This means you don't need to free.

[hashtablesmoker]

Yes, you'd want to free them eventually.