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