在 c 中按字典顺序打印 trie

Question

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

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

"end"表示一个词的补全（例如词本中字母'k'处的end==1，这样可以防止在检查是否实际插入了一个词时出现混淆在树上）。

方法如下：

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] = '[=11=]';
        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] = '[=11=]';
    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);
  }
}

在 c 中按字典顺序打印 trie

Printing a trie lexicographically in c

c

sorting

trie

lexicographic

preorder