剪枝樹枝

Question

我有一個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方法用於填充樹結構設置節點名稱和類型的每個節點（例如該第一個節點將被設置爲根類型，並且子節點可以是Element或Category類型）。

我正在尋找一種有效的方法（可能使用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) 

提前感謝！

Answer 1

首先，我們需要描述如何做一個樹的深度優先聚集：

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

這給你一個簡明的聲明方式來描述你想要的變換應用到你的樹上，而不需要在變換的描述中進入遍歷的細節。

Answer 2

它並不那麼複雜;你只需要樹的遞歸遍歷。基本情況是節點本身是一個類別。然後，只需調用每個孩子的功能，並保留那些在他們的孩子中有類別的功能。

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

Answer 3

您可以使用後序遍歷一棵樹。當你回到樹的第二級時，沒有找到類別類型葉。從此節點再次遍歷以刪除所有以此爲根的葉子。