如何将带有父字段的平面对象列表转换为Golang中嵌套的类似树的数组结构

Question

如果我有一个平面的EmployeeNode结构数组，每个结构都有一个ReportTo字段，那么如何创建一个树状结构，其中树的根由一个EmployeeNode结构表示，而子字段包含一个向根节点报告的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{}
},
]

// 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{},
                },
            ]
        },
    },
}

Answer 1

像这样的事情应该对你有好处：

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[""]
}