Построить древовидную структуру из родительских / дочерних пар в GO

Question

Я пытаюсь построить древовидную структуру из родительского x дочернего набора данных в Go. В конечном итоге данные будут получены из таблицы 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.

Это моя попытка решить эту проблему. Он работает для root элементов и дочерних элементов первого уровня, однако не глубже go, чем в дереве. Насколько я понимаю, мне нужен рекурсивный l oop, чтобы достичь того, чего я хочу, но у меня возникают проблемы при разработке более глубоких уровней.

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, но ответы либо не go выше первого уровня или просто не решают проблему в целом.

Answer 1

Во-первых, вы никогда не должны использовать указатели на кусочки, если вам это не нужно. Более типично назначить возвращаемое значение переменной, например mySlice = sliceReturningFunction().

Я не уверен, каковы все требования здесь, но одно решение может быть:

1. Построить карту отношений родитель-потомок (map[int][]int).
2. Передать отношение root -уровня функции, которая рекурсивно создает категории.

Вот пример рекурсивного функция. Обратите внимание, что он возвращает новый фрагмент, а не изменяет указатель.

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
}

Я добавил полный пример на игровой площадке . Это не проверено, и я уверен, что есть лучшие решения, но это просто и может дать вам хотя бы некоторые идеи. Если у вас будут тысячи узлов, и к ним часто обращаются, вам нужно оптимизировать не только код Go.