Построение иерархических объектов из плоского списка родительских / дочерних
-
11-07-2019 - |
Вопрос
У меня есть список элементов в иерархии, и я пытаюсь разобрать этот список в реальную иерархию объектов.Я использую измененный обход дерева предварительного заказа чтобы сохранить / выполнить итерацию по этому списку, и поэтому у меня есть подмножество дерева, включая всех дочерних элементов, упорядоченных по их "левому" значению.
Например, учитывая дерево:
- Пункт А
- Пункт A.1
- Пункт A.2
- Пункт A.2.2
- Пункт В
- Пункт B.1
- Пункт С
Я получаю список:
- Пункт А, Пункт А.1, Пункт А.2, Пункт А.2.2, Пункт В, Пункт Б.1, Пункт С
(Это в порядке "левого" значения из измененной настройки дерева предварительных заказов).
То, что я хочу сделать, это разобрать это на объекты, которые содержат фактическую структуру дерева, например:
Class TreeObject {
String Name;
Guid ID;
Guid ParentID;
List<TreeObject> Children;
}
Плоский список возвращается как Список TreeObjects - и каждый TreeObject имеет свойства для ID, ParentID, Left и Right.То, что я ищу, - это функция:
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 для хранения объектов, поэтому список составляется в порядке "левого" значения, что в основном означает, что родительский элемент всегда стоит перед любым заданным элементом в списке.Другими словами, элемент, на который ссылается элемент.Родительский идентификатор всегда уже добавлен (за исключением случаев узлов верхнего уровня или корневых узлов).
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 лет спустя, вот рекурсивная версия LINQ:
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; } }
}
}
Исправление примера, приведенного грегмак
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();
}