How to Build a Hierarchical Tree Structure from a List of Path Strings?

Transforming a Path Structure into a Tree

Developing a nested data structure from a collection of path strings can pose challenges, especially when dealing with pointers and recursion. Let's investigate a solution to create a hierarchical tree from an array of path structures.

Consider the following example:

s:=[]string {
  "a/b/c",
  "a/b/g",
  "a/d"
}

Our goal is to construct a tree that resembles the following JSON structure:

{
 "name": "a",
 "children": [
     {
      "name": "b",
      "children": [
        {
         "name": "c",
         "children": []
        },
        {
         "name": "g",
         "children": []
        }
      ]
    },
    {
     "name": "d",
     "children": []
    }
  ]
}

To achieve this, we implement a recursive function called AddToTree that takes an existing tree and a list of path segments.

func AddToTree(root []Node, names []string) []Node {
    if len(names) > 0 {
        var i int
        for i = 0; i < len(root); i++ {
            if root[i].Name == names[0] { //already in tree
                break
            }
        }
        if i == len(root) {
            root = append(root, Node{Name: names[0]})
        }
        root[i].Children = AddToTree(root[i].Children, names[1:])
    }
    return root
}

This function traverses the existing tree to determine if the specified node already exists. If it does, it proceeds to the next segment of the path. Otherwise, it creates a new node with the specified name and appends it to the existing tree.

Example output (note that I used omitempty on the children field, because I don't like null entries in my JSONs):

[{
    "name": "a",
    "children": [{
        "name": "b",
        "children": [{
            "name": "c"
        }, {
            "name": "g"
        }]
    }, {
        "name": "d"
    }]
}]

Our solution differs from the original approach in the following key aspects:

• It operates on a list of nodes rather than the children of a single node.
• It creates new nodes instead of reusing existing ones, preventing duplication.
• It checks for existing nodes in the tree, ensuring that each node is added only once.

The above is the detailed content of How to Build a Hierarchical Tree Structure from a List of Path Strings?. For more information, please follow other related articles on the PHP Chinese website!