使用c#lambdas进行递归非二进制,非排序树搜索

Question

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


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

1)如何编写递归lambda表达式以返回具有特定值的TreeNode(如果未找到则返回null),假设值是唯一的？当然#1可以使用#2来回答,但我想如果你知道没有重复,可能会有更有效的方法.

2)假设值不唯一,现在返回匹配列表？

Answer 1

编辑:更正了代码,我实际上编译并测试了两段代码,但我必须先粘贴版本才能在VS中修复它们.对于那个很抱歉.

我添加了一个带有代码的Subversion存储库,包括单元测试,以确保它现在按预期工作,在这里,使用用户名和密码登录为"guest",没有引号.

像这样:

1:先找到

Func<TreeNode, String, TreeNode> findNode = null; // satisfy recursion re-use
findNode = (n, value) =>
{
    if (n == null) return n;
    if (n.Value == value) return n;
    foreach (var subNode in n.Nodes)
    {
        TreeNode foundNode = findNode(subNode, value);
        if (foundNode != null) return foundNode;
    }
    return null;
};

请注意,此处的陷阱是对于要递归的lambda或委托,在将实际委托分配给变量之前,需要先使用已知值声明变量.否则,编译器会在给定值之前抱怨您正在使用变量.

2:找到所有

Func<TreeNode, String, List<TreeNode>> findNodes = null;
findNodes = (n, value) =>
{
    var result = new List<TreeNode>();
    if (n == null) return result;
    if (n.Value == value) result.Add(n);
    foreach (var subNode in n.Nodes)
    {
        result.AddRange(findNodes(subNode, value));
    }
    return result;
};

这里的诀窍就是收集每个级别的节点,并向上聚合.