在 GO 中从父/子对构建树结构

Question

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

数据源如下所示：

----------------------------
    身份证 | 家长
----------------------------
    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
        }]
    }
]

我在 SO 上看到过类似的问题，但答案要么不高于第一级，要么根本不能完全解决问题。

Answer 1

首先，除非确实必要，否则永远不应该使用指向切片的指针。更典型的是为变量分配一个返回值，例如mySlice = sliceReturningFunction()。

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

1. 构建亲子关系图（map[int][]int）。
2. 将根级关系传递给递归构建类别的函数。

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

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
}

我在 Playground 上添加了一个完整的示例。它没有经过测试，我确信有更好的解决方案，但它很简单，至少可以给你一些想法。如果您将拥有数千个节点并且经常访问这些节点，那么您将需要单独优化 Go 代码。