5

我有一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）来修剪结束节点类型不是 Category 类型的树枝。关于如何实现这一目标的任何想法？

这是一个视觉示例：

之前：

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)

提前致谢！

4

3 回答 3

3

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

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

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

于 2013-04-18T19:49:33.527 回答
1

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

/// <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();
}
于 2013-04-18T19:43:55.617 回答
0

您可以只使用后序遍历一棵树。当您返回树的第 2 级而没有找到类别类型叶时。再次从该节点遍历以删除所有以该节点为根的叶子。

于 2013-04-18T19:49:04.633 回答