Golang：根据 id 和 parent id 从线性数组创建嵌套

Question

我有一个数据线性名称，例如：

姓名：一，身份证：1，父母身份证：0
姓名：One-One，身份证：2，父母身份证：1
姓名：One-One-一个，ID：3，ParentId：2
姓名：One-One-两个，Id：4，ParentId：2

例如，此数据是我从数据库中获取的，但我想测试我将虚拟数据构建为结构的逻辑。我想我为数据递归地做了一个临时索引。如果地图中不存在数据，我会设置，如果数据必须附加到切片之前，我会得到索引。但是，我认为在函数递归中（我在下面显示），它不起作用（数据不附加）。为什么？是不是算法逻辑有问题？

我的结果的正确解是

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

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

打开 Golang Playground

Answer 1

切片不是数组

在函数中附加到切片不会增加原始切片的长度和容量。

change := func(slice []int) {
    slice = append(slice, 3)
}
slice := []int{1, 2}
change(slice)
fmt.Println(slice) 
// Output: [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

        // 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
}

Golang：根据 id 和 parent id 从线性数组创建嵌套

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

mapping

nested

go

切片不是数组