Нахождение класса в списке

Question

У меня есть класс (Node), у которого есть свойство SubNodes, которое является списком класса Node

У меня есть список узлов (из которых каждый узел может иметь или не иметь список подузлов внутри себя). Мне нужно иметь возможность найти узел в списке / подузлах узла.

Я пытался выполнить поиск в списке, но он будет искать только классы узлов в списке, а не список подузлов. Посмотрел библиотеку C5 и несколько бинарных деревьев, но не нашел ничего подходящего. любой совет?

Класс

 public class Node
 {
        public Guid Id { get; set; }
        public DateTime Created { get; set; }
        public List<Node> Nodes { get;set;}
 }

Функция (результат - конечный результат)

private void GetRecersive(List<Node> list, ref List<Node> result)
        {
            foreach (Node item in list)
            {

                if (item.ParentId.Equals(Guid.Empty))
                {
                    result.Add(item);
                }
                else
                {
                    result.ForEach(x => x.FindNodes(y => y.Id.Equals(item.ParentId)).FirstOrDefault().Nodes.Add(item));
                }

                List<Node> nodes = GetNodesByParent(item.Id);

                GetRecersive(nodes, ref result);
            }
        }

Answer 1

Как говорит empi, рекурсивный поиск здесь идеален. Если у вас действительно есть дерево, то есть циклов нет, все так просто:

public class Node
{
    // Properties as before

    public Node FindById(Guid id)
    {
        if (id == Id)
        {
            return this;
        }
        foreach (Node node in Nodes)
        {
            Node found = node.FindById(id);
            if (found != null)
            {
                return found;
            }
        }
        return null; // Not found in this subtree
    }
}

В противном случае вам нужно будет сохранить набор (например, HashSet<Node>) узлов, которые вы уже посетили. Циклы делают разные вещи неприятными:)

Вы могли бы переписать цикл foreach, используя LINQ:

return Nodes.Select(x => x.FindById(id)).FirstOrDefault();

но я не уверен, что это действительно так же ясно, как явный цикл в данном конкретном случае (и это несмотря на то, что я большой поклонник LINQ).

Answer 2

Вы можете добавить код, который выравнивает вашу иерархию, и использовать LINQ:

public class Node
{
    // Properties

    public IEnumerable<Node> AllNodes
    {
        get
        {
            yield return this;

            foreach (var node in Nodes.SelectMany(n => n.AllNodes))
                yield return node;
        }
    }
}

и используйте LINQ to Objects:

var matches = nodes.SelectMany(n => n.AllNodes).Where(n => n.Created < DateTime.Today);

Answer 3

Вот как я бы сделал это, чтобы покрыть список узлов, независимо от его глубины:

Класс узла:

public class Node
{
    public Guid Id { get; set; }
    public DateTime Created { get; set; }
    public List<Node> Nodes { get; set; }

    public Node()
    {
        this.Nodes = new List<Node>();
    }

    public List<Node> FindNodes(Func<Node, bool> condition)
    {
        List<Node> resList = new List<Node>();

        if (this.Nodes != null && this.Nodes.Count > 0)
        {
            this.Nodes.ForEach(x =>
                {
                    resList.AddRange(x.FindNodes(condition));
                    if (condition(x))
                        resList.Add(x);
                }
            );
        }

        return resList;
    }
}

Имея этот список узлов, например:

List<Node> nodeList = new List<Node>()
{
    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 01, 10), 
        Nodes = { 
            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 01, 11) }, 
            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 01, 12) } } },
    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 02, 10), 
        Nodes = { 
            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 02, 11), 
                Nodes = {
                    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 11, 11) }, 
                    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 12, 12),
                        Nodes = {
                            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2011, 11, 11) }, 
                            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2011, 12, 12) } } } } }, 
            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 02, 12) } } },
    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 03, 10), 
        Nodes = { 
            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 03, 11) }, 
            new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 03, 12) } } },
};

Я могу найти любой подузел, который мне нужен:

List<Node> resList = new List<Node>();

nodeList.ForEach(x =>
    resList.AddRange(x.FindNodes(y => y.Created.Day == 12)));

Вы можете смотреть на что угодно. В приведенном выше примере я ищу узлы, созданные в 12-й день любого месяца и года.

Answer 4

Вам придется искать это рекурсивно (поиск в списке узлов, затем в списке узлов каждого узла в предыдущем списке узлов и т. Д.) И вести список посещенных узлов (иначе вы никогда не закончите, если есть циклы в структуре). Вы пытались это сделать?

Answer 5

Кажется, мы все усложнили. Я показал проблему моему коллеге, и он представил нижеприведенный текст, который отлично работает.

private void BuildUpChildren(List<Node> list)
        {
            foreach (Node item in list)
            {
                List<Node> nodes = GetNodesByParent(item.Id);
                item.Nodes.AddRange(nodes);
                BuildUpChildren(nodes);
            }
}