修剪结束节点满足某些标准的树枝

本文关键字：标准 结束 节点 满足 修剪 | 更新日期: 2023-09-27 18:09:49

我有一个TreeNode类如下:

public class TreeNode
{
    public enum NodeType { Root,Element, Category}
    public TreeNode()
    {
        Children = new List<TreeNode>();
    }
    public List<TreeNode> Children { get; set; }
    public string Name { get; set; }
    public NodeType Type { get; set; }
}

我有一个BuildTree方法，它填充树结构，为每个节点设置节点名称和类型(例如，第一个节点将被设置为根类型，子节点可以是元素或类别类型)。

我正在寻找一种有效的方法(也许使用LINQ)来修剪结束节点类型不属于类别类型的树枝。对如何实现这一点有什么想法吗?

这里有一个可视化的例子:

前

: 

Root
|
|_ NodeA (Element)
|_ Node B (Element)
|  |_ Node B.1 (Category)
|_ Node C (Element)
|  |_ Node C.1 (Element)
|    |_Node C.1.1 (Category)
|_ Node D (Element)
   |_Node D.1 (Element)
后

: 

Root
|
|_ Node B (Element)
|  |_ Node B.1 (Category)
|_ Node C (Element)
   |_ Node C.1 (Element)
     |_Node C.1.1 (Category)

提前感谢!

修剪结束节点满足某些标准的树枝

首先，我们需要描述如何对树进行深度优先聚合:

//seed: leafNode -> accumulate
//func: interiorNode, children accumulates -> accumulate
public static TAccumulate Aggregate<TAccumulate>(
    this TreeNode root,
    Func<TreeNode, TAccumulate> seed,
    Func<TreeNode, List<TAccumulate>, TAccumulate> func)
{
    if (root.Children == null || !root.Children.Any())
        return seed(root);
    return func(root, children.Select(child => child.Aggregate(seed, func)).ToList());
}

然后我们可以用它来做一个修改，如你所要求的:

tree.Aggregate(
    leaf => new
    {
        Keep = leaf.NodeType == TreeNode.NodeType.Category,
        Node = leaf
    },
    (node, children) =>
    {
        var removal = new HashSet<TreeNode>(
            children.Where(child => !child.Keep).Select(child => child.Node));
        node.Children.RemoveAll(removal.Contains);
        return new
        {
           Keep = children.Any(child => child.Keep),
           Node = node
        };
    });

这为您提供了一种简洁的、声明性的方式来描述您想要应用于您的树的转换，而无需在转换的描述中进入遍历的细节。

没那么复杂;你只需要对树进行递归遍历。基本情况是节点本身是一个类别。然后在每个子元素上调用该函数，并保留那些在其子元素中有一个类别的元素。

/// <summary>
/// Removes all child nodes that do not have at least one Category as a child.
/// </summary>
/// <param name="node">The node to alter the children of.</param>
/// <returns>True if there is at least one Category in this subtree</returns>
public static bool RemoveEmptyElements(TreeNode node)
{
    if (node.Type == TreeNode.NodeType.Category)
        return true;
    node.Children = node.Children.Where(child => RemoveEmptyElements(child))
            .ToList();
    return node.Children.Any();
}

您可以使用后序来遍历树。当你回到树的第二层却没有找到类别类型叶子时。从该节点再次遍历以删除所有从该节点扎根的叶子。

相关文章：