英文:
Get a tree like structure out of path string
问题
我已经翻译了你的代码,如下所示:
我已经卡在这里两天了,因为我对指针和递归不太熟悉。我有一个类似路径的结构的数组,假设如下:
s:=[]string {
"a/b/c",
"a/b/g",
"a/d",
}
使用如下的数据结构:
type Node struct {
Name string `json:"name"`
Children []Node `json:"children"`
}
我想得到如下的结果:
{
"name": "a",
"children": [
{
"name": "b",
"children": [
{
"name": "c",
"children": []
},
{
"name": "g",
"children": []
}
]
},
{
"name": "d",
"children": []
}
]
}
我尝试使用递归来构建它,对于一个字符串(例如"a/b/c")它工作得很好,但是一旦我尝试实现一些应该将缺失的节点("a/b/g"中的"g")添加到树中,我就卡住了。
我有这样的代码:
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
}
}
有人能指导我一个高效的解决方案吗?
英文:
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",
}
With a data structure like this:
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": []
}
]
}
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.
I had something like:
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?
答案1
得分: 6
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] { //已存在于树中
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
条目):
[{
"name": "a",
"children": [{
"name": "b",
"children": [{
"name": "c"
}, {
"name": "g"
}]
}, {
"name": "d"
}]
}]
与你的版本相比的显著差异:
- 它操作的是节点列表,而不是单个节点的子节点。这很重要,因为你的版本假设所有树都有相同的单个根节点(
a
),但实际情况可能并非如此。在你的版本中,唯一处理这种情况的方法是在根节点上有一个“虚假”的节点。 - 它不重用输入节点。这是你的代码的主要问题之一。如果len(children) > 1,你会更新输入节点的名称,将其附加到其子节点,然后递归调用。这意味着每个先前级别的切片都成为子节点的一部分。你需要创建一个_新的_节点。
- 它实际上搜索了树。你没有搜索树以查看要插入的项是否已经存在,因此会重复节点(具体来说,节点b)。
英文:
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
}
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"
}]
}]
Notable difference from your version:
- 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)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论