使用Trie打印所有字典的单词

Question

我正在使用与C

中的以下结构一起在词典上工作

  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]);
    }
 }

}

但是它无法正确打印例如，我有单词啤酒蜜蜂熊野兽

它正在打印熊手它应该打印BearbeastBeebeer

如何正确打印单词列表？

Answer 1

您需要跟踪路径（从根到当前节点的路径）。当您到达末端节点（IS_END为true）时，您会打印路径是字典单词。

一种方法是使用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);
}

Answer 2

您可以尝试使用node.child [i] -> c，当使用struct var时，必须使用"。"。（＆amp; point）。"，我不知道我的认为是真的：）