Удаление головы вокруг n parent-> детские ассоциации

Question

Я постараюсь объяснить это лучшее, что я могу. У меня довольно сложность, пытаясь выяснить эту логику.

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

Итак, примерно, это:

public class MyObject{
     public string Parent { get; set; }
     public string Child { get; set; }
}

То, что я пытаюсь понять, - это то, как построить это в простое управление TreeView. Мне нужно создать отношения, но я не могу понять, как, потому что они могут быть смешаны. Я, вероятно, могу объяснить это лучше с тем, что должно выглядеть дерево:

Так что, если у меня есть следующие предметы внутри моей коллекции:

0. Parent: "A", Child: "B"
1. Parent: "B", Child: "C"
2. Parent: "B", Child: "D"

Я хотел бы, чтобы мое дерево выглядеть так:

-A
--B
---C
-A
--B
---D
-B
--C
-B
--D

Как я могу сделать это в C #? Мне понадобится его поддержку до N отношения, поскольку у нас есть некоторые филиалы, я бы ожидал достичь примерно 50 узлов.

Answer 1

ОБНОВИТЬ

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

Я хочу держать его в записи, что использование рекурсивной структуры данных делает это проще:

public class MyRecursiveObject
{
    public MyRecursiveObject Parent { get; set; }
    public string Name { get; set; }
    public List<MyRecursiveObject> Children { get; set; }
}

Вы увидите очень четко Зачем Это легче после прочтения кода реализации ниже:

private void PopulateTree(IEnumerable<MyObject> items)
{
    var groupedItems =
        from i in items
        group i by i.Parent into g
        select new { Name = g.Key, Children = g.Select(c => c.Child) };
    var lookup = groupedItems.ToDictionary(i => i.Name, i => i.Children);
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, Enumerable.Empty<string>(), parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        IEnumerable<string> newPath = path.Concat(new string[] { name });
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
    }
    else
    {
        TreeNode parentNode = null;
        foreach (string item in path)
            parentNode = AddTreeNode(parentNode, item);
        AddTreeNode(parentNode, name);
    }
}

private TreeNode AddTreeNode(TreeNode parent, string name)
{
    TreeNode node = new TreeNode(name);
    if (parent != null)
        parent.Nodes.Add(node);
    else
        treeView1.Nodes.Add(node);
    return node;
}

Прежде всего, я понял, что словарь будет содержать ключевые ключи для промежуточных узлов, а также только корневых узлов, поэтому нам не нужны две рекурсивные звонки в рекурсивном AddToTree метод, чтобы получить узлы «B» в виде корней; начальная прогулка в PopulateTree Метод уже делает это.

Что мы делать нужно охранять против добавления листовых узлов в начальной прогулке; Используя рассматриваемую структуру данных, они обнаруживаются, проверяя, есть ли ключ в родительском словаре. С рекурсивной структурой данных это было бы легче: просто проверить Parent == null. Отказ Но рекурсивная структура не то, что у нас есть, поэтому код выше, что мы должны использовать.

То AddTreeNode В основном является методом утилиты, поэтому нам не нужно повторять эту нулю проверять логику позже.

Настоящее безобразие во втором, рекурсивный AddToTree метод. Поскольку мы пытаемся создать уникальную копию каждого поддерева, мы не можем просто добавить узел дерева, а затем повторить этот узел в качестве родителя. «А» только один ребенок здесь, «B», но «B» имеет двое детей, «C» и «D». Там должно быть два копии «А», но нет способа узнать об этом, когда «A» первоначально передается на AddToTree метод.

Так что мы на самом деле должны делать, это не создавать Любые узлы до завершающей стадии и храните временный путь, для которого я выбрал IEnumerable<string> потому что это неизменно и, следовательно, невозможно запутаться. Когда добавить больше детей, этот метод просто добавляет к пути и рекурсирует; Когда больше нет детей, он проводит весь сохраненный путь и добавляет узел для каждого.

Это очень сильно неэффективно, потому что мы сейчас создаем новую перечисленную на каждом вызове AddToTree. Отказ Для большого количества узлов, вероятно, разжевывают много памяти. Это работает, но было бы намного эффективнее с рекурсивной структурой данных. Используя примерную структуру в верхней части, вам не нужно было бы сохранить путь или создать словарь; когда нет детей, просто поднимайтесь по пути в while петля с использованием Parent ссылка.

В любом случае, я думаю, это академик, потому что это не рекурсивный объект, но я думал, что стоит указать в любом случае как что-то, чтобы иметь в виду для будущих дизайнов. Код выше буду Произведите именно результаты, которые вы хотите, я прошел вперед и проверил его на реальном дереве.

---

Обновление 2. - так оказывается, что версия выше довольно жестоко относится к памяти / стекам, скорее всего, результат создания всех тех IEnumerable<string> экземпляры. Хотя это не отличный дизайн, мы можем удалить эту конкретную проблему, меняясь на мультипликацию List<string>. Отказ Следующий фрагмент показывает различия:

private void PopulateTree(IEnumerable<MyObject> items)
{
    // Snip lookup-generation code - same as before ...

    List<string> path = new List<string>();
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, path, parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        path.Add(name);
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
        path.Remove(name);
    }
    // Snip "else" block - again, this part is the same as before ...
}

Answer 2

Как рубенс, я попробовал оба, но немного лучше, я думаю Универсальная коллекция деревьев

Эта коллекция дерева получила хорошую функциональность, чтобы двигаться вокруг дерева, прочитайте всю статью

образец со ссылкой выше

Static Class Module1
{

    public static void Main()
    {
        Common.ITree<myObj> myTree = default(Common.ITree<myObj>);
        myObj a = new myObj("a");
        myObj b = new myObj("b");
        myObj c = new myObj("c");
        myObj d = new myObj("d");

        myTree = Common.NodeTree<myObj>.NewTree;
        myTree.InsertChild(a).InsertChild(b).InsertChild(c).Parent.Parent.InsertNext(a).InsertChild(b).InsertChild(d).Parent.Parent.InsertNext(b).InsertChild(c).Parent.InsertNext(b).InsertChild(d);

        Console.WriteLine(myTree.ToStringRecursive);

        Console.ReadKey();
    }
}

Class myObj
{
    public string text;

    public myObj(string value)
    {
        text = value;
    }

    public override string ToString()
    {
        return text;
    }
}

было бы именно то, что вы только что показали

-
- b
--- C.
-
- b
--- D.
-Б.
--C.
-Б.
-

Answer 3

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

Во-первых, вы будете счастливее, если вы разработаете структуру данных для ваших узлов, которые искренне рекурсивят:

public class Node
{
   public Node Parent { get; private set; }
   public IEnumerable<Node> Children { get; private set; }
   public bool HasChildren { get { return Children.Count() > 0; } }

   public Node()
   {
      Children = new List<Node>();
   }
}

Твой MyObject Класс представляет родительские / дочерние отношения между строковыми значениями. До тех пор, пока вы можете реализовать FindChildren() Метод, который возвращает значения дочерних значений для данного родительского значения, используя этот класс для рационализации родительских / дочерних отношений, является простым:

public string Value { get; set; }
public static Node Create(string parentKey)
{
   Node n = new Node();
   n.Value = parentKey;
   foreach (string childKey in FindChildren(parentKey))
   {
      Node child = n.Children.Add(Node.Create(childKey));
      child.Parent = n;
   } 
   return n;
}

Просто реализовать свойство, которое возвращает потомки узла:

public IEnumerable<Node> Descendants
{
   get
   {
      foreach (Node child in Children)
      {
         yield return child;
         foreach (Node descendant in child.Descendants)
         {
            yield return descendant;
         }
      }
   }
}

Добавить А. Node Для дерева вам нужны два метода. (Обратите внимание, что это не методы Node Класс!) Я сделал их перегрузки, но аргумент может быть сделан для того, чтобы дать им разные имена:

public void AddNode(Node n, TreeView tv)
{
   TreeNode tn = tv.Nodes.Add(n.Value);
   tn.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

public void AddNode(Node n, TreeNode parent)
{
   TreeNode tn = parent.Nodes.Add(n.Value);
   parent.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

Я устанавливаю Tag на каждом TreeNode так что вы можете найти свой путь обратно на оригинал Node.

Так что для инициализации вашего TreeView Из списка родительских клавиш верхнего уровня вам нужен такой метод:

public void PopulateTreeView(IEnumerable<string> parents, TreeView t)
{
   foreach (string parentKey in parents)
   {
      Node n = Node.Create(parentKey);
      AddNode(n, t);
      foreach (Node descendant in n.Descendants)
      {
         if (n.HasChildren)
         {
            AddNode(descendant, t);
         }
      }
   }
}

Редактировать:

Я не совсем понял, как твой MyObject класс работает; Я думаю, что делаю сейчас, и я редактировал это соответственно.