英文:
How to convert a flat list of objects with parent field, into a nested tree-like array structure in Golang
问题
如果我有一个由EmployeeNode结构组成的平面数组,每个结构都有一个ReportTo字段,我该如何创建一个类似树状结构的结构,其中树的根由一个EmployeeNode结构表示,Children字段包含报告给根节点的EmployeeNodes的列表?例如,给定下面的输入,我该如何转换为根EmployeeNode结构?
type EmployeeNode struct {
UserName string
ReportTo string
Children []EmployeeNode
}
var input []EmployeeNode = [
{
UserName: "Bob Wang",
ReportTo: "",
Children: []EmployeeNode{},
},
{
UserName: "Jim Halpert",
ReportTo: "Bob Wang",
Children: []EmployeeNode{},
},
{
UserName: "Brett Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{},
},
{
UserName: "Ryan Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{},
},
{
UserName: "Michael Wang",
ReportTo: "Bob Wang",
Children: []EmployeeNode{},
},
{
UserName: "Annie Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{},
},
{
UserName: "Jay Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{},
},
]
// 期望的结果
var root EmployeeNode = EmployeeNode{
UserName: "Bob Wang",
ReportTo: "",
Children: []EmployeeNode{
EmployeeNode{
UserName: "Jim Halpert",
ReportTo: "Bob Wang",
Children: []EmployeeNode{
EmployeeNode{
UserName: "Brett Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{},
},
EmployeeNode{
UserName: "Ryan Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{},
},
},
},
EmployeeNode{
UserName: "Michael Wang",
ReportTo: "Bob Wang",
Children: []EmployeeNode{
EmployeeNode{
UserName: "Annie Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{},
},
EmployeeNode{
UserName: "Jay Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{},
},
},
},
},
}
请注意,这只是一个示例代码,具体实现可能会根据你的需求和编程语言有所不同。
英文:
If I have a flat array of EmployeeNode structs each with a ReportTo field, how do I create a tree-like structure where the root of the tree is represented by an EmployeeNode struct, and the Children field contains a list of EmployeeNodes that report to the root node? For example, given the input below, how do I convert to the root EmployeeNode struct?
type EmployeeNode struct {
UserName string
ReportTo string
Children []EmployeeNode
}
var input []EmployeeNode = [
{
UserName: "Bob Wang",
ReportTo: "",
Children: []EmployeeNode{}
},
{
UserName: "Jim Halpert",
ReportTo: "Bob Wang",
Children: []EmployeeNode{}
},
{
UserName: "Brett Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{}
},
{
UserName: "Ryan Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{},
},
{
UserName: "Michael Wang",
ReportTo: "Bob Wang",
Children: []EmployeeNode{}
},
{
UserName: "Annie Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{}
},
{
UserName: "Jay Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{}
},
]
// Expected result
var root EmployeeNode = EmployeeNode{
UserName: "Bob Wang",
ReportTo: "",
Children: []EmployeeNode{
EmployeeNode{
UserName: "Jim Halpert",
ReportTo: "Bob Wang",
Children: [
EmployeeNode{
UserName: "Brett Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{},
},
EmployeeNode{
UserName: "Ryan Wang",
ReportTo: "Jim Halpert",
Children: []EmployeeNode{},
},
]
},
EmployeeNode{
UserName: "Michael Wang",
ReportTo: "Bob Wang",
Children: [
EmployeeNode{
UserName: "Annie Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{},
},
EmployeeNode{
UserName: "Jay Wang",
ReportTo: "Michael Wang",
Children: []EmployeeNode{},
},
]
},
},
}
答案1
得分: 1
应该是这样的:
func list2tree(employees []EmployeeNode) EmployeeNode {
// 一个用于跟踪每个子树的映射。
// 使用指向EmployeeInfo结构体的指针,以确保每个结构体只有一个副本。
subtrees := map[string]*EmployeeNode{}
// 填充映射:每个节点都是自己子树的根节点
for _, emp := range employees {
subtrees[emp.ReportTo] = &emp
}
// 遍历员工列表
for _, emp := range employees {
// 如果这不是根节点,她向某人汇报
if emp.ReportTo != "" {
// 查找他们的直接经理
subtree := subtrees[emp.ReportTo]
// 将他们添加为直接下属
subtree.Children = append(subtree.Children, emp)
}
}
// 最终,树已经完全填充
// 返回整个树的根节点
return *subtrees[""]
}
希望对你有帮助!
英文:
Something like this should do you:
func list2tree(employees []EmployeeNode) EmployeeNode {
// a map, to keep track of each individual subtree.
// Using a pointer to the EmployeeInfo struct so as to ensure that there's
// only a single copy of each struct.
subtrees := map[string]*EmployeeNode{}
// populate the map: every node is the root of its own subtree
for _, emp := range employees {
subtrees[emp.ReportTo] = &emp
}
// iterate over the list of employees
for _, emp := range employees {
// if this is not the root node, she reports to somebody
if emp.ReportTo != "" {
// look up their immediate manager
subtree := subtrees[emp.ReportTo]
// add them as a direct report
subtree.Children = append(subtree.Children, emp)
}
}
// At the end of the day, now, the tree is fully populated
// return the root node for the entire tree
return *subtrees[""]
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论