Построение дерева из списка с помощью рекурсии

Question

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

Input[] inputs = new Input[] 
{ 
    new Input(1), 
    new Input(3,1), 
    new Input(19,3), 
    new Input(22,1), 
    new Input(4,1), 
    new Input(5,22), 
}; 

Вот декларация для BuildTree(), которая в настоящее время не работает:

public TreeNode BuildTree(IEnumerable<Input> inputs, TreeNode parentNode = null) 
{ 
    List<Input> nodes = inputs.ToList<Input>(); 

    foreach (Input node in nodes) 
    { 
     TreeNode newNode = new TreeNode(node.Id); 
     if (parentNode == null) 
     { 
      parentNode = BuildTree(nodes, newNode); 
     } 
     else 
     { 
      parentNode.AddChild(newNode); 
     } 
    } 

    return parentNode; 
} 

Вот вызов BuildTree:

TreeNode rootNode = BuildTree(inputs); 

Так BuildTree функция должна вернуть корень дерева после его создания. Я пробовал перебирать входные данные. Я попытался удалить первый вход из списка с каждой итерацией. Я не могу это понять. Любая помощь будет принята с благодарностью! Спасибо!

Answer 1

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

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

public TreeNode BuildTree(IEnumerable<Input> inputs) 
{ 
    TreeNode rootNode = null; 
    // Build a dictionary to store each input and its node 
    var dict = inputs.ToDictionary(
     input => input.Id, 
     input => new { Input = input, Node = new TreeNode(input.Id.ToString()) }); 

    // Iterate through the nodes and build relationship among them 
    foreach(var value in dict.Values) 
    { 
     var input = value.Input; 
     if(input.ParentId != null) 
     { 
      dict[(int)input.ParentId].Node.Nodes.Add(value.Node); 
     } 
     else 
     { 
      rootNode = value.Node; 
     } 
    } 
    return rootNode; 
}