将从树结构中 return 特定节点的函数

Question

我正在编写函数，它将 return 树结构中的特定节点。但是当我使用 LINQ 在树中搜索时，它在第一个分支中搜索，最后当它到达叶时它抛出空引用异常，因为叶没有任何子节点。

这是我的 class,

public class Node
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public string Content { get; set; }
        public IEnumerable<Node> Children { get; set; }
        public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy
        {
            return new[] { this }
                   .Concat(Children.SelectMany(child => child.GetNodeAndDescendants()));
        }
    }

我就是这样调用这个函数的，

 var foundNode = Location.GetNodeAndDescendants().FirstOrDefault(node => node.Name.Contains("string to search"));

或

var foundNode = Location.GetNodeAndDescendants().FirstOrDefault(node => node.Id==123)

执行此操作的正确方法是什么？任何示例代码将不胜感激

Answer 1

如果您不介意依赖第三方解决方案，我有一个我一直在开发的轻量级库，它几乎可以对任何树执行此操作和许多其他操作。它被称为Treenumerable。您可以在 GitHub 上找到它：https://github.com/jasonmcboyd/Treenumerable; and the latest version (1.2.0 at this time) on NuGet here: http://www.nuget.org/packages/Treenumerable。它具有良好的测试覆盖率并且看起来很稳定。

它确实需要您创建一个助手 class，它使用两个方法实现 ITreeWalker 接口：TryGetParent 和 GetChildren。正如您可能猜到的那样，TryGetParent 获得了一个节点的父节点，因此您的 Node class 必须以它知道其父节点的方式进行修改。我想您可以在 TryGetParent 中抛出一个 NotSupported 异常，因为该方法对于任何遍历操作都不是必需的。不管怎样，无论你走哪条路，下面的代码都会做你想做的事：

ITreeWaler<Node> walker;
// Don't forget to instantiate 'walker'.

var foundNode =
    walker
    .PreOrderTraversal(Location)
    .FirstOrdefault(node => node.Name.Contains("string to search"));

我的实现与您的实现之间值得一提的一个区别是我的实现不依赖于递归。这意味着您不必担心一棵深树抛出 WhosebugException.

Answer 2

编写自己的函数没有错，但是基于 LINQ 或递归迭代器的实现不是一个好主意（性能！）。但是为什么要依赖外部库呢？很多你不需要的代码，实现接口，修改你的类等。编写一个用于预序树遍历的通用函数并将其用于任何树结构并不难。这里是我参与How to flatten tree via LINQ?的修改版（没什么特别的，普通的迭代实现）：

public static class TreeHelper
{
    public static IEnumerable<T> PreOrderTraversal<T>(T node, Func<T, IEnumerable<T>> childrenSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = Enumerable.Repeat(node, 1).GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var children = childrenSelector(item);
                    if (children == null) continue;
                    stack.Push(e);
                    e = children.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

并且您在 class Node 中的函数变为：

public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy
{
    return TreeHelper.PreOrderTraversal(this, node => node.Children);
}

其他一切都保持你做的方式并且应该工作 w/o 任何问题。

编辑：看起来你需要这样的东西：

public interface IContainer
{
    // ...
}

public class CustomerNodeInstance : IContainer
{
    // ...
}

public class ProductNodeInstance : IContainer
{
    // ...
}

public class Node : IContainer
{
    // ...
    public IEnumerable<IContainer> Children { get; set; }
    public IEnumerable<IContainer> GetNodeAndDescendants() // Note that this method is lazy
    {
        return TreeHelper.PreOrderTraversal<IContainer>(this, item => { var node = item as Node; return node != null ? node.Children : null; });
    }
}

将从树结构中 return 特定节点的函数

Function which will return particular node from tree structure

c#

linq

tree

recursion