使用yield返回元素的树形递归顺序

Question

我有一个递归函数，它返回给定起始根节点的所有子树节点。

private IEnumerable<Node> getAllNodesRecursively(Node subnode)
{
    foreach (Node node in subnode.Nodes)
        getAllNodesRecursively(node);

    yield return subnode;
}

对于以下的树形结构：

A
|
+--B
|
+--C
|  |
|  +--D
|
+--E

我尝试按如下方式进行迭代：

foreach (Node n in getAllNodesRecursively(a))
{
    Console.WriteLine(n);
}

该函数仅返回A值。

我希望在递归中使用yield-return，并检索Preorder（例如，在此示例中为A、B、C、D、E）中的元素。

（如果在foreach之前放置yield return，则foreach将永远不会发生。）

这是可能的吗？

- Kornelije Petak

---

你试过把yield return放在前面，foreach就不会被调用吗？我猜它还是会被调用的。 - okrumnow

是的，你说得对。Yield return不会跳过代码的其余部分。它似乎只是一种语法糖，允许值返回并仍然保持函数运行。我的错。 - Kornelije Petak

Answer 1

你尝试过类似这样的方法吗：

private IEnumerable<Node> getAllNodesRecursively(Node subnode) 
{ 
    // Return the parent before its children
    yield return subnode; 

    foreach (Node node in subnode.Nodes) 
    {
        foreach(Node n in getAllNodesRecursively(node))
        {
            yield return n;
        }
    }
} 

你的实现正在递归调用 getAllNodesRecursively，但忽略了该函数的返回值。

- Joe

---

这个可以运行，但为什么我还需要再次迭代（内部foreach）？为什么迭代器方法不允许递归呢？我已经尝试使用调试器，它会跳过我的递归调用，除非它在迭代中使用（如foreach）。为什么会这样呢？ - Kornelije Petak

@ChristianHayter "那不会返回除顶级节点之外的所有节点两次吗？" 不会。 - Joe

Joe的例子可以稍微简化一下：private IEnumerable<Node> getAllNodesRecursively(Node root) { yield return root; foreach (var child in root.Nodes.SelectMany(getAllNodesRecursively)) { yield return child; } } - peter70

Answer 2

您需要显式迭代每个节点的子节点，并使用yield return返回结果，如下所示：

        public IEnumerable<int> preOrder(Node root)
        {
            if (root == null)
                yield break;

            yield return root.val;

            if (root.left != null)
                foreach (int i in preOrder(root.left))
                    yield return i;

            if (root.right != null)
                foreach (int i in preOrder(root.right))
                    yield return i;
        }

- Lee.O.

---

虽然这段代码片段可能解决了问题，但是包括解释真的有助于提高您的帖子质量。请记住，您正在为未来的读者回答问题，而这些人可能不知道您的代码建议的原因。 - lokusking

Answer 3

是的，这是可能的，只需在 foreach 前面放置 yield return。您正在考虑普通 return 语句的行为。

- Christian Hayter

---

我修改了我的帖子，因为我在显示内容上错了。只有第一个元素被返回。如果我在foreach之前放置yield return，同样的事情会发生。这是怎么回事？ - Kornelije Petak

嗯，我现在没有尝试这个的条件。你用调试器逐步执行代码了吗？ - Christian Hayter

调试器简单地跳过了递归调用。这是一个有趣的问题。 - Kornelije Petak