在 C 的 trie 中打印单词

Question

填充 trie 没问题。单词不包含数字或空格，只包含小写字母。

printTrieContents 使用在 main 中分配的缓冲区。

问题：如果 trie 包含单词 "scores" 和 "something"，将打印 "scores" 但不会打印 "something"。

其他都还好

struct trieNode {
  int count;
  struct trieNode *children[ALPHA_SIZE];
};


void printTrieContents(struct trieNode *root, char *buffer, int buffIndex){
        int i;
        for(i = 0; i < ALPHA_SIZE; i++){
                if(root->children[i] != NULL){
                        buffer[buffIndex] = i + 'a';
                        printTrieContents(root->children[i], buffer, buffIndex + 1);
                }
                if(!hasChildren(root)){
                        buffer[buffIndex] = '[=10=]';
                        if(strlen(buffer) > 0){
                                printf("%s: %d\n", buffer, root->count);
                                buffIndex = 0;
                        }
                }   
        }
}

int hasChildren(struct trieNode *root){
        int i;
        for(i = 0; i < ALPHA_SIZE; i++){
                if(root->children[i] != NULL){
                        return 1;
                }
        }
return 0;
}

Answer 1

你最终遍历到了一片叶子。此时，作为一片叶子，你没有children。您添加 null 并将 buffIndex 设置为零 。但是你没有退出，你继续旋转，这意味着你将回到那个子句并将缓冲区 [0] 设置为 Null，有效地清除你的字符串，你最终会递归并继续下一个 child.

edit: 当你检测到需要附加null时，而不是设置buffIndex（注意，buffIndex是当前帧局部的，设置它不会有任何影响其余的调用堆栈）return。您将开始递归备份您的堆栈。然后你会回到一个有更多 children 的帧，你可以开始迭代其他 children，用它们的新字符串覆盖缓冲区，并打印新词。

在 C 的 trie 中打印单词

Printing words in a trie in C

c

traversal

trie