Huffman Tree - all pointers pointitng to the same location

128 Views Asked by At

I am writing the Huffman coding algorythm and I have a problem with pointers. Here's my code:

TreeNode Algorythm::createATreeAndReturnRoot(){
    while (treeNodesList.size() > 1){
        sortLeafs();

        TreeNode lowestF = treeNodesList.front(); treeNodesList.pop_front();
        TreeNode lowestS = treeNodesList.front(); treeNodesList.pop_front();
        TreeNode sum = TreeNode(&lowestF, &lowestS);

        tree.push_back(lowestF);
        tree.push_back(lowestS);
        tree.push_back(sum);

        treeNodesList.push_back(sum.item);
    }
    return tree.at(tree.size()-1);
}

And the TreeNode constructor:

TreeNode::TreeNode(TreeNode* leftChild, TreeNode* rightChild)
{
    right = rightChild;
    left = leftChild;
    item.setLetter('?');
    item.setLetterCount(leftChild->item.getLetterCount() + rightChild->item.getLetterCount());
}

class TreeNode
{
public:
    TreeNode();
    TreeNode(TreeNode* leftChild, TreeNode* rightChild);
    ~TreeNode();
    TreeNode::TreeNode(TreeNode* treeNode);
    TreeNode::TreeNode(TreeItem treeItem);
    bool isLeaf();
    bool hasLeftChild();
    bool hasRightChild();
    bool operator< (TreeNode &other);

    TreeItem item;
    TreeNode *left;
    TreeNode *right;
};

At the end I have a tree and root has correct letter count, but all the pointers left and right in the tree point to the same location (the childs of a root).

1

There are 1 best solutions below

2
On BEST ANSWER

You have this problem because you're not correctly using pointers. Look, you create two TreeNode's on a stack, then you take their addresses, and make them children of new node. But, because they are on stack, they have the same address. So all the left and right children will point to the same location.

You probably wanted to allocate them on heap using new or shared_ptr.