How to create a trie in c# [closed]

Question

Does anyone know where I can find an example of how to construct a trie in C#? I'm trying to take a dictionary/list of words and create a trie with it.

Answer 1

This is my own code, pulled from my answer to How to find a word from arrays of characters? :

public class Trie {   public struct Letter   {     public const string Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";     public static implicit operator Letter(char c)     {       return new Letter() { Index = Chars.IndexOf(c) };     }     public int Index;     public char ToChar()     {       return Chars[Index];     }     public override string ToString()     {       return Chars[Index].ToString();     }   }    public class Node   {     public string Word;     public bool IsTerminal { get { return Word != null; } }     public Dictionary<Letter, Node> Edges = new Dictionary<Letter, Node>();   }    public Node Root = new Node();    public Trie(string[] words)   {     for (int w = 0; w < words.Length; w++)     {       var word = words[w];       var node = Root;       for (int len = 1; len <= word.Length; len++)       {         var letter = word[len - 1];         Node next;         if (!node.Edges.TryGetValue(letter, out next))         {           next = new Node();           if (len == word.Length)           {             next.Word = word;           }           node.Edges.Add(letter, next);         }         node = next;       }     }   } 

Answer 2

Take a look at this codeplex project:

https://github.com/gmamaladze/trienet

It is a library containing several different variants of well tested generic c# trie classes including patricia trie and parallel trie.

• Trie – the simple trie, allows only prefix search, like .Where(s => s.StartsWith(searchString))
• SuffixTrie - allows also infix search, like .Where(s => s.Contains(searchString))
• PatriciaTrie – compressed trie, more compact, a bit more efficient during look-up, but a quite slower durig build-up.
• SuffixPatriciaTrie – the same as PatriciaTrie, also enabling infix search.
• ParallelTrie – very primitively implemented parallel data structure which allows adding data and retriving results from different threads simultaneusly.