c++ - 使用 trie 打印字典中的所有单词

Question

我正在使用 c 中具有以下结构的 trie 来编写字典

  struct trie_node {
    int is_end;   //0 is is not the end of the word ,otherwise 1
    char c;       
    struct trie_node* child[26];
  };

我可以插入单词，搜索单词，我想打印字典中的所有单词。不确定如何处理。我正在尝试打印

void print(struct trie_node node) {
int i = 0;
 for (i = 0; i < 26; i++) {
    if (node->child[i] != NULL) {
       printf("%c", node->child[i]->c);
       print(node->child[i]);
    }
 }

但是打印不正确例如，如果我有的话啤酒蜜蜂熊野兽

正在打印熊熊它应该打印熊兽啤酒

如何正确打印单词列表？

Answer 1

您需要跟踪路径(从根到当前节点的路径)。当您到达结束节点(is_end 为真)时，您将打印字典单词的路径。

一种方法是使用 char 数组并跟踪其长度，这样您就知道需要打印多少个元素。请看下面的代码:

void print_path (char *path, int len){
  int i;
  for(i = 0; i < len; i++)
    printf("%c", path[i]);
}
void print(struct trie_node* node, char *path, int len) {
  // sanity check
  if (! node)
    return;

  // current node is part of the current path, so add it
  path[len++] = node->c;

  // if it is an end node then print the path
  if (node->is_end)
    print_path(path, len);  

  // now go through the children and recursive call 
  int i = 0;
  for (i = 0; i < 26; i++) {
    if (node->child[i] != NULL) {
      print(node->child[i], path, len);                     
    }
  }
}

int main(){
  // proper allocation for the trie
  // ...
  // calling the print, assuming the height of tree is at most 128
  char path[128];
  print(b, path, 0);
}