2

I am working on a dictionary using a trie with the following struct in 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];
  };

I am able to insert words, search words and I would like to print all the words of the dictionary. Not sure how to handle it. I was trying to print 

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

}

But it is not printing correctly if for example I have the words beer bee bear beast

it is printing bearster it should print bearbeastbeebeer

How can I print correctly the list of words ?

zancudo
  • 325
  • 1
  • 3
  • 9
  • When you recursively call `print(node->child[i]);`, you're not printing any of the characters from the ancestor nodes. So after printing `bear`, your program is then printing the `st` at the end of `beast` without repeating the first three characters. – r3mainer Feb 28 '17 at 02:49
  • 1
    Possible duplicate of [algorithm to print trie alphabetically](http://stackoverflow.com/questions/17843628/algorithm-to-print-trie-alphabetically) – r3mainer Feb 28 '17 at 03:37
  • You've not provided enough information for us to reproduce the issue you describe; try moving your *example* from *English* to *C* or *C++* (and make sure it compiles and runs, so we can reproduce the issue you describe)... The other thing is, you need to *pick a language*; either C or C++. If your code compiles with a C compiler, you can pick C. Otherwise, pick C++. – autistic Feb 28 '17 at 04:22
  • @zancudo, please look at my answer down below and let me know if you tried it out. – Arash Feb 28 '17 at 16:44

2 Answers2

2

You need to keep track of the path (path from the root to the current node). When you reach to an end node (is_end is true), you print the path which is the dictionary word.

One approach is to use an array of char and keep track of its length so you know how many of elements you need to print. See the code below:

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);
}
Arash
  • 1,950
  • 14
  • 17
  • 1
    Also, I suggest that you [stop casting `malloc` in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) or [stop using `malloc` in C++](http://stackoverflow.com/questions/184537/in-what-cases-do-i-use-malloc-vs-new), think about `sizeof (char)` (both type-wise in retrospect of `int len` and value-wise in retrospect of `malloc(128 * 1)`) and when it might be most appropriate to use automatic storage duration as opposed to dynamic allocation (`malloc`/`free`, `new`/`delete`, whatever your choice)... – autistic Feb 28 '17 at 04:31
  • It always astounds me when people cast the return value of `malloc` but not the argument of `free`; that blows the entire reasoning for casting `malloc` out of the window. So you need the cast to convert a `void *` to a `char *` in C++, but you don't need it the other way around? Hmmm... – autistic Feb 28 '17 at 04:33
  • Thanks for pointing that out (no casting needed with malloc). – Arash Feb 28 '17 at 04:46
  • 1
    At the end, I removed the malloc allocation since the allocation size is fixed. – Arash Mar 05 '17 at 02:16
  • Yes, you've chosen automatic storage duration... Good choice :) – autistic Mar 05 '17 at 04:02
0

you can try to use node.child[i]->c,when use struct var you must use a ".",when use struct point must use "->" or "(&point).",i don't know my think is true : )

threedream
  • 1
  • 1