1

我有两种方法可以从平面列表返回动态层次结构。第一个在这里使用递归方法效果很好：(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)
        };
4

3 回答 3

2

要从下向上构建，您需要从所有有效的叶节点（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)。

于 2013-01-23T05:25:55.610 回答
1

首先，我建议定义一个递归方法来确定一个项目是否有一个输出项目的路径，基于给定的列表：

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();
于 2013-01-23T05:49:20.197 回答
0

你想遍历你的数据深度优先顺序

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

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;
}
于 2013-01-23T10:12:05.720 回答