بناء كائنات هرمية من القائمة المسطحة للوالد/الطفل

Question

لدي قائمة بالعناصر الموجودة في تسلسل هرمي، وأحاول تحليل هذه القائمة إلى تسلسل هرمي فعلي للكائنات.أنا استخدم تعديل اجتياز شجرة الطلب المسبق لتخزين/التكرار من خلال هذه القائمة، وما لدي هو مجموعة فرعية من الشجرة، بما في ذلك جميع الأطفال، مرتبة حسب قيمتها "اليسرى".

على سبيل المثال، نظرا للشجرة:

• البند أ
  • البند أ.1
  • البند أ.2
    • البند أ.2.2
• البند ب
  • البند ب.1
• البند ج

أحصل على القائمة:

• العنصر أ، العنصر أ.1، العنصر أ.2، العنصر أ.2.2، العنصر ب، العنصر ب.1، العنصر ج

(هذا بترتيب القيمة "اليسرى" من إعداد شجرة الطلب المسبق المعدل).

ما أريد القيام به هو تحليل هذا إلى كائنات تحتوي على البنية الفعلية للشجرة، على سبيل المثال:

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

يتم إرجاع القائمة المسطحة كقائمة كائنات TreeObject - ولكل كائن TreeObject خصائص للمعرف، و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 -> البند ب).

---

يحرر:أنا أبحث عن حل غير القوة الغاشمة هنا (على سبيل المثال، عدم التكرار عدة مرات، ونقل العناصر إلى العقد الفرعية، حتى يتبقى فقط الآباء من المستوى الأعلى).أعتقد أن هناك طريقة أنيقة يمكنها التكرار مرة واحدة، ووضع العناصر حسب الحاجة فقط.

تذكر أنها تكون دائمًا بترتيب هرمي (نظرًا لأنني أستخدم MPTT)، لذا سيكون العنصر المحدد دائمًا تابعًا أو شقيقًا للعنصر السابق، أو على الأقل يشارك أحد الوالدين مع العنصر السابق.لن يأتي أبدًا إلى مكان آخر في الشجرة.

Answer 1

هذه هي الوظيفة التي انتهيت من كتابتها.أنا أستخدم 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();
}

نتائج:

وبما أنني أقوم بتحديث هذا بعد 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();
}

Answer 2

أفترض أنك تعرف أصل جميع العناصر بالفعل.

كل ما عليك فعله هو تكرار كل عناصر القائمة مرة واحدة وإضافة العنصر الحالي إلى القائمة الفرعية الخاصة بالأصل.احتفظ فقط بالعناصر التي ليس لها أصول في القائمة المتداخلة المستهدفة.

إليك بعض التعليمات البرمجية الزائفة:

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

أما بالنسبة للحصول على الوالدين، فمن ما يمكنني رؤيته في المثال الخاص بك، قد تحتاج إلى تحليل الاسم وإنشاء مكدس أثناء تقدمك في القائمة.

هذه المشاكل تبدو صعب ولكنه في الحقيقة ليس كذلك.كثير من الناس يرون هذه المشكلة من زاوية خاطئة؛يجب ألا تحاول ملء كل قائمة أطفال، بل عليك التخلص من عناصر الأطفال من القائمة المسطحة، عندها يصبح الأمر سهلاً.

Answer 3

الإصدار البديل الذي يتم تجميعه بشكل طبيعي، لم أكن متأكدًا مما إذا كانت هناك مشكلة في الكود أعلاه.

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 4

هنا مثال، ونأمل أن يساعد هذا

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 5

تصحيح المثال الذي قدمه com.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();
    }