2008-11-25 8 views
18

У меня есть список элементов в иерархии, и я пытаюсь разобрать этот список в фактическую иерархию объектов. Я использую modified pre-order tree traversal для хранения/повторения этого списка, и поэтому у меня есть подмножество дерева, включая всех детей, упорядоченное по их «левому» значению.Создание объектов иерархии из плоского списка parent/child

Например, если дерево:

  • Пункт А
    • Пункт A.1
    • Пункт А.2
      • Пункт A.2.2
  • Пункт B
    • Пункт B.1
  • Пункт C

Я получаю список:

  • Пункт А, пункт А.1, А.2 предмета, Пункт A.2.2, Пункт B, Пункт B.1, Пункт C

(Это в порядке «левого» значения из измененной настройки дерева предварительного заказа).

То, что я хочу сделать, это разобрать это в объекты, которые содержат фактическую структуру дерева, например:

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 

Я в недоумении, как это сделать - отслеживании родителей, и быть в состоянии иметь дело с большим скачком (например, пункт А.2.2 -> Пункт Б).


Edit: Я ищу не-перебор решения здесь (например, не зацикливание несколько раз, перемещение элементов в дочерние узлы, пока не только родители верхнего уровня слева). Я предполагаю, что есть элегантный метод, который может зацикливаться один раз и просто поместить элементы по мере необходимости.

Помните, что они всегда находятся в иерархическом порядке (поскольку я использую MPTT), поэтому данный элемент всегда будет дочерним или родственным из предыдущего элемента или, по крайней мере, разделяет родителя с предыдущим элементом , Он никогда не появится где-то еще в дереве.

+0

Означает ли это ваше хранение ParentID и левые и правые значения для каждого узла в БД? – 2011-09-05 20:47:49

ответ

24

Вот функция, которую я в конечном итоге писать. Я использую 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(); 
} 

Результаты:

enter image description here

Поскольку я обновляю это 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(); 
} 
3

Предполагаю, что вы уже знаете родителя всех предметов.

Все, что вам нужно сделать, это перебрать все элементы списка один раз и добавить текущий элемент в список дочерних элементов его родителя. Храните элементы без родителей в целевом вложенном списке.

Вот некоторые псевдо-код:

foreach Item item in flatlist 
    if item.Parent != null 
     Add item to item.Parent.ChildrenList 
     Remove item from flatlist 
    end if 
end for 

Что касается получения родителей, от того, что я могу видеть в вашем примере, вы, возможно, придется разобрать имя и построить стек по мере продвижения в списке.

Это проблемы выглядит трудно, но это действительно так. Многие люди видят эту проблему под неправильным углом; вы не должны пытаться заполнять список всех детей, а скорее избавляться от детских предметов из плоского списка, тогда становится легко.

+0

Это та часть, которую я не получаю. Я предполагаю, что есть хороший способ иметь стек, который содержит всех родителей, и продолжать настаивать на нем, поскольку предмет глубже его родителя или выталкивает последний из них, когда вы поднимаетесь вверх. То, что я хочу избежать, - это цикл по списку, удаляющий элементы. – gregmac 2008-11-26 01:58:30

+0

Как только вы узнаете родителя каждого узла, вы можете пройти через список один раз. Я обновил свой ответ с помощью некоторого псевдокода. – Coincoin 2008-11-26 16:41:54

+0

Я знаю идентификатор родителя, но у меня нет ссылки на сам родительский объект (без поиска по списку, конечно). – gregmac 2008-12-01 21:45:01

0

Вот пример, надеюсь, что это помогает

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

}

1

Альтернативная версия, которая компилируется нормально, я не был уверен, была ли проблема с кодом выше.

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; 
    } 
0

Корректирование пример, приведенный 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(); 
    } 

 Смежные вопросы

  • Нет связанных вопросов^_^