最近编写员工分组的组织架构树,记录一下两种方式:
递归框架
递归方法优缺点:
优点:代码较少;
缺点:性能较差;
树函数(列表,父ID) ret = [] for 节点 in 列表: if 节点的parent_id 等于 父ID 节点.children = 获取树(列表, 节点ID) ret = append(ret,节点) return ret
package main import ( "encoding/json" "fmt" ) type Node struct { Id int `json:"id"` ParentId int `json:"parent_id"` Name string `json:"name"` Children []*Node `json:"children"` } func getTreeRecursive(list []*Node, parentId int) []*Node { res := make([]*Node, 0) for _, v := range list { if v.ParentId == parentId { v.Children = getTreeRecursive(list, v.Id) res = append(res, v) } } return res } func main() { list := []*Node{ {4, 3, "ABA", nil}, {3, 1, "AB", nil}, {1, 0, "A", nil}, {2, 1, "AA", nil}, } res := getTreeRecursive(list, 0) bytes, _ := json.MarshalIndent(res, "", " ") fmt.Printf("%s\n", bytes) }
迭代框架
本质是创建一条引用链,将所有的节点串起来
获取树(列表,父ID) memo = {} for 节点 in 列表: //构造memo给节点的父ID查找追加节点用 if 节点ID in memo: 节点.children = memo[节点ID].children //之前构造的children数组覆盖当前节点的children memo[节点ID] = 节点 else 节点.children = [] memo[节点ID] = 节点 //给像父对象的children追加 if 节点父ID in memo: memo[节点父ID].children.add(memo[节点ID]) //追加当前构造的ID节点 else: memo[节点父ID] = {'children':[memo[节点ID]]} //初始化父对象再追加 return memo[父ID].children
package main import ( "encoding/json" "fmt" ) type Node struct { Id int `json:"id"` ParentId int `json:"parent_id"` Name string `json:"name"` Children []*Node `json:"children"` } func getTreeIterative(list []*Node, parentId int) []*Node { memo := make(map[int]*Node) for _, v := range list { if _, ok := memo[v.Id]; ok { v.Children = memo[v.Id].Children memo[v.Id] = v } else { v.Children = make([]*Node, 0) memo[v.Id] = v } if _, ok := memo[v.ParentId]; ok { memo[v.ParentId].Children = append(memo[v.ParentId].Children, memo[v.Id]) } else { memo[v.ParentId] = &Node{Children: []*Node{memo[v.Id]}} } } return memo[parentId].Children } func main() { list := []*Node{ {4, 3, "ABA", nil}, {3, 1, "AB", nil}, {1, 0, "A", nil}, {2, 1, "AA", nil}, {5, 3, "ABB", nil}, } res := getTreeIterative(list, 0) bytes, _ := json.MarshalIndent(res, "", " ") fmt.Printf("%s\n", bytes) }