CODEWITHSUNDEEP
arrayscbinary-search-treehuffman-codepreorder
verra123
verra123

Reputation: 1

How to turn char array into BST?

I'm currently trying to turn a char array into a Huffman Tree. For example, if the char array is {0,0,1,a,1,b,0,0,1,c,1,d}, each 0 corresponds to a branch node, while each 1 corresponds to a leaf node, and the char following the 1 is the value stored in the leaf node like so: Preorder Tree. I get that this must be done recursively, but I'm getting confused by the recursive logic. Each node struct contains a char value, a bool which checks whether or not the node is a leaf node, and a left and right node struct.

HuffNode* build_Tree(char* topology, int index, int nodes_written, int sz)
{
    if(nodes_written == sz)
    {
        return NULL;
    }
    if(topology[index] == '0')
    {
        HuffNode*  left = build_Tree(topology, index + 1, nodes_written + 1, sz);
        HuffNode*  right = build_Tree(topology, index + 1, nodes_written + 1, sz);
        HuffNode* newnode = create_HuffNode(0, false);
        newnode->left = left;
        newnode->right = right;
        return newnode;
    }
    else if(topology[index] == '1')
    {
        HuffNode* endbranch = create_HuffNode(topology[index+1], true);
        return NULL;
    }
    return NULL;
}

I call it like:

HuffNode* full_tree = build_Tree(actual_char_Topology, 0, 0, sz);

from another function, but when I try to print out full_tree, there's nothing there. I think I'm getting confused from what happens to index and sz when I hit a '1', any advice would be appreciated!

Upvotes: 0

Views: 267

Answers (1)

selbie
selbie

Reputation: 104559

I'm pretty sure this needs to be changed:

else if(topology[index] == '1')
{
    HuffNode* endbranch = create_HuffNode(topology[index+1], true);
    return NULL;
}

To this:

else if(topology[index] == '1')
{
    HuffNode* endbranch = create_HuffNode(topology[index+1], true);
    return endbranch;
}

The other issue you have is with these pairs of statements:

    HuffNode*  left = build_Tree(topology, index + 1, nodes_written + 1, sz);
    HuffNode*  right = build_Tree(topology, index + 1, nodes_written + 1, sz);

Because you are passing in identical parameters to build_Tree, your left and right nodes will be identical. You need your left tree parse to return something (out parameter) to indicate how many nodes it parsed so that you can pass the correct starting index into the second call to build_Tree.

Upvotes: 1

Related Questions