Поиск класса в списке

Question

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

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

Я попытался выполнить поиск в списке, но это будет искать только классы Node в списке, а не список SubNodes. Посмотрел библиотеку 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

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

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

Answer 2

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

Answer 3

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

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 4

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

Класс Node:

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 5

Вы можете добавить код, который вы flatterns иерархии и использовать 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 к объектам:

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