Click here to Skip to main content
15,867,488 members
Articles / Programming Languages / C#

Phone Directory Implementation Using TRIE

Rate me:
Please Sign up or sign in to vote.
4.88/5 (21 votes)
15 Mar 20073 min read 122.7K   4.6K   30  
Phone Directory Implementation Using TRIE data structure.
using System;
using System.Collections;
using System.Text;

namespace PhoneDirectory
{
    public class Trie
    {
        /* Gets all the childern starting from a string
           ex: returns all names starting from Jo -> John, Joe, Joseph etc*/
        public static void GetChildrenStartingFromKey(Node node, string key)
        {
           //Get the node which has the value of "Jo"
            Node curNode = GetChildNode(node, key);

            //if "Jo" found:
            if (curNode != null)
            {
                //get the children of "Jo" -> John, Joe, Joseph etc
                IEnumerator iterator = curNode.GetDepthNodes();

                while (iterator.MoveNext())
                {
                    //get child
                    Node childNode = (Node)iterator.Current;
                    
                    //Does child have a valid full name
                    if (childNode.IsTerminal)
                        Console.WriteLine(childNode.Value);
                }
            }

        }

        //Locates a node based on the key; eg. Locates "Jo" node on the tree
        public static Node GetChildNode(Node node, string key)
        {
            //Is key empty
            if (string.IsNullOrEmpty(key))
                return node;//terminal Node?

            //get the first character
            string first = key.Substring(0, 1);
            
            //get the tail: key - first character
            string tail = key.Substring(1);

            //current node
            Node curNode = node.Children.GetNodeByKey(first);

            //loop until you locate the key i.e. "Jo"
            if (curNode != null)
            {
                return GetChildNode(curNode, tail);
            }
            else
            {
                //not found, return null
                return null;
            }
        }

        //Find a node given the key("Jo")
        public static bool Find(Node node, string key)
        {
            //Is key empty
            if (string.IsNullOrEmpty(key))
                return true;//terminal Node

            //get the first character
            string first = key.Substring(0, 1);

            //get the tail: key - first character
            string tail = key.Substring(1);

            Node curNode = node.Children.GetNodeByKey(first);

            //loop until you locate the key i.e. "Jo"
            if (curNode != null)
            {
                return Find(curNode, tail);
            }
            else
            {
                //not found, return false
                return false;
            }
        }

        //Inserts Names into the Trie data structure
        public static Node InsertNode(string name, Node root)
        {
            //Is name null?
            if (string.IsNullOrEmpty(name))
                throw new ArgumentNullException("Null Key");

            //set the index, start inserting characters
            int index = 1;
            
            //key
            string key;

            //start with the root node
            Node currentNode = root;

            //loop for all charecters in the name
            while (index <= name.Length)
            {
                //get the key character
                key = name[index - 1].ToString(); 

                //does the node with same key already exist?
                Node resultNode = currentNode.Children.GetNodeByKey(key);

                //No, this is a new key
                if (resultNode == null)
                {
                    //Add a node
                    Node newNode = new Node(key, name.Substring(0, index));
                    
                    //If reached the last charaecter, this is a valid full name
                    if (index == name.Length)
                        newNode.IsTerminal = true;
                    
                    //add the node to currentNode(i.e. Root node for the first time)
                    currentNode.Children.Add(newNode);

                    //set as the current node
                    currentNode = newNode;
                }
                else
                {
                    //node already exist, set as tghe current node
                    //and move to the next character in the name
                    currentNode = resultNode;
                }

                //move to the next character in the name
                index++;
            }

            //all done, return root node
            return root;
        }
       
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions