Nice & Universal Way to Convert List of Items to Tree

Nice & universal way to convert List of items to Tree

If you want to have universal method you''ll need an additional class:

public class TreeItem<T>
{
    public T Item { get; set; }
    public IEnumerable<TreeItem<T>> Children { get; set; }
}

Then use it with this helper:

internal static class GenericHelpers
{
    /// <summary>
    /// Generates tree of items from item list
    /// </summary>
    /// 
    /// <typeparam name="T">Type of item in collection</typeparam>
    /// <typeparam name="K">Type of parent_id</typeparam>
    /// 
    /// <param name="collection">Collection of items</param>
    /// <param name="id_selector">Function extracting item's id</param>
    /// <param name="parent_id_selector">Function extracting item's parent_id</param>
    /// <param name="root_id">Root element id</param>
    /// 
    /// <returns>Tree of items</returns>
    public static IEnumerable<TreeItem<T>> GenerateTree<T, K>(
        this IEnumerable<T> collection,
        Func<T, K> id_selector,
        Func<T, K> parent_id_selector,
        K root_id = default(K))
    {
        foreach (var c in collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), root_id)))
        {
            yield return new TreeItem<T>
            {
                Item = c,
                Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c))
            };
        }
    }
}

Usage:

var root = categories.GenerateTree(c => c.Id, c => c.ParentId);

Testing:

static void Test(IEnumerable<TreeItem<category>> categories, int deep = 0)
{
    foreach (var c in categories)
    {
        Console.WriteLine(new String('\t', deep) + c.Item.Name);
        Test(c.Children, deep + 1);
    }
}
// ...
Test(root);

Output

Sport
    Balls
    Shoes
Electronics
    Cameras
        Lenses  
        Tripod
    Computers
        Laptops
Empty

C# Convert List to Tree Like Structure

Ok, your problem is in here and is a symptom of your confusing parameter naming:

private void CreateNode(List<CategoryNode> nodes, CategoriesList parent)
{
    foreach (var node in nodes)
    {
        if (node.Id == parent.Id)
        {
            node.Children.Add(new CategoryNode { Id = parent.Id, Name = parent.Name });
        }
        else
        {
            CreateNode(node.Children, parent);
        }
    }
}

This is called when a node isn't a top level node. It's supposed to find the parent and add the new node as a child. But the problem is that the parameter parent is actually the item you are adding. So this:

if (node.Id == parent.Id)

Can never be true. Because you node the node with the Id matching the item you are adding hasn't been added yet! There is no node in nodes that matches the Id of the item you are adding (unless your list can contain duplicate id's, which I'm assuming isn't the case)

It should be something like:

if (node.Id == parent.ParentId)

Which wouldn't have tripped you up if you'd name the second parameter to CreateNode something like item or newNode, or anything other than parent.

Here's a fiddle that seems to work correctly.

How to efficiently build a tree from a flat structure?

Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly.

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}

Convert a list of objects to a json tree structure

I kept a mapping between indentation and the element to add children to:

// test data
var sourceList = [
    { title: "item-1", indent: "0" },
    { title: "item-2", indent: "0" },
    { title: "item-3", indent: "0", folder: true },
    { title: "item-4", indent: "1" },
    { title: "item-5", indent: "1", folder: true },
    { title: "item-6", indent: "2" },
    { title: "item-7", indent: "2" },
    { title: "item-8", indent: "0" }
];

// init
var targetJson = [];
var roots = { 0 : targetJson};

// actual code:
sourceList.forEach(function(item){
  if (!roots[item.indent].splice) {
    roots[item.indent] = roots[item.indent].children = [];
  }
  roots[item.indent].push(item);
  if (item.folder) {
    roots[+item.indent+1] = item;
  }
});

// output
console.log(targetJson);

PS: i kept the indent property in the object so you can check the results. Feel free to remove it after the item is added. It is inconsequential.

Create a tree from a list of Objects containing paths in Javascript

If you want to use the example code you gave, you just need to change one line:

const [root, ...names] = p.path.split("/");

and add another line:

const id = p.name == name ? p.id : undefined;

and change one final line:

q.push((temp = { id, name, children: [] }));

const paths = ["About.vue", "Categories/Index.vue", "Categories/Demo.vue", "Categories/Flavors.vue", "Categories/Types/Index.vue", "Categories/Types/Other.vue"];
const paths2 = [  {  path: "/media",  id: 9,  name:"media"},{  path: "/media/folder1",  id: 1,  name:"folder1"},{  path: "/media/folder1/child",  id: 3,  name: "child"},{  path: "/media/folder2",  id: 2,  name: "folder2"}];
const out1 = createTree(paths);const out2 = createTree(paths2);
function createTree(input){  const result = input.reduce((r, p, i) => {    if (!(p instanceof Object)){      p = {path: p, id: i};    }    const path = p.path && p.path.substr(0,1) == "/"                ? p.path                : "/" + p.path;    const [root, ...names] = path.split("/");    const last = names[names.length - 1];    names.reduce((q, name) => {      let temp = q.find(o => o.name === name);      //const id = p.name == name ? p.id : undefined;      const id = last == name ? p.id : undefined      if (!temp) {        q.push((temp = { id, name, children: [] }));      }      return temp.children;    }, r);    return r;  }, []);  console.log(result)  return result;}

WPF - Good Way to take a list to a Tree

This will take your list of strings and turn it into a tree suitable for viewing with TreeView as you described:

public IList BuildTree(IEnumerable<string> strings)
{
  return
    from s in strings
    let split = s.Split("/")
    group s by s.Split("/")[0] into g  // Group by first component (before /)
    select new
    {
      Name = g.Key,
      Children = BuildTree(            // Recursively build children
        from s in grp
        where s.Length > g.Key.Length+1
        select s.Substring(g.Key.Length+1)) // Select remaining components
    };
}

This will return a tree of anonymous types, each containing a Name property and a Children property. This can be bound directly to the TreeView by specifying a HierarchicalDataTemplate with ItemsSource="{Binding Children}" and content consisting of a <TextBlock Text="{Binding Name}"> or similar.

Alternatively you could define a tree node class in code if you want additional members or semantics. For example, given this node class:

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

your BuildTree function would be slightly different:

public List<Node> BuildTree(IEnumerable<string> strings)
{
  return (
    from s in strings
    let split = s.Split("/")
    group s by s.Split("/")[0] into g  // Group by first component (before /)
    select new Node
    {
      Value = g.Key,
      Children = BuildTree(            // Recursively build children
        from s in grp
        where s.Length > g.Key.Length+1
        select s.Substring(g.Key.Length+1)) // Select remaining components
    }
    ).ToList();
}

Again this can be bound directly using a HierarchicalDataTemplate. I generally use the first solution (anonymous types) unless I want to do something special with the tree nodes.

Creating Recursive Object from flat list

You could consider using Json.NET.

Json.NET serializes any IDictionary to a JSON key/value pair object - but converting to a Dictionary<string, object> then serializing would be problematic because the .Net dictionary is unordered, and you (probably) want to preserve the relative order of the MenuItem objects when serializing to JSON. Thus it makes sense to manually convert to a tree of JObject objects using LINQ to JSON since Json.NET preserves order of object properties.

Thus you would do:

    public static string CreateJsonFromMenuItems(IList<MenuItem> menuItems)
    {
        return new JObject
        (
            menuItems.ToTree(
                m => (int?)m.SiteMenuId,
                m => m.ParentId, m => new JProperty(m.MenuName, m.Url),
                (parent, child) =>
                {
                    if (parent.Value == null || parent.Value.Type == JTokenType.Null)
                        parent.Value = new JObject();
                    else if (parent.Value.Type != JTokenType.Object)
                        throw new InvalidOperationException("MenuItem has both URL and children");
                    child.MoveTo((JObject)parent.Value);
                })
        ).ToString();
    }

(Note this method throws an exception if a MenuItem has both a non-null Url and a collection of children.)

It uses the following extension methods:

public static class JsonExtensions
{
    public static void MoveTo(this JToken token, JObject newParent)
    {
        if (newParent == null)
            throw new ArgumentNullException();
        var toMove = token.AncestorsAndSelf().OfType<JProperty>().First(); // Throws an exception if no parent property found.
        if (toMove.Parent != null)
            toMove.Remove();
        newParent.Add(toMove);
    }
}

public static class RecursiveEnumerableExtensions
{
    static bool ContainsNonNullKey<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TKey key)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return key == null ? false : dictionary.ContainsKey(key); // Dictionary<int?, X> throws on ContainsKey(null)
    }

    public static IEnumerable<TResult> ToTree<TInput, TKey, TResult>(
        this IEnumerable<TInput> collection,
        Func<TInput, TKey> idSelector,
        Func<TInput, TKey> parentIdSelector,
        Func<TInput, TResult> nodeSelector,
        Action<TResult, TResult> addMethod)
    {
        if (collection == null || idSelector == null || parentIdSelector == null || nodeSelector == null || addMethod == null)
            throw new ArgumentNullException();
        var list = collection.ToList(); // Prevent multiple enumerations of the incoming enumerable.
        var dict = list.ToDictionary(i => idSelector(i), i => nodeSelector(i));
        foreach (var input in list.Where(i => dict.ContainsNonNullKey(parentIdSelector(i))))
        {
            addMethod(dict[parentIdSelector(input)], dict[idSelector(input)]);
        }
        return list.Where(i => !dict.ContainsNonNullKey(parentIdSelector(i))).Select(i => dict[idSelector(i)]);
    }
}

Working fiddle.

---

Related Topics