我正在尝试递归遍历一棵树并通过递归携带一个字符串。
这个想法是(对于霍夫曼编码),从根开始,如果你向左,将一个 0 连接到你的字符串,如果你向右,连接一个 1。当你到达叶子时,你的最终字符串是一个 0 的字符串和 1s 那是你的“编码”。
这是我的功能:
void encode_tree(bin_node *root, char *string)
{
if(root->left==NULL && root->right==NULL)
{
root->encoding = string;
printf("%d got an encoding of %s\n", root->data, root->encoding);
return;
}
root->encoding = string;
encode_tree(root->left, strcat(string, "0"));
encode_tree(root->right, strcat(string, "1"));
}
但是这段代码是错误的,它给了我不正确的编码。
假设我有这棵树:
3\65
6\-1
3\70
9\-1
2\66
3\-1
1\67
16\-1
7\68
我对 7/86 的编码应该是 0,1/67 应该是 100,2/66 应该是 101,3/70 应该是 110,3/65 应该是 111。
但这是我从函数中获得的编码:
7/68 got an encoding of 0
1/67 got an encoding of 0100
2/66 got an encoding of 01001
3/70 got an encoding of 0100110
3/65 got an encoding of 01001101