Добавление нескольких уникальных дочерних элементов на нескольких уровнях с одним или несколькими циклами и «чистым» кодом

Я новичок в C# и в данный момент пытаюсь бросить себе вызов с разными задачами.

На данный момент я пытаюсь создать веб-приложение, в котором вы можете вводить буквы и подстановочные знаки для поиска возможных слов.

Из предыдущих вопросов по этому поводу я решил создать Trie, содержащее буквы, сгенерированные из более чем 400 тысяч слов. Позже я буду искать в Trie возможные совпадения слов в зависимости от ввода букв и подстановочных знаков.

Я создал два класса, один из которых представляет один узел в Trie, а другой представляет все Trie.

В настоящее время я нахожусь в тупике, моя проблема в том, что я хочу добавить несколько дочерних элементов в Trie на нескольких уровнях, и каждый дочерний элемент должен быть уникальным.

Выполнение этого вручную будет выглядеть примерно так:

//Level 1
Root.Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
//Level 2
Root.Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
//Level 3
Root.Children[0].Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));

Проблема в том, что я хочу добавить детей с одним или несколькими циклами, и делать это таким образом кажется немного «неправильным»:

LetterArray = Word.ToCharArray();
int level = 0;
foreach (char Letter in LetterArray)
{
    //Level 1
    if (level == 0)
        Root.Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
    //Level 2
    if (level == 1)    
        Root.Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
    //Level 3
    if (level == 2)
        Root.Children[0].Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));

    level++;
}

Что мне нужно, так это один или несколько циклов с «чистым» кодом, думаете, вы можете мне помочь? Я думаю, что для того, чтобы Trie был доступен для поиска позже, буквы должны идти по порядку. Вот мои другие вопросы, связанные с этим: Вопрос 1, Вопрос 2.

Вот мой класс TrieNode:

public class TrieNode
{
    private char _Letter;
    private bool _IsEndOfWord;
    private List<TrieNode> _Children;

    public char Letter {
        get { return _Letter; }
        set { _Letter = value; }
    }
    public bool IsEndOfWord {
        get { return _IsEndOfWord; }
        set { _IsEndOfWord = value; }
    }
    public List<TrieNode> Children {
        get { return _Children; }
        set { _Children = value; }
    }

    public TrieNode(char letter, bool isEndOfWord, List<TrieNode> children) {
        Letter = letter;
        IsEndOfWord = isEndOfWord;
        Children = children;
    }
}

… и вот мой класс Trie:

public class Trie
{
    private TrieNode _Root;

    public TrieNode Root
    {
        get { return _Root; }
        set { _Root = value; }
    }

    public Trie(List<string> Words)
    {
        Root = new TrieNode('^', false, new List<TrieNode>());
        char[] LetterArray;

        foreach (String Word in Words)
        {
            LetterArray = Word.ToCharArray();

            foreach (char Letter in LetterArray)
            {
                // Here is where I want to add nodes to my Trie
            }
        }
    }
}

loops c# children trie
person Linus Jäderlund    schedule 19.09.2011    source источник
comment
Кстати, поскольку у вас нет другой логики использования резервных значений, я предлагаю вам использовать короткую версию: public char Letter { get; set; }, public bool IsEndOfWord { get; set; }, public List<TrieNode> Children { get; set; }.   -  person ANeves thinks SE is evil    schedule 19.09.2011
comment
@ANeves О, понятно, большое спасибо за этот вклад: D   -  person Linus Jäderlund    schedule 19.09.2011

Ответы (2)


arrow_upward
1
arrow_downward

Я бы также выполнил это с помощью рекурсии, однако мой рекурсивный метод был бы внутри класса TrieNode:

public AddWord(string word)
{
    if (String.IsNullOrEmpty(word))
    {
        throw new ArgumentException("word must contain values.", word);
    }

    var letter = word[0];
    var child = Children.FirstOrDefault(x => x.Letter = letter);

    if (child == null)
    {
        //The child doesn't exist.  Create it.
        child = new TrieNode(letter, false, new List<TrieNode>());
    }

    if (word.Length > 1)
    {
        child.AddWord(word.Substring(1);
    }
    else
    {
        child.IsEndOfWord = true;
    }
}

Наконец, вам просто нужно изменить свой начальный цикл в конструкторе Trie:

foreach (String Word in Words)
{
    _Root.AddWord(Word);
}

(примечание: я не тестировал этот код, поэтому могут быть опечатки).

person rie819    schedule 19.09.2011

arrow_upward
2
arrow_downward

Вы ищете рекурсию?
http://en.wikipedia.org/wiki/Recursion_%28computer_science%29

using System.Linq;

public Trie(List<string> words)
{
    Root = new TrieNode('^', false, new List<TrieNode>());
    // Might have gotten the wrong method, check with intellisense
    char[] letters = words.SelectMany( word => word.ToCharArray());
    RecursiveAdd(letters, Root, 0);
}

private const int desiredDepth = 5;
private void RecursiveAdd(char[] letters, TrieNode branch, currentDepth)
{
    foreach(char letter in letters) {
        TrieNode node = new TrieNode(Letter, false, new List<TrieNode>());
        branch.Children.Add(node);
        if( currentDepth < desiredDepth ) {
            RecursiveAdd(letters, node, currentDepth+1);
        }
    }
}

Я надеюсь, что это поможет, и извините, если я сделал слишком много работы для вас.
Лучший способ учиться это делать, я согласен.

person ANeves thinks SE is evil    schedule 19.09.2011