且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

从树结构返回特定节点的函数

更新时间:2023-02-05 20:44:12

编写自己的函数没错,但是基于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; });
    }
}