golang扁平数据列表转化为树状结构

在数据表中，数据是以一条一条，这种扁平化的数据保存的，然后通过外键这种形式关联起来，如果是一个树形结构，在扁平化的一维列表中 是这个样子的，

扁平的为一维列表的树状结构

var items = []ItemType{
        {Id: 1, Pid: 0,  Content: "1"},
        {Id: 2, Pid: 1,  Content: "1-2"},
        {Id: 3, Pid: 1,  Content: "1-3"},
        {Id: 4, Pid: 3,  Content: "1-3-4"},
        {Id: 5, Pid: 0,  Content: "5"},
        {Id: 6, Pid: 5,  Content: "5-6"},
        {Id:7 , Pid: 6,  Content: "5-6-7"},
        {Id: 8, Pid: 6,  Content: "5-6-8"},
    }
复制代码

像这样的数据是可以保存在数据库中的，又通过外键的关联描述出了一个树状结构。那么把扁平的一维数据列表转化为树下状，大概是这样子:

package main
import (
    "encoding/json"
    "fmt"
)

type ItemType struct {
    Content string
    Pid     int64
    Id      int64
}
type TreeItem struct {
    ItemType
    Children []*TreeItem
}
type IdMapTreeType map[int64]*TreeItem

func main() {
    var items = []ItemType{
        {Id: 1, Pid: 0,  Content: "1"},
        {Id: 2, Pid: 1,  Content: "1-2"},
        {Id: 3, Pid: 1,  Content: "1-3"},
        {Id: 4, Pid: 3,  Content: "1-3-4"},
        {Id: 5, Pid: 0,  Content: "5"},
        {Id: 6, Pid: 5,  Content: "5-6"},
        {Id:7 , Pid: 6,  Content: "5-6-7"},
        {Id: 8, Pid: 6,  Content: "5-6-8"},
    }
    var tree []*TreeItem
    idMapTreeItem := make(IdMapTreeType)
    for _, item := range items {
        var treeItem TreeItem
        treeItem.Id = item.Id
        treeItem.Pid = item.Pid
        treeItem.Content = item.Content
        // 根节点收集
        if item.Pid == 0 {
            tree = append(tree, &treeItem)
        } else {
            // 子节点收集
            idMapTreeItem[item.Pid].Children = append(idMapTreeItem[item.Pid].Children, &treeItem)
        }
        // 把节点映射到map表
        idMapTreeItem[item.Id] = &treeItem
    }
    jsonRes, _ := json.Marshal(tree)
    fmt.Println(string(jsonRes))
}
复制代码

列表转化为树结构

[
  {
    "Content": "1",
    "Pid": 0,
    "Id": 1,
    "Children": [
      {
        "Content": "1-2",
        "Pid": 1,
        "Id": 2,
        "Children": null
      },
      {
        "Content": "1-3",
        "Pid": 1,
        "Id": 3,
        "Children": [
          {
            "Content": "1-3-4",
            "Pid": 3,
            "Id": 4,
            "Children": null
          }
        ]
      }
    ]
  },
  {
    "Content": "5",
    "Pid": 0,
    "Id": 5,
    "Children": [
      {
        "Content": "5-6",
        "Pid": 5,
        "Id": 6,
        "Children": [
          {
            "Content": "5-6-7",
            "Pid": 6,
            "Id": 7,
            "Children": null
          },
          {
            "Content": "5-6-8",
            "Pid": 6,
            "Id": 8,
            "Children": null
          }
        ]
      }
    ]
  }
]
复制代码

原理就是每一条数据在树中都有一个特定的位置，数据项是根节点则直接加入到根节点中， 并注册id映射到它的内存地址(指针)，
如果不是根节点，则通过它的上级pid在映射表中把上级的内存地址拿到并把数据写进去,并也是一样把自己注册到映射表中。然后就还原出来了。
文章转载自《重学golang.算法.# 扁平数据列表转化为树状结构》