建设层次的对象平面列表中的父母/子女
-
11-07-2019 - |
题
我有一个列表中的项目在一个层次结构,并且我尝试分析这列入一个实际的层次的对象。我在使用 修改前以穿越树 储存/迭代过这个名单,所以我有什么一个子集树,包括所有儿童,下令通过他们的"左边"的价值。
例如,给定的树:
- 项目一
- 项目A.1
- 项目A.2
- 项目A.2.2
- 项目B
- 项目B.1
- 项目C
我的名单:
- 的项目,项目A.1项A.2,项目A.2.2项目B,项目B.1项C
(这是为了"左"值从修改预订树setup).
什么我想要做的是分析这成为对象,其中包含实际的结构树,例如:
Class TreeObject {
String Name;
Guid ID;
Guid ParentID;
List<TreeObject> Children;
}
平列出返回作为一个列表中的TreeObjects和每个TreeObject有属性ID,ParentID,左,右。我在寻找什么是功能:
List<TreeObject> FlatToHeirarchy(List<TreeObject> list);
这需要平面列表中,返回一个嵌套清单。
换句话说:
List<TreeObject> flatSet = LoadTreeObjectsFromDatabase();
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2
我在失去怎么做这个-跟踪父母,并能够处理更大的跳跃(例如,项目A.2.2->项目B)。
编辑:我正在寻找非暴力的解决方案(例如,循环不好几次,移动的物品进儿童节点,直到只有顶级的父母左)。我猜还有一个优雅的方法,可以一次循环,只是地方的项目作为必要的。
记住,他们总是在一个层次了(因为我使用MPTT),因此某一项目将始终是一个孩子或兄弟姐妹以前的项目,或者至少共用一个父母与以前的项目。它是永远不要去别的地方在树。
解决方案
这里的功能结果我的写作。我使用的MPTT储存的对象,所以该清单是为了在"左"的价值,这基本上意味着父母总是之前的任何特定项目的清单。换句话说,项目所引用的项目。ParentID总是已经加入(的情况除外顶级或根节点)。
public class TreeObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}
public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
// hashtable lookup that allows us to grab references to containers based on id
var lookup = new Dictionary<int, TreeObject>();
// actual nested collection to return
var nested = new List<TreeObject>();
foreach (TreeObject item in list)
{
if (lookup.ContainsKey(item.ParentId))
{
// add to the parent's child list
lookup[item.ParentId].Children.Add(item);
}
else
{
// no parent added yet (or this is the first time)
nested.Add(item);
}
lookup.Add(item.Id, item);
}
return nested;
}
和一个简单的试验(在LinqPad):
void Main()
{
var list = new List<TreeObject>() {
new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
};
FlatToHierarchy(list).Dump();
}
结果:
因为我更新这5年后,这里是皇宫递归的版本:
public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
return (from i in list
where i.ParentId == parentId
select new TreeObject {
Id = i.Id,
ParentId = i.ParentId,
Name = i.Name,
Children = FlatToHierarchy(list, i.Id)
}).ToList();
}
其他提示
我假定你已经知道母体的所有项目.
所有你需要做的是迭代通过的所有项目的列表,一旦和增加的项目向其父母的儿童的名单。只有保留的项目没有父母中的目标嵌套清单。
这里是一些伪码:
foreach Item item in flatlist
if item.Parent != null
Add item to item.Parent.ChildrenList
Remove item from flatlist
end if
end for
如得到父母,从我可以看看你的实例,则可能需要分析的名称,并建立一堆为你提前在清单。
这个问题 看起来 很难,但它实际上不是。很多人看这个问题从错误的角度;不,你必须试着填入每一个儿童名单,而是摆脱的儿童的项目列表,然后就变得容易。
备选版本,汇编了通常情况下,我不确定如果有问题的代码以上。
private List<Page> FlatToHierarchy(List<Page> list) {
// hashtable lookup that allows us to grab references to the parent containers, based on id
Dictionary<int, Page> lookup = new Dictionary<int, Page>();
// actual nested collection to return
List<Page> nested = new List<Page>();
foreach(Page item in list) {
if (lookup.ContainsKey(item.parentId)) {
// add to the parent's child list
lookup[item.parentId].children.Add(item); //add item to parent's childs list
lookup.Add(item.pageId, item); //add reference to page in lookup table
} else {
// no parent added yet (or this is the first time)
nested.Add(item); //add item directly to nested list
lookup.Add(item.pageId, item); //add reference to page in lookup table
}
}
return nested;
}
这里是一个例子,希望这可以帮助
class Program
{
static void Main(string[] args)
{
TreeObject a = new TreeObject() { Name = "Item A" };
a.Children.Add( new TreeObject() { Name = "Item A.1" });
a.Children.Add( new TreeObject() { Name = "Item A.2" });
TreeObject b = new TreeObject() { Name = "Item B" };
b.Children.Add(new TreeObject() { Name = "Item B.1" });
b.Children.Add(new TreeObject() { Name = "Item B.2" });
TreeObject c = new TreeObject() { Name = "Item C" };
List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });
string list = BuildList(nodes);
Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
List<TreeObject> newlist = new List<TreeObject>();
TreeObject temp = null;
foreach (string s in list.Split(','))
{
if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
{
temp = new TreeObject() { Name = s };
newlist.Add(temp);
}
else
{
temp.Children.Add(new TreeObject() { Name = s });
}
}
Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
}
static string BuildList(List<TreeObject> nodes)
{
StringBuilder output = new StringBuilder();
BuildList(output, nodes);
return output.Remove(output.Length - 1, 1).ToString();
}
static void BuildList(StringBuilder output, List<TreeObject> nodes)
{
foreach (var node in nodes)
{
output.AppendFormat("{0},", node.Name);
BuildList(output, node.Children);
}
}
}
public class TreeObject
{
private List<TreeObject> _children = new List<TreeObject>();
public string Name { get; set; }
public Guid Id { get; set; }
public List<TreeObject> Children { get { return _children; } }
}
}
纠正给出的例子通过 gregmac
IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
{
var q = (from i in list
where i.parent_id == parentId
select new
{
id = i.id,
parent_id = i.parent_id,
kks = i.kks,
nome = i.nome
}).ToList();
return q.Select(x => new TreeObject
{
children = FlatToHierarchy(list, x.id)
}).ToList();
}