将路径字符串转换为树形结构。

huangapple go评论75阅读模式
英文:

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) &gt; 0 {
		var i int
		for i = 0; i &lt; 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):

[{
	&quot;name&quot;: &quot;a&quot;,
	&quot;children&quot;: [{
		&quot;name&quot;: &quot;b&quot;,
		&quot;children&quot;: [{
			&quot;name&quot;: &quot;c&quot;
		}, {
			&quot;name&quot;: &quot;g&quot;
		}]
	}, {
		&quot;name&quot;: &quot;d&quot;
	}]
}]

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)

huangapple
  • 本文由 发表于 2017年5月5日 21:09:37
  • 转载请务必保留本文链接:https://go.coder-hub.com/43805840.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定