Search strings from a list using Radix Tree

A logic to build a Radix tree (not completely though..) to search a string from a list of strings. Ideally the radix tree should be built something like this, but the logic below constructs a node for every character in the string.



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RadixTree
{
    class Program
    {
        public class Node
        {
            public char _Character;
            public List<Node> _Children = new List<Node>();
        }

        private static List<Node> traversedNodes = new List<Node>();
        private static bool stopTraversing = false;

        private static string wordString = "";
        private static string mainString = "";
        private static string[] searchStrings = new string[] 
                                                    {   "Chicago",
                                                        "Blue",
                                                        "Antioch",
                                                        "Chiwawa",
                                                        "Clarion"
                                                    };

        static void Main(string[] args)
        {
            Node root = new Node();

            int charIndex = 0;
            foreach (string str in searchStrings)
            {
                FindAndCreateNodeInTree(root, str, ref charIndex);
                charIndex = 0;
            }

            Console.WriteLine("Start\n");
            GetUserInputAndDisplayData(root);

            Console.ReadLine();
        }

        public static void GetUserInputAndDisplayData(Node root)
        {
            string input = "A";

            while (!string.IsNullOrEmpty(input))
            {
                input = Console.ReadLine();

                if (string.IsNullOrEmpty(input))
                    break;

                Console.WriteLine("-------------------------");

                stopTraversing = false;
                traversedNodes.Clear();

                // Get the parent nodes first
                GetSearchCharacterNodes(root, input, 0);

                mainString = "";
                foreach (Node node in traversedNodes)
                {
                    mainString += node._Character;

                    // If we have reached the last node in the list.. its time to retrive all the words
                    if (node == traversedNodes[traversedNodes.Count - 1])
                    {
                        wordString = mainString;
                        FindAndPrintAllWords(node);
                    }
                }

                Console.WriteLine();
            }
        }

        private static void FindAndPrintAllWords(Node parent)
        {
            if (parent._Children.Count > 0)
            {
                foreach (Node node in parent._Children)
                {
                    wordString += node._Character;
                    FindAndPrintAllWords(node);
                    // Trace back
                    wordString = wordString.Remove(wordString.Length - 1);
                }
            }
            else
            {
                // Found and word
                Console.WriteLine(wordString);
            }
        }

        public static void GetSearchCharacterNodes(Node parent, string str, int charIndex)
        {
            foreach (Node child in parent._Children)
            {
                if (stopTraversing)
                    break;

                if (child._Character == str[charIndex])
                {
                    traversedNodes.Add(child);
                    if (charIndex < str.Length - 1)
                    {
                        charIndex++;
                        GetSearchCharacterNodes(child, str, charIndex);
                    }
                    else
                    {
                        // We have found the parent nodes
                        stopTraversing = true;
                    }
                }
            }
        }

        public static void FindAndCreateNodeInTree(Node parent, string str, ref int charIndex)
        {
            foreach (Node child in parent._Children)
            {
                if (child._Character == str[charIndex])
                {
                    charIndex++;
                    FindAndCreateNodeInTree(child, str, ref charIndex);
                    return;
                }
            }

            CreateNodeInTree(parent, str, charIndex);
        }

        public static void CreateNodeInTree(Node parent, string str, int charIndex)
        {
            for (int i = charIndex; i < str.Length; i++)
            {
                Node node = new Node();
                node._Character = str[i];

                parent._Children.Add(node);

                parent = node;
            }
        }

        public static void DisplayTreeData(Node parent)
        {
            foreach (Node child in parent._Children)
            {
                Console.WriteLine(child._Character + " : " + parent._Character);
                DisplayTreeData(child);
            }
        }

    }
}

Comments

Popular posts from this blog

Authoritative Server - MMO

Code dependencies