从路径字符串中获取树状结构 [英] Get a tree like structure out of path string

问题描述

我被困住了 2 天，因为我不会用指针和递归来坚定.我有一个类似结构的路径数组，可以说:

I am stuck since 2 days, as I am not to firm with pointers and recursion. I have an array of path like structures, lets say:

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

使用这样的数据结构:

 type Node struct {
   Name     string `json:"name"`
   Children []Node `json:"children"`
}

我想以这样的方式结束:

I would like to end up with something like this:

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

我尝试用递归来构建它，它工作得很好，但只适用于一个字符串(例如a/b/c")，只要我尝试实现一些应该添加缺失节点的东西(g" in "a/b/g") 到一棵树我被卡住了.

I tried to build it with a recursion, which works kind of fine, but only for one string (e.g. "a/b/c"), as soon as I try to implement something which should add missing nodes ("g" in "a/b/g") to a tree I am stuck.

我有类似的东西:

func appendChild(root Node, children []string) Node {
   if len(children) == 1 {
      return Node{children[0], nil}
   } else {
      t := root
      t.Name=children[0]
      t.Children = append(t.Children, appendChild(root, children[1:]))
      return t
   }
}

有人能给我指出一个有效的解决方案吗?

Could someone point me to an efficient solution?

推荐答案

https://play.golang.org/p/9pER5cwChF

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
}

示例输出(请注意，我在 children 字段上使用了 omitempty，因为我不喜欢 JSON 中的 null 条目):

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"
    }]
}]

与您的版本显着不同:

• 它对节点列表而不是单个节点的子节点进行操作.这很重要，因为您的版本假定所有树都具有相同的单个根节点 (a)，但实际情况可能并非如此.在您的版本中处理这个问题的唯一方法是在根目录下有一个假"节点.
• 它不会重用输入节点.这是您的代码的主要问题之一.如果 len(children) > 1，则更新输入节点的名称，附加到它的子节点，然后递归.这意味着切片的每个先前级别都成为子级的一部分.您需要创建一个新节点.
• 它实际上是在搜索树.您不是在搜索树以查看被插入的项目是否已经存在，因此您复制节点(特别是节点 b)

• It operates on a list of nodes instead of the children of a single node. This is important, as your version assumes that all of the trees have the same single root node (a), when this might not be the case. The only way to handle that in your version is to have a "fake" node at the root.
• It does NOT reuse the input node. This is one of the primary problems with your code. If len(children) > 1, you update the input node's name, append to it's children, then recurse. This means that every prior level of the slice becomes part of the children. You need to create a new node instead.
• It actually searches the tree. You're not searching the tree to see if the item being inserted already exists, so you duplicate nodes (specifically, node b)

这篇关于从路径字符串中获取树状结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！