如何将树过滤到共同父级

Question

我有一棵树（带有复选框），如下所示。

A
    A1
        A11
            A111（已选）
            A112（已选）
            A113
        B11
            B111（已选）
            B112

我想过滤它以返回如下，因为A1是所选节点的公共父级

A1
   A11
       A111
       A112
    B11
       B111

树是一个具有根节点及其子节点的层次结构：

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

基本上，这是 UI 中的树结构。根据用户选择的内容（复选框），我必须找到公共父级并显示结果树。

Answer 1

以下是查找一组节点的共同祖先的基本思想：

1. 对于每个选定的节点，获取包括其自身及其祖先的节点集；
2. 找到所有这些节点的交集；
3. 其中，选取深度最高的节点。

那么，我们该怎么做呢？

让我们首先编写一个属性来获取 的祖先列表Node。（我们需要“and self”部分来处理仅选择单个节点的情况 - 在这种情况下，公共节点是该节点本身，我假设您不想要父节点。如果我错了并且您希望它无论如何都能找到父节点，您可以更改此属性以仅返回严格的祖先，但随后您需要为没有祖先的根节点添加特殊情况。）

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;
    }
}

命名空间中已经有一个Intersect方法System.Linq可以找到一组项的交集，因此我们已经完成了第 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