主页 / 问题 / 1412293
Accepted
Iceneo
Asked:2022-07-21 20:21:46 +0800 CST2022-07-21 20:21:46 +0800 CST

惰性方法中的 C# 递归

  • 772

问题如下 - 我需要列出二叉搜索树的所有元素 - 我通过递归编写代码，但它不能正常工作。出于某种原因，该方法不想递归地输入自己，而只是跳过带有条目的行。可能是什么问题呢？

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);
        }
c# рекурсия

2 个回答

  1. Best Answer

    为了好玩，除了作者的回答，我还写了更多的选项。

    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 上也不会崩溃。

    • 3

  2. 事实证明，一切都更加混乱 - 据我了解，关键是在 GetEnumerator () 方法中，我们开始通过 Root 枚举集合的所有元素，在 HelpMethod 本身中，我们递归地开始枚举 OTHER 集合，其中的元素没有返回到我们原来的，所以你需要这样做

    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;
        }

    结果，递归迭代其他集合会将元素返回到我们原来的元素——出于某种原因，它让我想起了 LINQ 中的 SelectMany ()

    • 1

相关问题