[c#] LINQ를 사용하여 트리 검색

Program / 글쓴이

이 클래스에서 만든 트리가 있습니다.

class Node
{
    public string Key { get; }
    public List<Node> Children { get; }
}

모든 자녀와 모든 자녀를 검색하여 조건과 일치하는 항목을 얻고 싶습니다.

node.Key == SomeSpecialKey

어떻게 구현할 수 있습니까?

답변

이것은 재귀가 필요하다는 오해입니다. 그것은 것입니다 스택 또는 큐와 쉬운 방법을 필요로 재귀를 사용하여 구현하는 것입니다. 완전성을 위해 비재 귀적 답변을 제공하겠습니다.

static IEnumerable<Node> Descendants(this Node root)
{
    var nodes = new Stack<Node>(new[] {root});
    while (nodes.Any())
    {
        Node node = nodes.Pop();
        yield return node;
        foreach (var n in node.Children) nodes.Push(n);
    }
}

예를 들어 다음 표현식을 사용하여 사용하십시오.

root.Descendants().Where(node => node.Key == SomeSpecialKey)

답변

Linq로 개체 트리 검색

public static class TreeToEnumerableEx
{
    public static IEnumerable<T> AsDepthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)
    {
        yield return head;

        foreach (var node in childrenFunc(head))
        {
            foreach (var child in AsDepthFirstEnumerable(node, childrenFunc))
            {
                yield return child;
            }
        }

    }

    public static IEnumerable<T> AsBreadthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)
    {
        yield return head;

        var last = head;
        foreach (var node in AsBreadthFirstEnumerable(head, childrenFunc))
        {
            foreach (var child in childrenFunc(node))
            {
                yield return child;
                last = child;
            }
            if (last.Equals(node)) yield break;
        }

    }
}

답변

Linq를 구문과 같은 방식으로 유지하려면 모든 하위 항목 (자식 + 자식의 자식 등)을 가져 오는 방법을 사용할 수 있습니다.

static class NodeExtensions
{
    public static IEnumerable<Node> Descendants(this Node node)
    {
        return node.Children.Concat(node.Children.SelectMany(n => n.Descendants()));
    }
}

이 열거 형은 where 또는 first 또는 무엇이든 사용하여 다른 것과 마찬가지로 쿼리 할 수 ​​있습니다.

답변

이 확장 방법을 시도하여 트리 노드를 열거 할 수 있습니다.

static IEnumerable<Node> GetTreeNodes(this Node rootNode)
{
    yield return rootNode;
    foreach (var childNode in rootNode.Children)
    {
        foreach (var child in childNode.GetTreeNodes())
            yield return child;
    }
}

그런 다음 Where()절 과 함께 사용하십시오 .

var matchingNodes = rootNode.GetTreeNodes().Where(x => x.Key == SomeSpecialKey);

답변

아마도 당신은 단지

node.Children.Where(child => child.Key == SomeSpecialKey)

또는 한 단계 더 깊이 검색해야하는 경우

node.Children.SelectMany(
        child => child.Children.Where(child => child.Key == SomeSpecialKey))

모든 수준에서 검색해야하는 경우 다음을 수행하십시오.

IEnumerable<Node> FlattenAndFilter(Node source)
{
    List<Node> l = new List();
    if (source.Key == SomeSpecialKey)
        l.Add(source);
    return
        l.Concat(source.Children.SelectMany(child => FlattenAndFilter(child)));
}

답변

public class Node
    {
        string key;
        List<Node> children;

        public Node(string key)
        {
            this.key = key;
            children = new List<Node>();
        }

        public string Key { get { return key; } }
        public List<Node> Children { get { return children; } }

        public Node Find(Func<Node, bool> myFunc)
        {
            foreach (Node node in Children)
            {
                if (myFunc(node))
                {
                    return node;
                }
                else
                {
                    Node test = node.Find(myFunc);
                    if (test != null)
                        return test;
                }
            }

            return null;
        }
    }

그런 다음 다음과 같이 검색 할 수 있습니다.

    Node root = new Node("root");
    Node child1 = new Node("child1");
    Node child2 = new Node("child2");
    Node child3 = new Node("child3");
    Node child4 = new Node("child4");
    Node child5 = new Node("child5");
    Node child6 = new Node("child6");
    root.Children.Add(child1);
    root.Children.Add(child2);
    child1.Children.Add(child3);
    child2.Children.Add(child4);
    child4.Children.Add(child5);
    child5.Children.Add(child6);

    Node test = root.Find(p => p.Key == "child6");

답변

IEnumerable<T>확장 방법을 사용하지 않는 이유

public static IEnumerable<TResult> SelectHierarchy<TResult>(this IEnumerable<TResult> source, Func<TResult, IEnumerable<TResult>> collectionSelector, Func<TResult, bool> predicate)
{
    if (source == null)
    {
        yield break;
    }
    foreach (var item in source)
    {
        if (predicate(item))
        {
            yield return item;
        }
        var childResults = SelectHierarchy(collectionSelector(item), collectionSelector, predicate);
        foreach (var childItem in childResults)
        {
            yield return childItem;
        }
    }
}

그럼 그냥 해

var result = nodes.Children.SelectHierarchy(n => n.Children, n => n.Key.IndexOf(searchString) != -1);