Golang:根据id和父id创建嵌套的树形结构数组

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

Golang: Create nested from linear array bassed on id and parent id

问题

我有一个名为data linear的数据,例如:

  • 名称:One,ID:1,父ID:0
  • 名称:One-One,ID:2,父ID:1
  • 名称:One-One-One,ID:3,父ID:2
  • 名称:One-One-Two,ID:4,父ID:2

例如,我从数据库中获取这些数据,但是为了测试逻辑,我使用虚拟数据创建了一个结构。我认为我需要为数据递归创建一个临时索引。我设置了一个条件,如果数据在映射中不存在,我就获取索引,如果数据需要在切片之前追加,我就将其追加到切片中。但是,我认为在递归函数中(下面我展示了它),它不起作用(数据没有被追加)。为什么呢?算法逻辑有什么问题吗?

对于我的结果,有什么正确的解决方案吗?

完整的Golang代码如下:

package main

import (
	"encoding/json"
	"fmt"
)

type Data struct {
	Id       int    `json:"id"`
	ParentId int    `json:"parent_id"`
	Name     string `json:"name"`
}

type Datas []Data

type Response struct {
	Id       int       `json:"id"`
	Name     string    `json:"name"`
	Children Responses `json:"children"`
}

type Responses []*Response

func main() {
	datas := Datas{
		{
			Name: "One",
			Id:   1,
		},
		{
			Name:     "One-One",
			Id:       2,
			ParentId: 1,
		},
		{
			Name:     "One-One-One",
			Id:       3,
			ParentId: 2,
		},
		{
			Name:     "One-One-Two",
			Id:       4,
			ParentId: 2,
		},
	}

	var result Responses
	tempIdx := make(map[int]int)

	for _, val := range datas {
		res := Response{
			Id:   val.Id,
			Name: val.Name,
		}

		if val.ParentId == 0 {
			result = append(result, &res)
			tempIdx[val.Id] = len(result) - 1
			continue
		} else {
			recursive(val.ParentId, result, res, tempIdx)
		}

	}

	json, err := json.Marshal(result)
	if err != nil {
		panic(err)
	}
	fmt.Println(string(json))
}

func recursive(idxParent int, datas Responses, res Response, tempIdx map[int]int) {
	idxData, ok := tempIdx[idxParent]
	if ok {
		recursive(idxData, datas[idxData].Children, res, tempIdx)
	} else {
		datas = append(datas, &res)
		tempIdx[res.Id] = len(datas) - 1
	}
}

Golang Playground中打开。

英文:

I have a data linear of name such as:

  • name: One, Id: 1, ParentId: 0
  • name: One-One, Id: 2, ParentId: 1
  • name: One-One-One, Id: 3, ParentId: 2
  • name: One-One-Two, Id: 4, ParentId: 2

For example this data, I get from the database, but I think to test the logic I make the dummy data to struct.
I think I make a temporary index, for data recursively. I set if data does not exist in a map, and I get index if data has to append for before slice. But, I think in function recursive (i show it bellow), it doesn't work (data not append). Why?
is there any wrong algorithm logic?

And what is the right solution for my result is

[
  {
    "id": 1,
    "name": "One",
    "children": [
      {
        "id": 2,
        "name": "One-One",
        "children": [
          {
            "id": 3,
            "name": "One-One-One",
            "children": null
          },
          {
            "id": 4,
            "name": "One-One-Two",
            "children": null
          }
        ]
      }
    ]
  }
]

Full code in golang:

package main

import (
	"encoding/json"
	"fmt"
)

type Data struct {
	Id       int    `json:"id"`
	ParentId int    `json:"parent_id"`
	Name     string `json:"name"`
}

type Datas []Data

type Response struct {
	Id       int       `json:"id"`
	Name     string    `json:"name"`
	Children Responses `json:"children"`
}

type Responses []*Response

func main() {
	datas := Datas{
		{
			Name: "One",
			Id:   1,
		},
		{
			Name:     "One-One",
			Id:       2,
			ParentId: 1,
		},
		{
			Name:     "One-One-One",
			Id:       3,
			ParentId: 2,
		},
		{
			Name:     "One-One-Two",
			Id:       4,
			ParentId: 2,
		},
	}

	var result Responses
	tempIdx := make(map[int]int)

	for _, val := range datas {
		res := Response{
			Id:   val.Id,
			Name: val.Name,
		}

		if val.ParentId == 0 {
			result = append(result, &res)
			tempIdx[val.Id] = len(result) - 1
			continue
		} else {
			recursive(val.ParentId, result, res, tempIdx)
		}

	}

	json, err := json.Marshal(result)
	if err != nil {
		panic(err)
	}
	fmt.Println(string(json))
}

func recursive(idxParent int, datas Responses, res Response, tempIdx map[int]int) {
	idxData, ok := tempIdx[idxParent]
	if ok {
        // don't work in this "datas[idxData].Children", why?
		recursive(idxData, datas[idxData].Children, res, tempIdx)
	} else {
		datas = append(datas, &res)
		tempIdx[res.Id] = len(datas) - 1
	}
}

Open with Golang Playground

答案1

得分: 0

Slice不是一个数组

在函数中向切片追加元素不会增加原始切片的长度和容量。

change := func(slice []int) {
	slice = append(slice, 3)
}
slice := []int{1, 2}
change(slice)
fmt.Println(slice) 
// 输出: [1 2]

无论如何,即使你修复了切片的问题,你的输出也不会如预期。你基本上使用了一种树数据结构,所以建议使用一些树搜索算法。下面是使用BFS(广度优先搜索)的工作示例:

package main

import (
	"encoding/json"
	"fmt"
)

type Data struct {
	Id       int    `json:"id"`
	ParentId int    `json:"parent_id"`
	Name     string `json:"name"`
}

type Datas []Data

type Response struct {
	Id       int       `json:"id"`
	Name     string    `json:"name"`
	Children Responses `json:"children"`
}

type Responses []*Response

func main() {
	datas := Datas{
		{
			Name: "One",
			Id:   1,
		},
		{
			Name:     "One-One",
			Id:       2,
			ParentId: 1,
		},
		{
			Name:     "One-One-One",
			Id:       3,
			ParentId: 2,
		},
		{
			Name:     "One-One-Two",
			Id:       4,
			ParentId: 2,
		},
	}

	var result Responses
	for _, val := range datas {
		res := &Response{
			Id:   val.Id,
			Name: val.Name,
		}

		var found bool

		// 遍历根节点
		for _, root := range result {
			parent := findById(root, val.ParentId)
			if parent != nil {
				parent.Children = append(parent.Children, res)

				found = true
				break
			}
		}

		if !found {
			result = append(result, res)
		}
	}

	out, err := json.Marshal(result)
	if err != nil {
		panic(err)
	}
	fmt.Println(string(out))
}

func findById(root *Response, id int) *Response {
	queue := make([]*Response, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		nextUp := queue[0]
		queue = queue[1:]
		if nextUp.Id == id {
			return nextUp
		}
		if len(nextUp.Children) > 0 {
			for _, child := range nextUp.Children {
				queue = append(queue, child)
			}
		}
	}
	return nil
}
英文:

Slice is not an array

appending to slice in function doesn't increase length and capacity of original slice.

change := func(slice []int) {
slice = append(slice, 3)
}
slice := []int{1, 2}
change(slice)
fmt.Println(slice) 
// Output: [1 2]

Anyway even if you fix the slice issue your output won't be as expected. You are basically using a Tree data structure so it's recommended to use some of tree searching algorithms. Here's your working example with BFS

package main
import (
"encoding/json"
"fmt"
)
type Data struct {
Id       int    `json:"id"`
ParentId int    `json:"parent_id"`
Name     string `json:"name"`
}
type Datas []Data
type Response struct {
Id       int       `json:"id"`
Name     string    `json:"name"`
Children Responses `json:"children"`
}
type Responses []*Response
func main() {
datas := Datas{
{
Name: "One",
Id:   1,
},
{
Name:     "One-One",
Id:       2,
ParentId: 1,
},
{
Name:     "One-One-One",
Id:       3,
ParentId: 2,
},
{
Name:     "One-One-Two",
Id:       4,
ParentId: 2,
},
}
var result Responses
for _, val := range datas {
res := &Response{
Id:   val.Id,
Name: val.Name,
}
var found bool
// iterate trough root nodes
for _, root := range result {
parent := findById(root, val.ParentId)
if parent != nil {
parent.Children = append(parent.Children, res)
found = true
break
}
}
if !found {
result = append(result, res)
}
}
out, err := json.Marshal(result)
if err != nil {
panic(err)
}
fmt.Println(string(out))
}
func findById(root *Response, id int) *Response {
queue := make([]*Response, 0)
queue = append(queue, root)
for len(queue) > 0 {
nextUp := queue[0]
queue = queue[1:]
if nextUp.Id == id {
return nextUp
}
if len(nextUp.Children) > 0 {
for _, child := range nextUp.Children {
queue = append(queue, child)
}
}
}
return nil
}

huangapple
  • 本文由 发表于 2022年3月11日 14:34:28
  • 转载请务必保留本文链接:https://go.coder-hub.com/71434494.html
匿名

发表评论

匿名网友

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

确定