부모/자녀의 평평한 목록에서 계층 구조 구축

StackOverflow https://stackoverflow.com/questions/319108

문제

계층 구조에 항목 목록이 있으며이 목록을 실제 객체의 계층 구조로 구문 분석하려고합니다. 사용 중입니다 수정 된 선주문 트리 트래버스 이 목록을 통해 저장/반복하는 것은 내가 가진 것은 "왼쪽"값으로 주문한 모든 어린이를 포함하여 나무의 하위 집합입니다.

예를 들어, 나무가 주어지면 :

  • 항목 a
    • 항목 A.1
    • 항목 A.2
      • 항목 A.2.2
  • 항목 b
    • 항목 B.1
  • 항목 c

목록을 얻습니다.

  • 항목 A, 항목 A.1, 항목 A.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

나는 이것을하는 방법 - 부모를 추적하고 더 큰 점프를 처리 할 수있는 방법을 잃어 버렸습니다 (예 : 항목 A.2.2-> 항목 B).

편집 : 여기에서 비 브루트 포스 솔루션을 찾고 있습니다 (예 : 여러 번 반복하지 말고 상위 수준의 부모 만 남을 때까지 아이템을 어린이 노드로 옮기고 있습니다). 한 번 반복 할 수있는 우아한 방법이 있다고 생각합니다.

그들은 항상 계층 순서 (MPTT를 사용하기 때문에)이므로 주어진 항목은 항상 이전 항목의 어린이 또는 형제가되거나 적어도 이전 항목과 부모를 공유 할 것입니다. 그것은 결코 나무에있는 다른 곳에서 오지 않을 것입니다.

도움이 되었습니까?

해결책

여기에 내가 글을 쓰는 기능은 다음과 같습니다. MPTT를 사용하여 개체를 저장하고 있으므로 목록은 '왼쪽'값 순서대로이므로 기본적으로 부모는 항상 목록에 주어진 항목 앞에 오는 것을 의미합니다. 다시 말해, Item.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();
}

다른 팁

나는 당신이 이미 모든 항목의 부모를 알고 있다고 가정합니다..

목록의 모든 항목을 한 번 반복하고 현재 항목을 부모의 어린이 목록에 추가하는 것입니다. 대상 중첩 목록에 부모가없는 항목 만 보관하십시오.

여기 몇 가지 의사 코드가 있습니다.

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();
    }
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top