Как фильтровать дерево для общего родителя

Question

У меня есть дерево (с флажком), которое выглядит следующим образом.

 
A 
    A1 
     A11 
      A111 (selected) 
      A112 (selected) 
      A113 
     B11 
      B111 (selected) 
      B112 

Я хочу, чтобы фильтровать это, чтобы вернуться как следует, так как A1 является общим родителем для выбранных узлов

 
A1 
    A11 
     A111 
     A112 
    B11 
     B111 

Дерево представляет собой иерархию с корневыми узлами и их детьми:

public class Node 
{ 
    public int Id; 
    public string Name; 
    public Node Parent; 
    public List<Node> Children; 
} 

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

Answer 1

Вот основная идея для нахождения общего предка набора узлов:

1. Для каждый выбранный узел, получает множество узлов, включая себя и своих предков;
2. Найти перекресток всех этих узлов;
3. Из них возьмите узел с наивысшей глубиной.

Итак, как мы это сделаем?

Начнем с написания имущества, чтобы получить список предков для Node. (Нам нужна часть «и сам», чтобы обрабатывать ситуацию, когда выбран только один узел - в этом случае общий узел - это сам узел, и я предполагаю, что вы не хотите родителя. Если я ошибаюсь и вы хотите, чтобы найти родителей в любом случае, вы можете изменить это свойство возвращать только строгие предков, но тогда вам нужно добавить специальный случай для корневого узла, который не имеет предков.)

public List<Node> AncestorsAndSelf 
{ 
    get 
    { 
     List<Node> list = new List<Node> { this }; 
     Node p = Parent; 
     while (p != null) 
     { 
      list.Add(p); 
      p = p.Parent; 
     } 
     return list; 
    } 
} 

В домене System.Linq уже существует метод Intersect, который может найти пересечение набора элементов, поэтому мы получили этот шаг 2.

Для третьего шага нам нужен способ получить глубину узла. Но так как у нас уже есть AncestorsAndSelf свойства написано, это тривиально: Так что теперь у нас есть все части

public int Depth 
{ 
    get { return AncestorsAndSelf.Count; } 
} 

, мы можем написать метод, чтобы найти общий предок выбранного набора узлов:

public static Node FindClosestCommonAncestor(IEnumerable<Node> selectedNodes) 
{ 
    IEnumerable<Node> commonAncestors = selectedNodes.First().AncestorsAndSelf; 
    foreach (Node n in selectedNodes.Skip(1)) 
    { 
     commonAncestors = commonAncestors.Intersect(n.AncestorsAndSelf); 
    } 
    return commonAncestors.OrderByDescending(n => n.Depth).FirstOrDefault(); 
} 

Как только у нас есть общий предок, нам нужен способ распечатать поддерево. Это можно сделать с помощью простого рекурсивного метода, как это:

public override string ToString() 
{ 
    return ToString(""); 
} 

private string ToString(string indent) 
{ 
    string s = indent + Name + "\r\n"; 
    foreach (Node child in Children) 
    { 
     s += child.ToString(indent + " "); 
    } 
    return s; 
} 

Вот демонстрационный показ все это в действии: https://dotnetfiddle.net/cl7JGp

Answer 2

Предполагая, что вы список узлов корневого уровня называется nodes вы можете просто сделать:

var node = nodes.SingleOrDefault(_ => _.Name == "A1"); 
if (null != node) 
    return node.Children; 
return new List<Node>(); 
// or you can return null if you'd prefer