go - 从GO中的父子对构建树结构

Question

我正在尝试从Go中的父x子数据集构建树结构。最终，数据将来自MySQL表，但是为了简化此示例，我从等式中删除了数据库，而是创建了一个数组。对于“现实生活”解决方案，原理是相同的。

数据源如下所示:

---------------------------    ID      |   Parent---------------------------    1       |       0    2       |       1    3       |       1    4       |       0    5       |       4    6       |       4    7       |       0    8       |       7    9       |       2

The Parent colunm refer back to the ID column forming the parent x child relationship. ID's with parent = 0 are root elements.

这是我解决这个问题的尝试。它适用于根元素和第一级子元素，但是没有比树中更深入的了。
我的理解是，我需要一个递归循环来实现自己想要的功能，但是我无法确定更深层次的内容。

https://play.golang.org/p/6m0YTqe529O

上面数据源的预期输出是一个分层树，如下所示:

(以JSON表示，以方便可视化)。

[{
        "id": 1,
        "child": [{
                "id": 2,
                "child": [{
                    "id": 9
                }]
            },
            {
                "id": 3
            }
        ]
    },
    {
        "id": 4,
        "child": [{
            "id": 5
        }, {
            "id": 6
        }]
    },
    {
        "id": 7,
        "child": [{
            "id": 8
        }]
    }
]

我在S.O上也看到过类似的问题但答案要么不高于第一级，要么不完全解决问题。

Answer 1

首先，除非确实需要，否则永远不要使用指向 slice 的指针。更常见的是为变量分配返回值，例如mySlice = sliceReturningFunction()。

我不确定这里的所有要求是什么，但是一种解决方案可能是:

构建父子关系图(map[int][]int)。

将根级关系传递给递归构建类别的函数。

这是递归函数的示例。请注意，它返回一个新的 slice ，而不是变异一个指针。

func buildCategories(ids []int, relations map[int][]int) []Category {
    categories := make([]Category, len(ids))
    for i, id := range ids {
        c := Category{ID: id}
        if childIDs, ok := relations[id]; ok {
            c.Child = buildCategories(childIDs, relations)
        }
        categories[i] = c
    }
    return categories
}

我添加了 full example on the Playground。它未经测试，我敢肯定会有更好的解决方案，但是它很简单，至少可以给您一些想法。如果您将有成千上万个节点并且经常访问，那么您将需要优化，而不仅仅是Go代码。