c - 在 c 中按字典顺序打印 trie

Question

所以我正在实现一个 trie 以将单词存储在字典文件中。我已经实现了插入操作；现在我正在尝试按字典顺序打印。我快要搞定了，但我有一个小问题，我不确定如何解决。我还试图记住我的程序的速度，这就是我选择 trie 而不是数组或链表的原因。 这是单个节点的样子:

struct node {
  int end;
  int occurrences;
  int superwords;
  struct node* child[26];
};

“end”表示一个单词的完成(例如，end == 1 at the letter 'k' in the word book；这可以防止在检查单词是否实际插入到树中时出现混淆)。

方法如下:

void preorder(struct node *follow, char hold[200], int s){
  int i = 0;
  if(follow == NULL){
    return;
  }

  for(i = 0; i < 26; i++){
    if(follow->child[i] == NULL){
      continue;
    }
    else{
      printf("%c",'a'+i);
      hold[s] = 'a'+i;
      s++;
      if(follow->child[i]->end == 1){
        printf("\n");
        hold[s] = '\0';
        printf("%s", hold);
      }
      preorder(follow->child[i], hold, s);
    }
  }
  return;
}

我插入的词是:boo、book、booking、john、tex、text。它们应按该顺序打印并分开行。我的输出如下:

boo
book
booking
bookingjohn
bjohntex
bjtext
bjtext

我知道这可能与我的“hold”数组有关，它存储单词的前缀，这样它们就不会丢失。我需要在某处将索引设置回零以指示前缀及其所有关联词的完成(boo、book、booking 是一个很好的例子)但没有成功。任何帮助将不胜感激，我很乐意进一步阐明我的思考过程。

Answer 1

你非常接近。

有两个问题，都在遍历 trie 分支的 for 循环中:

else{
  printf("%c",'a'+i);
  hold[s] = 'a'+i;
  s++;

第一个问题是您(几乎)将所有内容打印两次。在上面的代码片段中，您在跟踪树时打印前缀。然后当你到达单词的末尾时，打印整个单词:

  if(follow->child[i]->end == 1){
    printf("\n");
    hold[s] = '\0';
    printf("%s", hold);
  }

所以根本不需要打印前缀，而且双重打印很困惑。

其次，s参数表示树中的深度，也就是当前前缀的长度。因此在探索一个 trie 节点期间它应该是恒定的。但每次找到新分支时，都会增加它(上面第一个代码段中的 s++)。而不是这样做，您需要递归调用以使用 s + 1 作为其参数，以便使用正确的前缀长度调用它。

您还可以大大简化您的控制结构。

这是一个例子:

void preorder(struct node *follow, char hold[200], int s){
  int i = 0;
  if(follow == NULL){
    return;
  }
  /* Print the word at the beginning instead of the end */
  if (follow->end) {
    hold[s] = 0;
    printf("%s\n", hold);
  }

  for(i = 0; i < 26; i++){
    /* preorder returns immediately if its argument is NULL, so
     * there's no need to check twice. Perhaps even better would be
     * to do the check here, and not do it at the beginning.
     */
    hold[s] = 'a'+i;
    preorder(follow->child[i], hold, s + 1);
  }
}