Создайте плоский список из дерева, упорядоченного по заказу дерева

Question

Я работаю над C#, и я ищу простой способ взять список, представляющий дерево, и поместить дерево в список с тем же порядком, что и в дерево.

У меня есть 4 свойства для каждого узла:
* ID
* ParentID,
* СтартПослед
* Имя

public class MyNode 
{ 
    public int ID{get;set;} 
    public int ParentID{get;set;} 
    public int SeqID{get;set;} 
    public string Name{get;set;} 
} 

И я есть коллекция MyNode:

List<MyNode> FlatListOfNodes{get;set;} 

Я ищу что-то, что будет выглядеть так:
FlatListOfNodes.OrderBy(something).DoAnotherThing1(somthing)....

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

, например, если будет это дерево:

-- Parent1 
    -- Child 1.1 
    -- Child 1.2 
     -- grandson 1.2.1 
     -- grandson 1.2.2 
     -- grandson 1.2.3 
    -- Child 1.3 
-- Parent2 
    -- Child 2.1 
    -- Child 2.2 
     -- grandson 2.2.1 
     -- grandson 2.2.2 
     -- grandson 2.2.3 
    -- Child 2.3 
     -- grandson 2.3.1 
     -- grandson 2.3.2 

Я хочу, чтобы представить его в виде плоского списка в том же порядке.

в этом примере:

• Parent1 есть ID = 32, ParentID = -1, SeqID = 1, Name = "Parent1"
• Child1.2 есть ID = 412, ParentID = 32, SeqID = 2, Name = "Child1.2"
• внук 1.2.1 есть ID = 231, ParentID = 412, SeqID = 1, Name = "внук 1.2.1"
• Parent2 будет иметь ID = 345, ParentID = -1, SeqID = 2, Name = "Parent2"
• Child2.3 с ID = 785, ParentID = 345, SeqID = 3, Name = "Child 2.3"
• Внук 2.3.1 будет иметь ID = 854, ParentID = 785, SeqID = 1, Name = "внуку 2.3.1"

Что такое лучший способ сделать это?
Есть ли способ сделать это с помощью linq?

Спасибо!

Answer 1

Ваше дерево может быть обобщено как m-ary tree. Учитывая, что ваш плоский список можно рассчитать, выполнив первый прогон глубины (DFT) этого дерева. Я подозреваю, что это будет быстрее, поскольку LINQ не предполагает, что ваша структура данных имеет определенную структуру. Here's a quick article on DFT for binary search trees - ДПФ для м-арных деревьев является абстракцией этой концепции.

Кажется, нет никакого естественного упорядочения каких-либо ваших переменных состояния. Вам придется придумать некоторые способы нарушения связей между детьми (например, почему Parent1 посетил до Parent2 - какой-то компаратор сказал алгоритму сначала посетить Parent1). Сравнение может быть основано на чем-то простом, таком как порядок генерации (например, самый старший ребенок). Как упоминается в комментарии ниже, сравните SeqID, чтобы выбрать следующий узел фокусировки для повторного включения.

Answer 2

Вы можете сделать это за два прохода. Во-первых, вы создаете словарь узлов, каждый из которых имеет список дочерних элементов.

class TreeNode 
{ 
    public MyNode NodeData; 
    public List<MyNode> Children = new List<MyNode>(); 
} 

Например:

Dictionary<int, MyNode> nodesDict = new Dictionary<int, MyNode>(); 
// add the parent node 
nodesDict.Add(-1, new TreeNode{NodeData = new MyNode{ID=1, ParentID=0, SeqID=1, Name="Root"}}); 

// now go through the original list of nodes 
foreach (var node in NodesList) 
{ 
    // If there is an entry for this node already in the dictionary, 
    // then update its NodeData. 
    // Otherwise create a new entry. 
    TreeNode dictNode; 
    if (nodesDict.TryGetValue(node.ID, out dictNode)) 
    { 
     dictNode.NodeData = node; 
    } 
    else 
    { 
     // add this node to the dictionary 
     dictNode = new TreeNode{NodeData = node};   
     nodesDict.Add(node.ID, dictNode); 
    } 

    // find this node's parent, and add the node to the child list 
    // if the node's parent doesn't exist, add it 
    TreeNode parentNode; 
    if (!nodesDict.TryGetValue(node.ParentID, out parentNode)) 
    { 
     // Parent doesn't yet exist. 
     // Create an entry for it. 
     parentNode = new TreeNode(); 
     nodesDict.Add(node.ParentID, parentNode); 
    } 
    // Add this node to the parent's children 
    parentNode.Children.Add(node); 
} 

Теперь то, что у вас есть словарь, который содержит запись для каждого узла дерева, и узлы дерева знают, что их дети. На данный момент все, о чем вы заботитесь, это узел с идентификатором -1. Оттуда можно добираться до всех остальных узлов.

var root = nodesDict[-1]; 
var children = root.Children.OrderBy(n -> n.SeqID); 
OutputNodes(children); 

И OutputNodes метод может рекурсивно посещать детей, чтобы построить плоский список:

List<MyNode> FlatList = new List<MyNode>(); 

void OutputNodes(IEnumerable<TreeNode> nodes) 
{ 
    foreach (var node in nodes) 
    { 
     FlatList.Add(node); 
     // and then the children 
     var orderedChildren = node.Children.OrderBy(n -> n.SeqID); 
     OutputNodes(orderedChildren); 
    } 
} 

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