0

我正在尝试递归遍历一棵树并通过递归携带一个字符串。

这个想法是（对于霍夫曼编码），从根开始，如果你向左，将一个 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
4

2 回答 2

2

这里的问题是您只分配了一个唯一的字符串，并且您试图为每个元素赋予其自己的唯一编码。这是行不通的，因为到最后，它们都指的是 SAME string。

您需要使用strdup或分配一个新字符串，并在string每次要将其分配给bin_node::encoding

改变

root->encoding = string;

设置编码（根，字符串）；

在哪里

void SetEncoding(bin_node* n, char* e)
{
    char *d = malloc (strlen (e) + 1);   // Space for length plus nul
    if (d == NULL) return NULL;          // No memory
    strcpy (d,s);                        // Copy the characters
    n->encoding = d; 
}
于 2013-02-25T01:41:03.617 回答
0

strcat 具有将字符附加到字符串末尾的效果，但是从末尾删除字符的代码在哪里？请注意在下面的示例中，“1”值如何替换“0”值。您的代码并非如此；您的代码附加了“0”，然后在“0”之后附加了“1”。

// usage: encode_tree(root, string, string);
void encode_tree(bin_node *root, char *string, char *end)
{
    if(root->left==NULL && root->right==NULL)
    {
        *end = '\0';
        printf("%d got an encoding of %s\n", root->data, root->encoding);
        return;
    }

    root->encoding = string;
    *end = '0'; encode_tree(root->left, string, end + 1);
    *end = '1'; encode_tree(root->right, string, end + 1);

}

于 2013-02-25T03:03:40.567 回答