Xây dựng các đối tượng phân cấp từ danh sách phẳng của cha/con

Question

Tôi có một danh sách các mục trong một hệ thống phân cấp và tôi đang cố phân tích danh sách này thành một hệ thống phân cấp thực tế của các đối tượng. Tôi đang sử dụng modified pre-order tree traversal để lưu trữ/lặp lại thông qua danh sách này và vì vậy những gì tôi có là một tập con của cây, bao gồm tất cả trẻ em, được sắp xếp theo giá trị "trái" của chúng.

Ví dụ, với cây:

• Mục A
  • mục A.1
  • mục A.2
    • mục A.2.2
• mục B
  • mục B.1
• mục C

tôi nhận được danh sách:

• Mục A, Mục A.1, khoản A.2, Mục A.2.2, Mục B, Mục B.1, Mục C

(Đây là thứ tự của giá trị "bên trái" từ cài đặt cây đã được sửa đổi trước đó).

Những gì tôi muốn làm là phân tích này thành các đối tượng có chứa các cấu trúc thực tế của cây, ví dụ:

Class TreeObject { 
    String Name; 
    Guid ID; 
    Guid ParentID; 
    List<TreeObject> Children; 
} 

Danh sách phẳng được trả về như một Danh sách TreeObjects - và mỗi TreeObject có thuộc tính cho ID , ParentID, Trái và Phải. Những gì tôi đang tìm kiếm là một chức năng:

List<TreeObject> FlatToHeirarchy(List<TreeObject> list); 

lấy danh sách phẳng và trả về danh sách lồng nhau.

Nói cách khác:

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null 
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet); 
// nestedSet.count == 3; nestedSet(0).Children.count == 2 

Tôi đang ở một mất mát như thế nào để làm điều này - theo dõi của cha mẹ, và có thể đối phó với một bước nhảy lớn hơn (ví dụ, khoản A.2.2 -> mục B).

---

Chỉnh sửa: Tôi đang tìm một giải pháp không brute-force ở đây (ví dụ, không lặp lại nhiều lần, di chuyển các mục vào nút con, cho đến khi chỉ còn cha mẹ cấp cao nhất). Tôi đoán có một phương pháp thanh lịch có thể lặp lại một lần và chỉ cần đặt các mục nếu cần.

Hãy nhớ rằng, chúng luôn theo thứ tự phân cấp (vì tôi đang sử dụng MPTT), vì vậy một mục nhất định sẽ luôn là con hoặc anh chị em của mục trước đó hoặc ít nhất chia sẻ một phụ huynh với mục trước . Nó sẽ không bao giờ đến một nơi khác trong cây.

Answer 1

Dưới đây là các chức năng tôi đã kết thúc bằng văn bản. Tôi đang sử dụng MPTT để lưu trữ các đối tượng, do đó, danh sách theo thứ tự của giá trị 'trái', mà về cơ bản có nghĩa là cha mẹ luôn luôn đến trước bất kỳ mục nào trong danh sách. Nói cách khác, mục được tham chiếu bởi item.ParentID luôn được thêm vào (ngoại trừ trong trường hợp các nút cấp cao nhất hoặc gốc).

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

và một thử nghiệm đơn giản (mà làm việc trong 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(); 
} 

Kết quả:

Kể từ khi tôi đang cập nhật này 5 năm sau, đây là một LINQ đệ quy phiên bản:

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

Answer 2

Tôi giả sử bạn đã biết cha mẹ của tất cả các mục.

Tất cả những gì bạn cần làm là lặp lại tất cả các mục trong danh sách một lần và thêm mục hiện tại vào danh sách con của cha mẹ. Chỉ giữ các mục không có cha mẹ trong danh sách lồng nhau mục tiêu.

Dưới đây là một số mã giả:

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

Như để nhận được các bậc cha mẹ, từ những gì tôi có thể thấy trong ví dụ của bạn, bạn có thể cần phải phân tích tên và xây dựng một chồng như bạn trước trong danh sách.

Sự cố này trông khó nhưng thực sự thì không. Rất nhiều người nhìn thấy vấn đề này từ góc độ sai; bạn không được cố gắng điền vào tất cả các danh sách trẻ em mà là loại bỏ các mục trẻ em khỏi danh sách phẳng, sau đó nó trở nên dễ dàng.

Answer 3

Dưới đây là một ví dụ, hy vọng điều này sẽ giúp

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

}

Answer 4

Phiên bản thay thế biên dịch thông thường, tôi đã không chắc chắn nếu có vấn đề với mã ở trên.

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

Answer 5

Sửa chữa ví dụ đưa ra bởi 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(); 
    }