The result of decoding the tree constructed using the first write-up is correct, but the tree constructed using the second write-up is decoded incorrectly, why? I thought they were equivalent but they are not, and I can't figure out the problem within the second version :( To make things clear, here is the correct diagram of the tree I want to construct: Graph of the tree

Tree* buildTree() {
    Tree* root, * curr;
    root = getNode('0');//set irrelevant node value to be '0'
    curr = root->left = getNode('0');
    curr->left = getNode('b');
    curr->right = getNode('g');
    curr = root->right = getNode('0');
    curr->right = getNode('e');
    curr = curr->left = getNode('0');
    curr->right = getNode('0');
    curr->right->left = getNode('a');
    curr->right->right = getNode('h');
    curr = curr->left = getNode('0');
    curr->right = getNode('d');
    curr = curr->left = getNode('0');
    curr->left = getNode('c');
    curr->right = getNode('f');
    return root;

}

And here the second version(the wrong one)

Tree* buildTree() {
    Tree* root, * curr;
    root = getNode('0');//不是解码关键节点的点，值都设为‘0’,*100
    root->left =root->right = getNode('0');
    root->left->left = getNode('b');//19
    root->left->right = getNode('g');//21
    root->right->right = getNode('e');
    curr = root->right->left = getNode('0');
    curr->left = curr->right = getNode('0');
    curr->right->left = getNode('a');
    curr->right->right = getNode('h');
    curr = curr->left = getNode('0');
    curr->left = getNode('0');
    curr->right = getNode('d');
    curr->left->left = getNode('c');
    curr->left->right = getNode('f');
    return root;

}

I tried comparing the two write-ups one-to-one with the tree illustration and didn't find any difference, but it turns out that they construct different results for decoding the tree.

The result of decoding the tree constructed using the first write-up is correct, but the tree constructed using the second write-up is decoded incorrectly, why? I thought they were equivalent but they are not, and I can't figure out the problem within the second version :( To make things clear, here is the correct diagram of the tree I want to construct: Graph of the tree

Tree* buildTree() {
    Tree* root, * curr;
    root = getNode('0');//set irrelevant node value to be '0'
    curr = root->left = getNode('0');
    curr->left = getNode('b');
    curr->right = getNode('g');
    curr = root->right = getNode('0');
    curr->right = getNode('e');
    curr = curr->left = getNode('0');
    curr->right = getNode('0');
    curr->right->left = getNode('a');
    curr->right->right = getNode('h');
    curr = curr->left = getNode('0');
    curr->right = getNode('d');
    curr = curr->left = getNode('0');
    curr->left = getNode('c');
    curr->right = getNode('f');
    return root;

}

And here the second version(the wrong one)

Tree* buildTree() {
    Tree* root, * curr;
    root = getNode('0');//不是解码关键节点的点，值都设为‘0’,*100
    root->left =root->right = getNode('0');
    root->left->left = getNode('b');//19
    root->left->right = getNode('g');//21
    root->right->right = getNode('e');
    curr = root->right->left = getNode('0');
    curr->left = curr->right = getNode('0');
    curr->right->left = getNode('a');
    curr->right->right = getNode('h');
    curr = curr->left = getNode('0');
    curr->left = getNode('0');
    curr->right = getNode('d');
    curr->left->left = getNode('c');
    curr->left->right = getNode('f');
    return root;

}

I tried comparing the two write-ups one-to-one with the tree illustration and didn't find any difference, but it turns out that they construct different results for decoding the tree.

• c
• huffman-tree

Share Improve this question Follow edited Nov 20, 2024 at 12:10 lylybay asked Nov 20, 2024 at 11:20 lylybaylylybay 311 silver badge11 bronze badge 2

• 1 C and C++ are different languages. Please tag only the one you actually use. Also please post a minimal reproducible example. – wohlstad Commented Nov 20, 2024 at 11:21
• "didn't find any difference" You could start with using text diff tool. It will show you some lines that are not identical. Then look closer (use a debugger) on the result of the lines that are different. – Gerhardh Commented Nov 20, 2024 at 11:38

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

The problem is that when you construct the tree you reuse node when you shouldn't be. For example here:

root->left = root->right = getNode('0');

This is wrong because now left and right are the same node. And now when you set stuff on the node:

root->left->left = getNode('b');

Since root->left and root->right are the same, you also affected root->right

You might be confused by what the original code is doing here:

curr = root->left = getNode('0');

This means that curr points to the same node as root->left. Modifying curr also modify root->left.

To fix this problem, make sure you create a new node every time, e.g.

root->left = getNode('0');
root->right = getNode('0');