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

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

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

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

发表评论

匿名网友

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

确定