如何将树筛选为公共父级

本文关键字：筛选 | 更新日期: 2023-09-27 18:36:56

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

一个    答1        答11            A111（已选择）            A112（已选择）            答113        B11            B111（已选）            B112系列

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

答1   答11       答111       答112    B11       B111系列

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

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

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

如何将树筛选为公共父级

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

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

那么，我们如何做到这一点呢？

让我们从编写一个属性开始，以获取Node的祖先列表。 （我们需要"和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;
    }
}

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

假设你有一个名为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
相关文章：