C# Рекурсия в ленивом методе

Question

проблема следующего характера - мне надо перечислить все элементы бинарного дерева поиска - написал код через рекурсию, но он работает некорректно. Метод почему-то не хочет рекурсивно заходить сам в себя и просто скипает строчку с заходом. В чём может быть проблема?

public IEnumerator<T> GetEnumerator()
        {
            if (Root == null)
                yield break;
            foreach (var node in HelpMethod(Root))
                yield return node;
        }
        private IEnumerable<T> HelpMethod(Node<T> subTree)
        {
            if (subTree.Left != null)
                HelpMethod(subTree.Left);
            yield return subTree.Value;
            if (subTree.Right != null)
                HelpMethod(subTree.Right);
        }

Answer 1

Как оказалось, всё немного запутанней - как я понял, смысл в том, что в методе GetEnumerator() мы запускаем перечисление всех элементов коллекции по Root, в самом же HelpMethod мы рекурсивно запускаем перечисление уже ДРУГИХ коллекций, элементы которых не возвращаются в нашу изначальную, поэтому необходимо сделать вот так

private IEnumerable<T> HelpMethod(Node<T> subTree)
        {
            if (subTree.Left != null)
                foreach (var value in HelpMethod(subTree.Left))
                    yield return value;
            yield return subTree.Value;
            if (subTree.Right != null)
                foreach (var value in HelpMethod(subTree.Right))
                    yield return value;
        }

Как итог, рекурсивный запуск итерации по другим коллекциям вернёт элементы в нашу первоначальную - мне почему-то напомнило SelectMany() из LINQ

Answer 2

Ради развлечения написал еще вариантов в дополнение к ответу автора.

static IEnumerable<T> EnumerateTree<T>(Node<T> tree)
{
    IEnumerable<T> GetValue()
    {
        yield return tree.Value;
    }
    IEnumerable<IEnumerable<T>> EnumerateBranch()
    {
        yield return EnumerateTree(tree.Left);
        yield return GetValue();
        yield return EnumerateTree(tree.Right);
    }
    return tree == null ? Array.Empty<T>() : EnumerateBranch().SelectMany(x => x);
}

Выдает значения 1 в 1 так же как метод автора.

Можно еще так, но этот вариант немного медленнее работает.

static IEnumerable<T> EnumerateTree<T>(Node<T> tree)
{
    return tree == null ? Array.Empty<T>() : EnumerateTree(tree.Left).Append(tree.Value).Concat(EnumerateTree(tree.Right));
}

А еще лучше вообще избавиться от рекурсии. Примерно так:

static IEnumerable<T> EnumerateTree<T>(Node<T> root)
{
    Stack<Node<T>> wayBack = new Stack<Node<T>>();
    Node<T> current = root;
    Node<T> prev = root;
    while (true)
    {
        if (current.Right != prev)
        {
            if (current.Left != null && current.Left != prev)
            {
                wayBack.Push(current);
                current = current.Left;
                continue;
            }
            yield return current.Value;
            if (current.Right != null)
            {
                wayBack.Push(current);
                current = current.Right;
                continue;
            }
        }

        if (wayBack.Count == 0)
            break;
        prev = current;
        current = wayBack.Pop();
    }
}

Мало того, что работает сильно быстрее, так еще и не падает в StackOverflow.

БЛОГ НА HUSL

C# Рекурсия в ленивом методе

Ответы (2 шт):