首页 / 知识

关于递归：在C#中遍历树的递归lambda表达式

2023-04-15 06:08:00

Recursive lambda expression to traverse a tree in C#

有人可以告诉我如何实现递归lambda表达式来遍历C#中的树结构。

好的，我终于找到了一些空闲时间。
我们开始：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class TreeNode
{
public string Value { get; set;}
public List<TreeNode> Nodes { get; set;}

public TreeNode()
{
Nodes = new List<TreeNode>();
}
}

Action<TreeNode> traverse = null;

traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};

var root = new TreeNode { Value ="Root" };
root.Nodes.Add(new TreeNode { Value ="ChildA"} );
root.Nodes[0].Nodes.Add(new TreeNode { Value ="ChildA1" });
root.Nodes[0].Nodes.Add(new TreeNode { Value ="ChildA2" });
root.Nodes.Add(new TreeNode { Value ="ChildB"} );
root.Nodes[1].Nodes.Add(new TreeNode { Value ="ChildB1" });
root.Nodes[1].Nodes.Add(new TreeNode { Value ="ChildB2" });

traverse(root);

使用定点组合器是一个合适的解决方案，甚至是许多功能编程语言中惯用的解决方案。简而言之：定点组合器回答了以下问题："我如何将匿名函数定义为递归？"。但是解决方案是如此简单，以致于撰写整篇文章来解释它们。

一个简单，实用的选择是在定义之前"回到过去" C：声明的滑稽动作。尝试以下操作("阶乘"功能)：

1 2	Func<int, int> fact = null; fact = x => (x == 0) ? 1 : x * fact(x - 1);

像吊饰一样工作。

或者，对于在类TreeNode上的对象的前序树遍历，该对象适当地实现了IEnumerable<TreeNode>来遍历其子级：

1
2
3
4
5

Action<TreeNode, Action<TreeNode>> preorderTraverse = null;
preorderTraverse = (node, action) => {
action(node);
foreach (var child in node) preorderTraverse(child, action);
};

A simple alternative is to"go back in time" to the antics of C and C++: declaration before definition. Try the following:

1
2
Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

Works like a charm.

是的，确实有效，但有一点警告。 C#具有可变的引用。因此，请确保您不会意外地执行以下操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

// Make a new reference to the factorial function
Func<int, int> myFact = fact;

// Use the new reference to calculate the factorial of 4
myFact(4); // returns 24

// Modify the old reference
fact = x => x;

// Again, use the new reference to calculate
myFact(4); // returns 12

当然，此示例有些虚构，但是在使用可变引用时可能会发生这种情况。如果您使用aku的链接中的组合器，则将不可能。

假设一个神话般的对象TreeItem，它包含一个Children集合来表示您的层次结构。

1
2
3
4
5
6
7
8
9
10
11
12

public void HandleTreeItems(Action<TreeItem> item, TreeItem parent)
{
if (parent.Children.Count > 0)
{
foreach (TreeItem ti in parent.Children)
{
HandleTreeItems(item, ti);
}
}

item(parent);
}

现在可以调用它，通过将名称打印到控制台来传递处理一项的lambda。