CODEWITHSUNDEEP
c++pointersbinary-tree
Jeremy
Jeremy

Reputation: 41

Recursive struct without pointers? (Huffman)

I defined a binary tree this way:

struct btree {
    int x;
    btree* left_child = nullptr;
    btree* right_child = nullptr;
};

Then I have a vector of floats (prob_distr) and I turn each float into a leaf and I put all the leafs into a priority queue (with a custom sort function but it doesn't matter here).

auto comp = [] (btree &a, btree &b) -> bool { return a.x > b.x; };
priority_queue<btree, vector<btree>, decltype(comp)> q(comp);

for(auto t: prob_distr)
{
    btree leaf;
    leaf.x = t;
    q.push(leaf);
}

For the Huffman algorithm, I then loop on the priority queue until it only has 1 element left: I take the 2 nodes at the top out of the queue, I create a new node with these two nodes as children and I put these new node into the queue.

while(q.size() >= 2)
{
    btree left = q.top(); q.pop();
    btree right = q.top(); q.pop();

    btree root;
    root.x = left.x + right.x;
    root.left_child = &left;
    root.right_child = &right;

    q.push(root);
}

The problem is that I have pointers to the left and right binary trees, and these trees are deleted when going out of the while loop. Then I have pointers pointing Nothing. Is there any way to solve this, for example by having a struct which stores the children trees and not just pointers, or by storing the nodes somewhere else without it gets too complicated?

Upvotes: 2

Views: 412

Answers (1)

Ari Hietanen
Ari Hietanen

Reputation: 1769

You need to use pointers here, because the size of the structure has to be known at the compile time. If you would have struct itself as a member variable the memory requirement would recursively go to infinity.

You need to dynamically allocate the memory with new. The memory allocated with new is allocated until you explicitly release it by using delete. Just write

root.left_child = new btree(left);
root.right_child = new btree(right);

As already said, you also need to use delete to free the memory of the children. Be careful not to make copies of children which do not get deleted, and not to delete children which are still in use somewhere else. Consider using smart pointers.

Upvotes: 2

Related Questions