层树打印所有后缀提供错误的输出

Question

我需要打印轮胎树的所有后缀。我正在使用以下遍历方法打印所有后缀。

struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    char label;
    bool isLeaf;
};

void traverse(char prefix[], struct TrieNode *root) {
    concatenate_string(prefix, &(root->label));
    if (root->isLeaf) {
        printf("%s\n", prefix);
    }

    for (int i = 0; i < 26; i++) {
        if (root->children[i]) {
            traverse(prefix, root->children[i]);
        }
    }
}

考虑跟随 Trie 树

    Root
 |     |    |
 L     M    N
|  |
a  b

所以我的预期输出是

La
Lb
M
N

但是我的代码打印出来了

  La
  Lab
  LabM
  LabMN

据我了解，问题的根本原因是没有正确更新前缀变量。如何解决这个问题？

Answer 1

那是因为你一直在串联。最好将 char prefix[] 作为局部变量，例如：

void traverse(char prefix[], struct TrieNode *root)
{
    char newprefix[30];
    strcpy(newprefix, prefix);
    concatenate_string(newprefix, &(root->label));
    if (root->isLeaf) {
        printf("%s\n",newprefix);
    }

    for(int i=0 ; i< 26 ; i++){
        if(root->children[i]){
            traverse(newprefix, root->children[i]);
        }
    }
}

并像这样打电话：

traverse("", root);

层树打印所有后缀提供错误的输出

Tiers tree print all suffixed provied wrong output

c

algorithm

trie