recursion - 打印 trie 树的单词

Question

我试图用 C 打印 trie 的内容。但是我不是很成功。让我一开始就说，这是我们现在在学校正在做的事情，这是一个练习。

这就是我的特里树的样子:

struct node{
    char letter; //holds the letter associated with that node
    int count; //its count
    struct node* child[26]; //each node can have 26 children
};

struct trie{
    struct node* root;
};

此打印方法必须遍历此 trie 并按字母顺序打印单词，并且不应打印计数为 0 的单词。

我正在考虑递归，这就是我的代码:

void print(node* root) {
    char buffer[15];//array to store the letters
    if(root==NULL){ return;}//if the root is null return
    int i;
    int index=0; //index for the buffer
    int hasAChild=hasChild(root);

    if (hasAChild != 0) { //the root has children keep on going
        for (i=0;i<27;i++) {
            //go thru all the children and if they have children call print                         recursively
            if (hasChild(root->child[i])) {
                print(root->child[i]);
            }
            else {
                // if they have no more children add the letter to the buffer
                buffer[index++] = root->child[i]->letter;
            }
            // print the contents in the bufffer
            printf("%s: %d",root->child[i]->count);
        }
    }
}

// function to determine if a node has children, if so it returns their number if not,returns 0

int hasChild(root) {
    if(root==NULL){
        return 0;
    }

    int i;
    int count=0;
    for(i=0;i<27;i++){
        if(root->child[i]!=NULL){
            count++;
        }
    }
    return count;
}

这就是它的样子

特里树的示例:

Root
  +--- a:2
  |     +--- t:4
  |
  +--- b:3
  |     +--- e:5
  |
  +--- c:0

我们有 'a' 2 次、'at' 4 次、'b' 3 次和 'be' 5 次，只应该打印单词。在这个例子中我将不得不打印于:4为:5但不是 c: 0，因为它的计数为 0

所以我只想打印形成的单词，而不打印不形成单词的字母。任何帮助或指导将不胜感激。谢谢!

Answer 1

我在这里看到三个问题:

• 仅当当前节点没有子节点时，才将字母附加到当前缓冲区。这意味着您将只显示单词的最后一个字母。

• 此外，每次进入该函数时，都会从一个空缓冲区开始。

• 您的 printf 语句缺少字符串参数。

您需要传递长度和缓冲区，并确保正确地以空值终止。