golang开发-通用分类树工具库(Category)

通用分类树工具库从设计到使用一篇关于如何设计和实现一个泛型、高性能、易用的分类树处理工具库的完整技术分享本文目录写在前面一、设计目标我们要解决什么问题二、核心数据结构设计三、核心功能实现四、使用示例五、性能优化与注意事项六、总结在业务系统开发中分类树Category Tree是一个非常常见的需求商品分类、组织架构、行政区划、菜单权限…几乎每个项目都会遇到。但每次都要重复写递归找子节点、找父节点、列表转树形结构这些代码不仅繁琐还容易出错。本文将分享一个泛型分类树工具库的设计与实现过程它具备以下特点泛型支持ID 可以是 int 或 string数据可以是任意类型零依赖纯标准库实现开箱即用功能完整列表转树、树转列表、查找子树、查找祖级、查找特定节点类型安全充分利用 Go 泛型编译时保证类型正确一、设计目标我们要解决什么问题在开始写代码之前先明确我们要解决的核心问题1.1 常见的分类树操作需求// 假设我们有这样的分类数据 type Category struct { ID int Pid int Name string } var categories []Category{ {ID: 1, Pid: 0, Name: 数码}, {ID: 2, Pid: 1, Name: 手机}, {ID: 3, Pid: 2, Name: iPhone}, // ... }我们需要的能力列表 → 树将平铺的列表转换为树形结构用于前端展示树 → 列表将树形结构重新平铺用于数据导出查找子树给定一个节点找到它下面所有的子节点含自身查找祖级给定一个节点找到它上面所有的父节点查找节点在树中查找特定 ID 的节点1.2 设计ID 类型不确定可能是 int可以拓展为comparable可能是 string数据类型不确定可能是商品分类可能是部门可能是区域性能要求频繁的递归查找不能太慢易用性API 要简单直观二、核心数据结构设计2.1 Item树的节点定义type ( // keyType 约束 ID 的类型只能是 int 或 string (可以改为comparable) keyType interface { int | string } // Item 树的节点 Item[T keyType, D any] struct { ID T json:id // 节点ID Pid T json:pid // 父节点ID Name string json:name // 节点名称 Raw D json:raw,omitempty,optional // 原始数据 Children []*Item[T, D] json:children,omitempty,optional // 子节点 } )设计思路使用泛型T支持灵活的ID类型D承载任意业务数据Children是切片保持顺序性Raw字段可选用于携带原始业务对象2.2 Category工具类的主体type Category[T keyType, D any] struct { List []*Item[T, D] // 平铺列表原始数据 Trees []*Item[T, D] // 树形结构根节点列表 }设计思路同时维护列表和树避免重复计算列表用于快速查找和祖级追溯树用于树形操作和子节点查找三、核心功能实现3.1 列表转树Conv这是最核心的功能将平铺的列表转换为树形结构。// Conv 转换列表为分类树 func (c *Category[T, D]) Conv(list []D, call func(D) *Item[T, D]) *Category[T, D] { // 1. 转换列表 var length len(list) c.List make([]*Item[T, D], length) for key, item : range list { var v call(item) // 2. 过滤无效ID if any(v.ID) nil { continue } // 处理 string 类型的空值 if tmp, ok : any(v.ID).(string); ok { if tmp { continue } } // 处理 int 类型的零值 if tmp, ok : any(v.ID).(int); ok { if tmp tmp 0 { continue } } c.List[key] v } if len(c.List) 0 { return c } // TODO 如果使用comparable这里要注意区分 comparable/keyType // 3. 构建树形结构根节点ID为0 c.Trees c.makeTrees(T(0)) return c }关键细节通过回调函数让调用方决定如何构建 Item自动过滤无效 IDnil、空字符串、0值根节点的 PID 约定为 0或空字符串3.2 递归构建树makeTrees// makeTrees 递归构建树形结构 func (c *Category[T, D]) makeTrees(pid T) []*Item[T, D] { var children []*Item[T, D] for _, item : range c.List { var value new(Item[T, D]) *value *item // 值拷贝避免相互影响 if value.Pid pid { children append(children, value) // 递归找子节点 value.Children c.makeTrees(value.ID) } } if len(children) 0 { children []*Item[T, D]{} } return children }设计要点值拷贝*value *item确保修改子节点不影响原列表递归终止当没有子节点时返回空切片深度优先先找子节点再找孙节点3.3 树转列表SubFlatList// SubFlatList 树状结构转平铺列表 func (c *Category[T, D]) SubFlatList(trees []*Item[T, D]) []*Item[T, D] { var list []*Item[T, D] for _, item : range trees { var val new(Item[T, D]) *val *item val.Children nil // 平铺时清除子节点 list append(list, val) if len(item.Children) 0 { list append(list, c.SubFlatList(item.Children)...) } } return list }应用场景数据库存储数据导出序列化传输3.4 查找子树FindTrees// FindTrees 查找指定ID下所有子集包含自身 func (c *Category[T, D]) FindTrees(parentIds []T, list []D, call func(D) *Item[T, D]) []T { var trees c.Conv(list, call).Trees if len(trees) 0 { return nil } var ( ids append([]T{}, parentIds...) records []*Item[T, D] ) // 1. 找到所有父节点 for _, id : range parentIds { var item c.FindId(id, trees) if item nil { continue } records append(records, item) } // 2. 收集所有子节点ID for _, item : range records { for _, subItem : range c.SubFlatList(item.Children) { ids append(ids, subItem.ID) } } return ids }典型场景删除分类时找出所有子分类权限继承时找出所有子菜单统计某个节点下所有数据3.5 查找祖级FindParents// FindParents 查找祖级节点 func (c *Category[T, D]) FindParents(ID T) []*Item[T, D] { // 1. 找到当前节点 var current *Item[T, D] for _, item : range c.List { if item.ID ID { current new(Item[T, D]) *current *item } } if current nil { return nil } var data []*Item[T, D]{current} // 2. 检查是否为根节点 if pid, ok : any(current.Pid).(string); ok pid { return data } if pid, ok : any(current.Pid).(int); ok pid 0 { return data } // 3. 递归找父节点并反转顺序从上到下 var ( list append([]*Item[T, D]{current}, c.findParents(current.Pid)...) res make([]*Item[T, D], len(list)) index 0 ) for i : len(list) - 1; i 0; i-- { res[index] list[i] index 1 } return res } func (c *Category[T, D]) findParents(pid T) []*Item[T, D] { var parents []*Item[T, D] for _, item : range c.List { if item.ID pid { var val new(Item[T, D]) *val *item parents append(parents, val) // 递归终止条件 if pid, ok : any(val.Pid).(string); ok pid { break } if pid, ok : any(val.Pid).(int); ok pid 0 { break } parents append(parents, c.findParents(val.Pid)...) } } return parents }返回值设计返回从根到当前节点的路径便于面包屑导航。3.6 查找节点Find/FindId// Find 在树中查找指定ID的节点 func (c *Category[T, D]) Find(ID T) *Item[T, D] { return c.find(ID, c.Trees) } func (c *Category[T, D]) find(ID T, subs []*Item[T, D]) *Item[T, D] { for _, item : range subs { if item.ID ID { return item } if len(item.Children) 0 { if val : c.find(ID, item.Children); val ! nil { return val } } } return nil } // FindId 在指定数据中查找节点支持外部传入数据 func (c *Category[T, D]) FindId(id T, data []*Item[T, D]) *Item[T, D] { for _, item : range data { if item.ID id { return item } if len(item.Children) 0 { var data c.FindId(id, item.Children) if data ! nil { return data } } } return nil }四、使用示例4.1 基础用法package main import ( encoding/json fmt strings ) // 定义业务数据结构 type ProductCategory struct { ID int Pid int Name string Level int // 业务特有字段 } func main() { // 准备数据 var data []ProductCategory{ {ID: 1, Pid: 0, Name: 数码, Level: 1}, {ID: 2, Pid: 0, Name: 家电, Level: 1}, {ID: 3, Pid: 1, Name: 手机, Level: 2}, {ID: 4, Pid: 3, Name: iPhone, Level: 3}, {ID: 5, Pid: 3, Name: 华为, Level: 3}, {ID: 6, Pid: 2, Name: 电视, Level: 2}, } // 创建分类树 var category New[int, ProductCategory]().Conv( data, func(item ProductCategory) *Item[int, ProductCategory] { return Item[int, ProductCategory]{ ID: item.ID, Pid: item.Pid, Name: item.Name, Raw: item, // 携带原始数据 } }, ) // 查看树形结构 treesJSON, _ : json.MarshalIndent(category.Trees, , ) fmt.Printf(树形结构\n%s\n, treesJSON) // 查找 iPhone 的祖级路径 var ( parents : category.FindParents(4) names []string ) for _, p : range parents { names append(names, p.Name) } fmt.Printf(iPhone 的路径%s\n, strings.Join(names, )) // 在树中查找节点 var node category.Find(3) if node ! nil { fmt.Printf(找到节点ID%d, Name%s\n, node.ID, node.Name) } }4.2 实际业务场景// 场景1删除分类时找出所有子分类ID func DeleteCategory(cateID int) { // 获取所有分类从数据库 var allCategories []ProductCategory db.Find(allCategories) var cate New[int, ProductCategory]().Conv( allCategories, func(item ProductCategory) *Item[int, ProductCategory] { return Item[int, ProductCategory]{ID: item.ID, Pid: item.Pid} }, ) // 找出所有要删除的ID包含子分类 var idsToDelete cate.FindTrees([]int{cateID}, allCategories, func(item ProductCategory) *Item[int, ProductCategory] { return Item[int, ProductCategory]{ID: item.ID, Pid: item.Pid} }, ) // 批量删除 db.Where(id IN ?, idsToDelete).Delete(ProductCategory{}) } // 场景2构建前端级联选择器数据 type CascaderOption struct { Value int json:value Label string json:label Children []CascaderOption json:children,omitempty } func BuildCascaderOptions() []CascaderOption { var all []ProductCategory db.Find(all) var cate New[int, ProductCategory]().Conv(all, func(item ProductCategory) *Item[int, ProductCategory] { return Item[int, ProductCategory]{ ID: item.ID, Pid: item.Pid, Name: item.Name, } }, ) return convertToCascader(cate.Trees) } func convertToCascader(trees []*Item[int, ProductCategory]) []CascaderOption { var res []CascaderOption for _, node : range trees { res append(res, CascaderOption{ Value: node.ID, Label: node.Name, Children: convertToCascader(node.Children), }) } return res } // 场景3面包屑导航 func GetBreadcrumb(cateID int) string { var all []ProductCategory db.Find(all) var cate New[int, ProductCategory]().Conv( all, func(item ProductCategory) *Item[int, ProductCategory] { return Item[int, ProductCategory]{ ID: item.ID, Pid: item.Pid, Name: item.Name, } }, ) var ( parents cate.FindParents(cateID) names []string ) for _, p : range parents { names append(names, p.Name) } return strings.Join(names, ) }4.3 字符串类型ID的使用// 适用于 MongoDB、UUID 等场景 type Org struct { ID string Pid string Name string Manager string } func HandleOrg() { var ( orgs []Org{ {ID: root, Pid: , Name: 总公司, Manager: 张三}, {ID: dept1, Pid: root, Name: 技术部, Manager: 李四}, {ID: dept2, Pid: dept1, Name: 前端组, Manager: 王五}, } tree New[string, Org]().Conv( orgs, func(item Org) *Item[string, Org] { return Item[string, Org]{ ID: item.ID, Pid: item.Pid, Name: item.Name, Raw: item, } }, ) ) // 查找前端组的所有上级 var parents tree.FindParents(dept2) for _, p : range parents { fmt.Printf(上级%s负责人%s\n, p.Name, p.Raw.Manager) } // 树转列表 var flatList tree.SubFlatList(tree.Trees) fmt.Printf(平铺后共 %d 个节点\n, len(flatList)) }五、性能优化与注意事项5.1 值拷贝的设计考量// 为什么需要值拷贝 var value new(Item[T, D]) *value *item // 如果不拷贝修改 Children 会影响原列表如果不进行值拷贝对Children的修改会污染原始数据导致多次调用结果不一致。5.2 递归的深度控制对于分类树这种层级有限的场景通常不超过10层递归完全够用。如果担心栈溢出可以改为迭代实现// 迭代版本的查找防止栈溢出 func (c *Category[T, D]) FindIterative(ID T) *Item[T, D] { var stack make([]*Item[T, D], 0) stack append(stack, c.Trees...) for len(stack) 0 { node : stack[len(stack)-1] stack stack[:len(stack)-1] if node.ID ID { return node } if len(node.Children) 0 { stack append(stack, node.Children...) } } return nil }5.3 内存使用优化复用实例复用 Category 实例避免重复构建按需携带Raw如果不需要原始数据可以不传 Raw大数据量处理考虑分批处理或使用数据库递归查询// 优化示例不携带 Raw 数据 var res New[int, ProductCategory]().Conv( data, func(item ProductCategory) *Item[int, ProductCategory] { return Item[int, ProductCategory]{ ID: item.ID, Pid: item.Pid, Name: item.Name, // Raw: item, // 如果不需原始数据省略该字段 } }, )5.4 并发安全当前实现非并发安全如果需要在并发环境使用type SafeCategory[T keyType, D any] struct { mu sync.RWMutex *Category[T, D] } func (s *SafeCategory[T, D]) Conv(list []D, call func(D) *Item[T, D]) *SafeCategory[T, D] { s.mu.Lock() defer s.mu.Unlock() s.Category.Conv(list, call) return s } // 其他方法类似...5.5 常见陷阱循环引用确保数据中没有循环引用A的父是BB的父是AID唯一性同一棵树中ID必须唯一根节点约定根节点的Pid必须是0或空字符串空值处理Conv时会自动过滤无效ID六、总结已实现的功能列表 ----- 树的双向转换查找子树包含自身查找祖级路径查找任意节点泛型支持 int/string ID任意业务数据类型零依赖纯标准库实现设计心得泛型以前需要用 interface{} 类型断言的地方使用泛型既安全又优雅值拷贝要谨慎该拷贝时一定要拷贝不该拷贝时不要浪费内存API 要直观方法命名要符合直觉Find、Conv、SubFlatList源码packagecategoriestype(keyTypeinterface{int|string}Item[T keyType,D any]struct{ID Tjson:idPid Tjson:pidNamestringjson:nameRaw Djson:raw,omitempty,optionalChildren[]*Item[T,D]json:children,omitempty,optional}Category[T keyType,D any]struct{List,Trees[]*Item[T,D]})funcNew[T keyType,D any]()*Category[T,D]{returnCategory[T,D]{}}// Conv 转换列表为分类列表func(c*Category[T,D])Conv(list[]D,callfunc(D)*Item[T,D])*Category[T,D]{varlengthlen(list)c.Listmake([]*Item[T,D],length)forkey,item:rangelist{varvcall(item)ifany(v.ID)nil{continue}iftmp,ok:any(v.ID).(string);ok{iftmp{continue}}iftmp,ok:any(v.ID).(int);ok{iftmp0{continue}}c.List[key]v}iflen(c.List)0{returnc}// 将分类结构化c.Treesc.makeTrees(T(0))returnc}// SubFlatList 结构化分类func(c*Category[T,D])makeTrees(pid T)[]*Item[T,D]{varchildren[]*Item[T,D]for_,item:rangec.List{varvaluenew(Item[T,D])*value*itemifvalue.Pidpid{childrenappend(children,value)value.Childrenc.makeTrees(value.ID)}}iflen(children)0{children[]*Item[T,D]{}}returnchildren}// SubFlatList 子集树状结构转平铺列表func(c*Category[T,D])SubFlatList(trees[]*Item[T,D])[]*Item[T,D]{varlist[]*Item[T,D]for_,item:rangetrees{varvalnew(Item[T,D])*val*item val.Childrennillistappend(list,val)iflen(item.Children)0{listappend(list,c.SubFlatList(item.Children)...)}}returnlist}// FindTrees 查找指定id下所有子集包含自身func(c*Category[T,D])FindTrees(parentIds[]T,list[]D,callfunc(D)*Item[T,D])[]T{vartreesc.Conv(list,call).Treesiflen(trees)0{returnnil}var(idsappend([]T{},parentIds...)records[]*Item[T,D])// 查询for_,id:rangeparentIds{varitemc.FindId(id,trees)ifitemnil{continue}recordsappend(records,item)}for_,item:rangerecords{for_,item:rangec.SubFlatList(item.Children){idsappend(ids,item.ID)}}returnids}func(c*Category[T,D])FindId(id T,data[]*Item[T,D])*Item[T,D]{for_,item:rangedata{ifitem.IDid{returnitem}iflen(item.Children)0{vardatac.FindId(id,item.Children)ifdata!nil{returndata}}}returnnil}// Find 查找idfunc(c*Category[T,D])Find(ID T)*Item[T,D]{returnc.find(ID,c.Trees)}func(c*Category[T,D])find(ID T,subs[]*Item[T,D])*Item[T,D]{for_,item:rangesubs{ifitem.IDID{returnitem}iflen(item.Children)0{ifval:c.find(ID,item.Children);val!nil{returnval}}}returnnil}// FindParents 查找祖级func(c*Category[T,D])FindParents(ID T)[]*Item[T,D]{varcurrent*Item[T,D]for_,item:rangec.List{ifitem.IDID{currentnew(Item[T,D])*current*item}}ifcurrentnil{returnnil}vardata[]*Item[T,D]{current}ifpid,ok:any(current.Pid).(string);ok{ifpid{returndata}}ifpid,ok:any(current.Pid).(int);ok{ifpid0{returndata}}var(listappend([]*Item[T,D]{current},c.findParents(current.Pid)...)resmake([]*Item[T,D],len(list))index0)fori:len(list)-1;i0;i--{res[index]list[i]index1}returnres}func(c*Category[T,D])findParents(pid T)[]*Item[T,D]{varparents[]*Item[T,D]for_,item:rangec.List{ifitem.IDpid{varvalnew(Item[T,D])*val*item parentsappend(parents,val)ifpid,ok:any(val.Pid).(string);ok{ifpid{break}}ifpid,ok:any(val.Pid).(int);ok{ifpid0{break}}parentsappend(parents,c.findParents(val.Pid)...)}}returnparents}