c＃构建层次结构

Question

我有两种方法从平面列表返回动态层次结构。第一个很好的使用递归方法：(ID/ParentID) list to Hierarchical list。

我现在正在尝试做同样的事情，除了这次只显示那些具有保存报告输出的类别和报告。我不确定从哪里开始，因为我发现的所有内容都是从根部开始构建的，我需要从下往上。

我得到这样的事情，现在在我的第一种方法：

Category 1 
    |_Sub Category 1 
    |_Report 1 
    |_Report 2 
     |_Saved Output 
Category 2 
    |_Sub Category 2 
    | |_Report 3 
    | |_Report 4 
    |_Sub Category 3 
    |_Report 5 
    |_Report 6 
     |_Saved Output 
Category 3 
    |_Sub Category 4 
    |_Report 7 

我想在我的第二个方法是这样的：

Category 1 
    |_Sub Category 1 
    |_Report 2 
     |_Saved Output 
Category 2 
    |_Sub Category 3 
    |_Report 6 
     |_Saved Output 

这里是我的基本测试结构：

class Flat 
{ 
    public int id { get; set; } 
    public int parentId { get; set; } 
    public string name { get; set; } 
    public bool isOutput { get; set; } 

    public Flat(int i, int pid, string n, bool o) 
    { 
     this.id = i; 
     this.parentId = pid; 
     this.name = n; 
     this.isOutput = o; 
    } 
} 

class MyClass 
{ 
    public int id { get; set; } 
    public int parentId { get; set; } 
    public string name { get; set; } 
    public bool isOutput { get; set; } 

    public List<MyClass> children { get; set; } 

    public MyClass() 
    { 
     this.children = new List<MyClass>(); 
    } 
} 

List<Flat> items = new List<Flat>() 
     { 
       new Flat(1,0,"Category 1",false), 
       new Flat(4,1,"Sub Category 1",false), 
       new Flat(8,4,"Report 1",false), 
       new Flat(9,4,"Report 2",false), 
       new Flat(15,9,"Saved Output",true), 
       new Flat(2,0,"Category 2",false), 
       new Flat(5,2,"Sub Category 2",false), 
       new Flat(10,5,"Report 3",false), 
       new Flat(11,5,"Report 4",false), 
       new Flat(6,2,"Sub Category 3",false), 
       new Flat(12,6,"Report 5",false), 
       new Flat(13,6,"Report 6",false), 
       new Flat(16,13,"Saved Output",true), 
       new Flat(3,0,"Category 3",false), 
       new Flat(7,3,"Sub Category 4",false), 
       new Flat(14,7,"Report 7",false) 
     }; 

Answer 1

要从底层开始构建，您需要从所有有效的叶节点开始（output == true），然后向上遍历所有父节点，直到到达根目录。这里有一个方法，应该工作：

List<Flat> GetSavedOutput(List<Flat> items) 
{ 
    // get all output leaf nodes 
    var toAdd = items.Where (i => i.isOutput == true).ToList(); 
    var result = new List<Flat>(); 

    // grab all parent nodes that are not already included until 
    // there's nothing new to add 
    while (toAdd.Count > 0) 
    { 
     result.AddRange(toAdd); 
     toAdd = items.Where (i => !result.Contains(i) 
           && result.Any (r => r.parentId == i.id)).ToList(); 
    } 

    return result; 
} 

这是短，见效快，而且应该为小的，简单的树工作得很好，但它不是因为一遍遍处理同一节点的最有效的方法。稍微复杂一些，但更好的方法，将是向上走父树的每个项目：

List<Flat> GetSavedOutput(List<Flat> items) 
{ 
    var savedOutput = items.Where (i => i.isOutput == true).ToList(); 
    var result = new List<Flat>(); 

    foreach (var item in savedOutput) { 
     result.Add(item); 
     var temp = item; 
     do { 
      temp = items.Single (i => i.id == temp.parentId); 
      result.Add(temp); 
     } while (temp.parentId != 0); 
    } 

    return result; 
} 

如果这仍然不够有效，可以通过存储父节点引用获得更多一点的表现在每个Flat实例中，以便父代可以在O(1)中直接引用，而无需使用Single（效率为O(n)）的调用查找它。

Answer 2

首先，我会建议定义一个递归的方法来确定一个项目是否具有输出项目的路径，根据给定的名单上：

static bool HasPathToOutput(List<Flat> items, Flat item) 
{ 
    if (item.isOutput) 
    { 
     return true; 
    } 

    // Recursively determine whether any of the item's children have 
    // a path to an output 
    return items.Where(i => i.parentId == item.id).Any(i => HasPathToOutput(items, i)); 
} 

然后使用该方法通过一些LINQ查询运行列表，首先得到的是有一个路径保存输出的项目，然后建立等级，最后，获取仅仅是在层次结构的顶部项目：

// Generate a predicate based on the list 
List<MyClass> foundItems = 
     items.Where(item => HasPathToOutput(items, item)) 
      .Select(f => new MyClass { id = f.id, isOutput = f.isOutput, parentId = f.parentId, name = f.name }) 
      .ToList(); 

// Generate child relationships 
foundItems.ForEach(item => item.children = foundItems.Where(child => child.parentId == item.id).ToList()); 

// Filter out top-level items 
List<MyClass> topLevel = foundItems.Where(i => i.parentId == 0).ToList(); 

Answer 3

你要遍历数据depth-first order

这将首先查看所有叶节点，将已保存的元素添加到列表并向父节点发送已保存根节点的信号。

public bool StoreSavedElements(List<Tree> elements) 
{ 
    bool nodeSaved = false; 

    foreach (Tree child in childs) 
    { 
     if (child.StoreSavedElements(elements)) 
     { 
      nodeSaved = true; 
     } 
    } 

    if (this.text == "Saved") 
    { 
     nodeSaved = true; 
     elements.Add(this); 
    } 

    return nodeSaved; 
}