Question Problem with prefix tree (trie) search

Serilla

New member
Joined
Oct 15, 2019
Messages
1
Programming Experience
Beginner
Hey,

I am working on a project in which I need to build a prefix tree (trie). Searching in the trie should return a list of words matching a given search prefix.

That's the code I have so far, but the search doesnt actually return the value I'm looking for and instead returns "Trees.PrefixTree+<FindAllWordsRecursive>d__5". What am I doing wrong or what do I have to change to get it run?

Thank you very much in advance!

C#:
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Threading;



namespace Trees
{
   
    public class Program
    {
        public static void Main()
        {
           
            //String[] file = File.ReadAllLines(@"C:\Users\samue\Desktop\Neuer Ordner (2)\liste.txt");
       
            string[] dictionary = new string[] { "test", "try", "angle", "the", "code", "is", "isnt" };
            PrefixTree trie = new PrefixTree();

            var sw = new Stopwatch();
            foreach (var word in dictionary)
            {
                trie.Add(word);
            }

            //Thread workerThread = new Thread(trie.Search(suchwort);

            Console.WriteLine(trie.Search("te"));

        }
    }
   
    public class PrefixTree
    {
        private PrefixTreeNode root;

        public PrefixTree()
        {
            root = new PrefixTreeNode(String.Empty);
        }

        public void Add(string word)
        {
            AddRecursive(root, word, String.Empty);
        }

        private void AddRecursive(PrefixTreeNode node, string remainingString, string currentString)
        {
            if (remainingString.Length <= 0)
            {
                return;
            }

            char prefix = remainingString[0];
            string substring = remainingString.Substring(1);
            if (!node.SubNodes.ContainsKey(prefix))
            {
                node.SubNodes.Add(prefix, new PrefixTreeNode(currentString + prefix));
            }

            if (substring.Length == 0)
            {
                node.SubNodes[prefix].IsWord = true;
                return;
            }
            else
            {
                AddRecursive(node.SubNodes[prefix], substring, currentString + prefix);
            }
        }
       

        public IEnumerable<string> Search(string searchString)
        {
            PrefixTreeNode node = root;
            foreach (var search in searchString)
            {
                if (!node.SubNodes.ContainsKey(search))
                {
                    return new string[0];
                }
                node = node.SubNodes[search];
            }

            return FindAllWordsRecursive(node);
        }

        private IEnumerable<string> FindAllWordsRecursive(PrefixTreeNode node)
        {
            if (node.IsWord)
            {
                yield return node.Word;
            }

            foreach (var subnode in node.SubNodes)
            {
                foreach (var result in FindAllWordsRecursive(subnode.Value))
                {
                    yield return result;
                }
            }
        }

        protected class PrefixTreeNode
        {
            private readonly Dictionary<char, PrefixTreeNode> subNodes;
            private bool isWord;
            private readonly string word;

            public PrefixTreeNode(string word)
            {
                subNodes = new Dictionary<char, PrefixTreeNode>();
                isWord = false;
                this.word = word;
            }

            public Dictionary<char, PrefixTreeNode> SubNodes { get { return subNodes; } }
            public bool IsWord { get { return isWord; } set { isWord = value; } }
            public string Word { get { return word; } }
        }
    }
   
}
 
Last edited:
That means that you are getting the value of calling ToString on an object of that type. It means that you are treating an object as though it was the String you wanted rather than getting the String you want from it, e.g. from a property. You need to debug your code properly, i.e. by setting breakpoints and stepping through the code, examining the state at each step. Before each step, ask yourself exactly what you expect to happen. After the step, check whether it actually did happen. The moment you find a difference between expectations and reality, you've found an issue. Even if you can't then resolve it yourself, at least you can give us all the relevant information.
 
The other part of the problem is that you declared:
C#:
public IEnumerable<string> Search(string searchString)
but are trying to get the output as:
C#:
Console.WriteLine(trie.Search("te"));

The WriteLine() will not automatically go through all the items of an enumerable.
 
Cross-posted here Trie implementation: Search method with weird return value
Use one of these if you need to evaluate values from IEnumerable<T> :
C#:
            IEnumerable<string> Values = new List<string> { "food", "drink", "foo" };
            /* #1 */
            var enumerat = Values.GetEnumerator();
            while (enumerat.MoveNext())
            {
                if (enumerat.Current == "foo")
                    Debug.WriteLine(enumerat.Current);
            }
            /* #2 */
            Values.ToList().ForEach(delegate (string s)
            {
                if (s == "foo")
                    Debug.WriteLine(s);
            });
            /* #3 */
            foreach (string s in Values)
            {
                if (s == "foo")
                    Debug.WriteLine(s);
            }
 
Back
Top Bottom