Skip to content

Instantly share code, notes, and snippets.

@ashwath10110
Last active November 5, 2015 18:42
Show Gist options
  • Save ashwath10110/a0364331b0f9960e5dc3 to your computer and use it in GitHub Desktop.
Save ashwath10110/a0364331b0f9960e5dc3 to your computer and use it in GitHub Desktop.
Simple Trie Datastructure in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Programming.Data_Structures.Trie
{
public static class TrieExtension
{
public static int AlphabetSize = 26;
public static int CharToInt(char x)
{
return ((int)x - (int)'a');
}
public static char IntToChar()
{
return ' ';
}
}
public class Trie
{
public class TrieNode
{
public int Value { get; set; }
public TrieNode[] Children { get; set; }
public int Prefixes { get; set; }
public bool Words { get; set; }
public TrieNode(int value = 0)
{
this.Value = value;
this.Prefixes = 0;
this.Words = false;
Children = new TrieNode[26];
for (int i = 0; i < TrieExtension.AlphabetSize; i++)
{
Children[i] = null;
}
}
}
public TrieNode Root { get; set; }
public Trie()
{
Root = new TrieNode();
}
public void Insert(string input)
{
if (Root == null)
Root = new TrieNode();
int length = input.Length;
int index;
TrieNode temp = Root;
for (int level = 0; level < length; level++)
{
index = TrieExtension.CharToInt(input[level]);
if (temp.Children[index] == null)
{
temp.Children[index] = new TrieNode(input[level]);
}
temp.Prefixes++;
temp = temp.Children[index];
}
temp.Words = true;
return;
}
public bool Search(string input)
{
int length = input.Length;
int index;
TrieNode temp = Root;
for (int level = 0; level < length; level++)
{
index = TrieExtension.CharToInt(input[level]);
if (temp.Children[index] == null)
{
return false;
}
temp = temp.Children[index];
}
if (temp.Words == true)
return true;
else
return false;
}
public int prefixes(String input)
{
int length = input.Length;
int index;
TrieNode temp = Root;
for (int level = 0; level < length; level++)
{
index = TrieExtension.CharToInt(input[level]);
if (temp.Children[index] == null)
{
return -1;
}
temp = temp.Children[index];
}
return temp.Prefixes;
}
public void Alphabetize(TrieNode node, string cprefix = "")
{
if (node.Words)
{
Console.WriteLine(cprefix);
}
for (int i = 0; i < 26; ++i)
{
if (node.Children[i] != null)
{
string currentstring = cprefix + (char)node.Children[i].Value;
Alphabetize(node.Children[i], currentstring);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment