c - 用字符串递归遍历树

Question

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

这个想法是(对于哈夫曼编码)，从根开始，如果向左走，则将 0 连接到字符串，如果向右走，则连接 1。当您到达叶子时，最终的字符串是由 0 和 1 组成的字符串，即您的“编码”。

这是我的功能:

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

Answer 1

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

您需要使用strdup或者分配一个新字符串并从 string 复制过来每次你想将它分配给 bin_node::encoding

改变

root->encoding = string;

至 SetEncoding(根, 字符串);

哪里

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; 
}