如何在Golang中将具有父字段的对象的扁平列表转换为嵌套的树状数组结构

huangapple
go评论113阅读模式
英文:

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结构？

  1. type EmployeeNode struct {
  2.     UserName string
  3.     ReportTo string
  4.     Children []EmployeeNode
  5. }
  1. var input []EmployeeNode = [
  2.     {
  3.         UserName: "Bob Wang",
  4.         ReportTo: "",
  5.         Children: []EmployeeNode{},
  6.     },
  7.     {
  8.         UserName: "Jim Halpert",
  9.         ReportTo: "Bob Wang",
  10.         Children: []EmployeeNode{},
  11.     },
  12.     {
  13.         UserName: "Brett Wang",
  14.         ReportTo: "Jim Halpert",
  15.         Children: []EmployeeNode{},
  16.     },
  17.     {
  18.         UserName: "Ryan Wang",
  19.         ReportTo: "Jim Halpert",
  20.         Children: []EmployeeNode{},
  21.     },
  22.     {
  23.         UserName: "Michael Wang",
  24.         ReportTo: "Bob Wang",
  25.         Children: []EmployeeNode{},
  26.     },
  27.     {
  28.         UserName: "Annie Wang",
  29.         ReportTo: "Michael Wang",
  30.         Children: []EmployeeNode{},
  31.     },
  32.     {
  33.         UserName: "Jay Wang",
  34.         ReportTo: "Michael Wang",
  35.         Children: []EmployeeNode{},
  36.     },
  37. ]
  1. // 期望的结果
  2. var root EmployeeNode = EmployeeNode{
  3.     UserName: "Bob Wang",
  4.     ReportTo: "",
  5.     Children: []EmployeeNode{
  6.         EmployeeNode{
  7.             UserName: "Jim Halpert",
  8.             ReportTo: "Bob Wang",
  9.             Children: []EmployeeNode{
  10.                 EmployeeNode{
  11.                     UserName: "Brett Wang",
  12.                     ReportTo: "Jim Halpert",
  13.                     Children: []EmployeeNode{},
  14.                 },
  15.                 EmployeeNode{
  16.                     UserName: "Ryan Wang",
  17.                     ReportTo: "Jim Halpert",
  18.                     Children: []EmployeeNode{},
  19.                 },
  20.             },
  21.         },
  22.         EmployeeNode{
  23.             UserName: "Michael Wang",
  24.             ReportTo: "Bob Wang",
  25.             Children: []EmployeeNode{
  26.                 EmployeeNode{
  27.                     UserName: "Annie Wang",
  28.                     ReportTo: "Michael Wang",
  29.                     Children: []EmployeeNode{},
  30.                 },
  31.                 EmployeeNode{
  32.                     UserName: "Jay Wang",
  33.                     ReportTo: "Michael Wang",
  34.                     Children: []EmployeeNode{},
  35.                 },
  36.             },
  37.         },
  38.     },
  39. }

请注意，这只是一个示例代码，具体实现可能会根据你的需求和编程语言有所不同。

英文:

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?

  1. type EmployeeNode struct {
  2. 	UserName string 
  3. 	ReportTo string 
  4. 	Children   []EmployeeNode 
  5. }
  1. var input []EmployeeNode = [
  2. {
  3.    UserName: "Bob Wang",
  4.    ReportTo: "",
  5.    Children: []EmployeeNode{}
  6. },
  7. {
  8.    UserName: "Jim Halpert",
  9.    ReportTo: "Bob Wang",
  10.    Children: []EmployeeNode{}
  11. },
  12. {
  13.    UserName: "Brett Wang",
  14.    ReportTo: "Jim Halpert",
  15.    Children: []EmployeeNode{}
  16. },
  17. {
  18.    UserName: "Ryan Wang",
  19.    ReportTo: "Jim Halpert",
  20.    Children: []EmployeeNode{},
  21. },
  22. {
  23.    UserName: "Michael Wang",
  24.    ReportTo: "Bob Wang",
  25.    Children: []EmployeeNode{}
  26. },
  27. {
  28.    UserName: "Annie Wang",
  29.    ReportTo: "Michael Wang",
  30.    Children: []EmployeeNode{}
  31. }, 
  32. {
  33.    UserName: "Jay Wang",
  34.    ReportTo: "Michael Wang",
  35.    Children: []EmployeeNode{}
  36. },
  37. ]
  1. // Expected result
  2. var root EmployeeNode = EmployeeNode{
  3.     UserName: "Bob Wang",
  4.     ReportTo: "",
  5.     Children: []EmployeeNode{
  6.         EmployeeNode{
  7.             UserName: "Jim Halpert",
  8.             ReportTo: "Bob Wang",
  9.             Children: [
  10.                 EmployeeNode{
  11.                     UserName: "Brett Wang",
  12.                     ReportTo: "Jim Halpert",
  13.                     Children: []EmployeeNode{},
  14.                 },
  15.                 EmployeeNode{
  16.                     UserName: "Ryan Wang",
  17.                     ReportTo: "Jim Halpert",
  18.                     Children: []EmployeeNode{},
  19.                 },
  20.             ]
  21.         },
  22.         EmployeeNode{
  23.             UserName: "Michael Wang",
  24.             ReportTo: "Bob Wang",
  25.             Children: [
  26.                 EmployeeNode{
  27.                     UserName: "Annie Wang",
  28.                     ReportTo: "Michael Wang",
  29.                     Children: []EmployeeNode{},
  30.                 },
  31.                 EmployeeNode{
  32.                     UserName: "Jay Wang",
  33.                     ReportTo: "Michael Wang",
  34.                     Children: []EmployeeNode{},
  35.                 },
  36.             ]
  37.         },
  38.     },
  39. }

答案1

得分: 1

应该是这样的：

  1. func list2tree(employees []EmployeeNode) EmployeeNode {
  3.   // 一个用于跟踪每个子树的映射。
  4.   // 使用指向EmployeeInfo结构体的指针，以确保每个结构体只有一个副本。
  5.   subtrees := map[string]*EmployeeNode{}
  6.   
  7.   // 填充映射：每个节点都是自己子树的根节点
  8.   for _, emp := range employees {
  9.     subtrees[emp.ReportTo] = &emp
  10.   }
  11.   
  12.   // 遍历员工列表
  13.   for _, emp := range employees {
  14.     
  15.     // 如果这不是根节点，她向某人汇报
  16.     if emp.ReportTo != "" {
  17.     
  18.       // 查找他们的直接经理
  19.       subtree := subtrees[emp.ReportTo]
  20.       
  21.       // 将他们添加为直接下属
  22.       subtree.Children = append(subtree.Children, emp)
  23.       
  24.     }
  26.   }
  28.   // 最终，树已经完全填充
  29.   // 返回整个树的根节点
  30.   return *subtrees[""]
  31. }

希望对你有帮助！

英文:

Something like this should do you:

  1. func list2tree(employees []EmployeeNode) EmployeeNode {
  3.   // a map, to keep track of each individual subtree.
  4.   // Using a pointer to the EmployeeInfo struct so as to ensure that there's
  5.   // only a single copy of each struct.
  6.   subtrees := map[string]*EmployeeNode{}
  7.   
  8.   // populate the map: every node is the root of its own subtree
  9.   for _, emp := range employees {
  10.     subtrees[emp.ReportTo] = &emp
  11.   }
  12.   
  13.   // iterate over the list of employees
  14.   for _, emp := range employees {
  15.     
  16.     // if this is not the root node, she reports to somebody
  17.     if emp.ReportTo != "" {
  18.     
  19.       // look up their immediate manager
  20.       subtree := subtrees[emp.ReportTo]
  21.       
  22.       // add them as a direct report
  23.       subtree.Children = append(subtree.Children, emp)
  24.       
  25.     }
  27.   }
  29.   // At the end of the day, now, the tree is fully populated
  30.   // return the root node for the entire tree
  31.   return *subtrees[""]
  32. }

huangapple
  • 本文由 发表于 2022年8月10日 03:21:27
  • 转载请务必保留本文链接：https://go.coder-hub.com/73297061.html
  • go
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定