Building a tree structure

Question

I'm trying to build a structure like this :

• Parent 1
  • Child 1
    • Super child 1
  • Child 2
    • Super Child 2
      • Super super Child 2

I don't know how many branches there will be.

I need to build my structure with an array of paths like this :

• Parent1/Child1/SuperChild1
• Parent1/Child2/SuperChild2/SupersuperChild2

I made a Model as following :

public class Person
{
    public string Name { get; set; }
    public string FullPath { get; set; }
    public List<Person> Children { get; set; }
}

I split every paths to an array and then I interate inside with foreach :

string[] list =
{
    "Parent1/Child1/SuperChild1/SupersuperChild1",
    "Parent1/Child1/SuperChild1/SupersuperChild2",
    "Parent2/Child2/SuperChild2/SupersuperChild3",
    "Parent2/Child3/SuperChild3/SupersuperChild4",
    "Parent2/Child3/SuperChild3/SupersuperChild5"
};

var branches = new List<Person>();

foreach (var tag in list)
{
    var tagSlash = tag.Replace("[", "").Replace("]", "/").Split('/');
    Person parent = null;
    foreach (var step in tagSlash)
    {
        Person branch = null;
        if (parent == null && branches.Find(b => b.Name.Equals(step)) == null)
        {
            branch = new Person
            {
                Name = step,
                FullPath = tagSlash.Last().Equals(step) ? tag : null,
                Children = new List<Person>()
            };

            branches.Add(branch);
        }
        else if (parent == null && branches.Find(b => b.Name.Equals(step)) != null)
        {
            branch = branches.Find(b => b.Name.Equals(step));
        }
        else if (parent.Children.Find(c => c.Name.Equals(step)) != null)
        {
            branch = parent.Children.Find(c => c.Name.Equals(step));
        }
        else
        {
            var ancestor = 
            branch = new Person
            {
                Name = step,
                FullPath = tagSlash.Last().Equals(step) ? tag : null,
                Children = new List<Person>()
            };
        }

        parent = branch;
    }
}

The previous code isn't finished because I'm stuck.

Do you have an idea on how to build that structure ?

Thank you.

Answer 1

something recursive? like:

string[] list =
{
    "Parent1/Child1/SuperChild1/SupersuperChild1",
    "Parent1/Child1/SuperChild1/SupersuperChild2",
    "Parent2/Child2/SuperChild2/SupersuperChild3",
    "Parent2/Child3/SuperChild3/SupersuperChild4",
    "Parent2/Child3/SuperChild3/SupersuperChild5"
};

var branches = new List<Person>();

foreach (var tag in list)
{
    var tagSlash = tag.Replace("[", "").Replace("]", "/").Split('/');

    var p1 = branches.FirstOrDefault(x => x.Name == tagSlash[0]);
    if (p1 == null)
    {
        p1 = new Person()
        {
            Name = tagSlash[0],
            FullPath = tagSlash[0]
        };
        branches.Add(p1);
    }

    MakeList.IterateListStep(p1, tagSlash, 1);
}

public static class MakeList
{
    public static void IterateListStep(Person parent, string[] tags, int level)
    {
        if(tags.Length <= level)
            return;

        var pers = parent.Children.FirstOrDefault(x => x.Name == tags[level]);

        if (pers == null)
        {
            pers = new Person()
            {
                Name = tags[level],
                FullPath = parent.FullPath + "//" + tags[level],
            };

            parent.Children.Add(pers);
        }

        IterateListStep(pers, tags, level + 1);

    }
}

Do make sure you initialize your children list

public List<Person> Children { get; set; } = new List<Person>();

Answer 2

Here is tested code :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;
using System.Xml.Linq;
using System.Data;
namespace ConsoleApplication51
{
    class Program
    {
         static void Main(string[] args)
         {
            string[] list =
            {
                "Parent1/Child1/SuperChild1/SupersuperChild1",
                "Parent1/Child1/SuperChild1/SupersuperChild2",
                "Parent2/Child2/SuperChild2/SupersuperChild3",
                "Parent2/Child3/SuperChild3/SupersuperChild4",
                "Parent2/Child3/SuperChild3/SupersuperChild5"
            };

             List<List<string>> people = list.Select(x => x.Split(new char[] {'/'}).ToList()).ToList();

             Person root = Person.BuildTree(people);

        }
    }
    public class Person
    {
        public string Name { get; set; }
        public string FullPath { get; set; }
        public List<Person> Children { get; set; }

        public static Person BuildTree(List<List<string>> people)
        {
            Person root = new Person();
            root.Name = "Root";
            int level = 0;
            BuildTreeRecursive(root, people, level);

            return root;
        }
        public static void BuildTreeRecursive(Person parent, List<List<string>> people, int level)
        {
            var groups = people.GroupBy(x => x[level]).ToList();
            foreach (var group in groups)
            {
                if(parent.Children == null) parent.Children = new List<Person>();
                Person child = new Person();
                parent.Children.Add(child);
                child.Name = group.Key;
                child.FullPath = string.Join("/", group.First().Take(level + 1));
                List<List<string>> descendnats = group.Where(x => x.Count() > level + 1).ToList();
                if (descendnats.Count > 0)
                {
                    BuildTreeRecursive(child, descendnats, level + 1);
                }

            }

        }
    }
 
 
}

Answer 3

I've isolated an INode interface and made a generic tree builder function, compiling here.

public interface INode<T>
{
    public string Name { get; }
    public string FullPath { get; }
    public IList<T> Children { get; }
}

public static class Extensions
{
    public static IEnumerable<T> BuildTrees<T>(
            this IEnumerable<string> paths,
            Func<string, string, T> nodeFactory,
            string delimiter = "/")
            where T : INode<T>
    {
        var nodes = new Dictionary<string, T>();
        var roots = new List<T>();
                
        foreach(var path in paths)
        {
            string fullPath = null;
            T parent = default;
            T node = default;
            
            foreach(var name in path.Split(delimiter))
            {
                var root = false;
                if (fullPath == null)
                {
                    root = true;
                    fullPath = name;
                }
                else
                {
                    fullPath = $"{fullPath}{delimiter}{name}";
                    parent  = node;
                }
                
                if (nodes.ContainsKey(fullPath))
                {
                    node = nodes[fullPath]; 
                }
                else
                {
                    node = nodeFactory(name, fullPath);
                    nodes.Add(fullPath, node);
                    
                    if (root)
                    {
                        roots.Add(node);
                    }
                    else
                    {
                        parent.Children.Add(node);          
                    }
                }
            }
        }
            
        return roots;   
    }
}

Which you could use like this,

public class Person : INode<Person>
{
    public string Name { get; set; }
    public string FullPath { get; set; }
    public IList<Person> Children { get; set; } = new List<Person>();
}

public class Program
{
    public static void Main()
    {
        string[] list =
        {
            "Parent1/Child1/SuperChild1/SupersuperChild1",
            "Parent1/Child1/SuperChild1/SupersuperChild2",
            "Parent2/Child2/SuperChild2/SupersuperChild3",
            "Parent2/Child3/SuperChild3/SupersuperChild4",
            "Parent2/Child3/SuperChild3/SupersuperChild5"
        };

        var roots = list.BuildTrees<Person>(
            (name, fullPath) => new Person { Name = name, FullPath = fullPath });
    }
}

Following your example, roots will be a sequence of the two tress defined in the list, e.g.

                                                |---> SupersuperChild1
Parent1 -------> Child1 -------> SuperChild1 ---|
                                                |---> SupersuperChild2

           |---> Child2 -------> SuperChild2 -------> SupersuperChild3
Parent2 ---|---> Child3 -------> SuperChild3 ---|---> SupersuperChild4
                                                |---> SupersuperChild5

Answer 4

Here's my take on your tree: use class Person : List<Person> to define the tree structure.

public class Person : List<Person>
{
    public string Name { get; private set; }
    private Person Parent { get; set; }
    public string FullPath => $"{(this.Parent == null ? String.Empty : this.Parent.FullPath)}/{this.Name}";
    private Person(string name, Person parent)
    {
        this.Name = name;
        this.Parent = parent;
    }
    public static IEnumerable<Person> Create(params string[] paths) => Person.Create(null, paths);

    private static IEnumerable<Person> Create(Person parent, params string[] paths)
    {
        var list = new List<Person>();
        var people = paths.Select(p => p.Split('/')).GroupBy(x => x[0], x => String.Join("/", x.Skip(1)));
        foreach (var person in people)
        {
            var current = new Person(person.Key, parent);
            var children = Person.Create(parent, person.Where(x => x.Any()).ToArray());
            current.AddRange(children);
            yield return current;
        }
    }
    public override string ToString() =>
        String.Join(Environment.NewLine, this.Flatten(0));
        
    private IEnumerable<string> Flatten(int depth)
    {
        yield return $"{new string('+', depth)}{this.Name}";
        foreach (var x in this.SelectMany(y => y.Flatten(depth + 1)))
        {
            yield return x;
        }
    }
}

Running this is easy:

string[] list =
{
    "Parent1/Child1/SuperChild1/SupersuperChild1",
    "Parent1/Child1/SuperChild1/SupersuperChild2",
    "Parent2/Child2/SuperChild2/SupersuperChild3",
    "Parent2/Child3/SuperChild3/SupersuperChild4",
    "Parent2/Child3/SuperChild3/SupersuperChild5"
};

var people = Person.Create(list);

foreach (var person in people)
    Console.WriteLine(person.ToString());

That outputs:

Parent1
+Child1
++SuperChild1
+++SupersuperChild1
+++SupersuperChild2
Parent2
+Child2
++SuperChild2
+++SupersuperChild3
+Child3
++SuperChild3
+++SupersuperChild4
+++SupersuperChild5