从树结构返回特定节点的函数 [英] Function which will return particular node from tree structure

问题描述

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

I am writing the function which will return particular node from tree structure. But when I search in a tree using LINQ it is searching in the first branch and finally when it reaches to leaf it is throwing null reference exception as leaf don't have any child.

这是我的课程，

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

这就是我调用此函数的方式

This is how I am calling this function,

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

OR

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

正确的方法是什么?并且任何示例代码将不胜感激

What would be the correct way to do this? and any sample code would be grateful

推荐答案

编写自己的函数没错，但是基于LINQ或递归迭代器的实现不是一个好主意(性能！).但是为什么要依赖外部库呢?许多不需要的代码，实现接口，修改类等.编写用于预遍历树遍历并将其用于任何树结构的通用函数并不难.这是我参与的如何通过LINQ展平树的修改版本? (没什么特别的，普通的迭代实现):

Nothing wrong to write your own function, but implementation based on LINQ or recursive iterator is not a good idea (performance!). But why depending on external libraries? A lot of code that you don't need, implementing interfaces, modifying your classes etc. It's not hard to write a generic function for pre-order tree traversal and use it for any tree structure. Here is a modified version of my participation in How to flatten tree via LINQ? (nothing special, ordinary iterative implementation):

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

其他所有操作均保持原样，并且应该不会出现任何问题.

Everything else stays the way you did it and should work w/o any problem.

编辑:您似乎需要以下内容:

EDIT: Looks like you need something like this:

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

这篇关于从树结构返回特定节点的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！