Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Phone Directory Implementation Using TRIE

, 15 Mar 2007
Phone Directory Implementation Using TRIE data structure.
article_demozip.zip
Program
bin
Debug
Program.exe
Program.pdb
Program.vshost.exe
Trie.dll
Trie.pdb
obj
Debug
Program.exe
Program.pdb
ResolveAssemblyReference.cache
TempPE
Program.csproj.user
Properties
article_srczip.zip
Trie
bin
Debug
Trie.dll
Trie.pdb
obj
Debug
TempPE
Trie.dll
Trie.pdb
Properties
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

Share

About the Author

Madhu Rajagopalan

United States United States
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.1411023.1 | Last Updated 15 Mar 2007
Article Copyright 2007 by Madhu Rajagopalan
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid