How to efficiently construct a tree-like structure from an array of path strings representing a file system hierarchy?

How to Construct a Tree-Like Structure from a Path String Array

Introduction:
Given an array of strings representing file paths, we aim to construct a tree-like data structure reflecting the directory hierarchy. Each string in the array represents a complete path from the root directory to a specific file or directory.

Recursive Approach with Child List:
To build the tree recursively, we need to traverse the path strings from left to right, splitting them into components. We can represent the tree using a Node struct with a name and a slice of child nodes.

<code class="go">type Node struct {
    Name     string
    Children []Node
}</code>

The key insight is to operate on a list of nodes rather than the children of a single node. This allows us to handle multiple trees with different root nodes.

<code class="go">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
}</code>

1. Check if the first component (names[0]) exists in the current list of nodes (root).
2. If not, add a node with this name to the list.
3. Recursively call AddToTree on the updated list, passing the remaining components of the path.

Example:
For the input path strings:

<code class="go">s := [...]string{"a/b/c", "a/b/g", "a/d"}</code>

The function AddToTree produces the following tree structure:

<code class="json">{
 "name": "a",
 "children": [
     {
      "name": "b",
      "children": [
        {
         "name": "c"
        },
        {
         "name": "g"
        }
      ]
    },
    {
     "name": "d",
     "children": []
    }
  ]
}</code>

Advantages Over the Original Approach:

1. Operates on a list of nodes, allowing for multiple trees with different root nodes.
2. Creates new nodes instead of reusing the input node, ensuring that each level of the tree is distinct.
3. Searches the tree to prevent duplication of nodes.

The above is the detailed content of How to efficiently construct a tree-like structure from an array of path strings representing a file system hierarchy?. For more information, please follow other related articles on the PHP Chinese website!