TreeUtil: 树构造器 about ekit HOT 3 CLOSED

// BuildTree 参数:list 源切片数据,rootId 最顶层rootId, opt 配配置, fn 转换器,用于处理字段映射
func BuildTree[T comparable, E constraints.Ordered](list []any, rootId T, opt TreeOptional, fu func(src any) TreeNode[T, E]) Tree[T] {
}

func ToTree[T any](data []T) Tree[T] {

}

type Tree[T any] struct {
       Root Node[T]
}

type City struct {
    ParentID int64
    Name
    Sort int
} 

// 深度优先遍历
func (t *Tree[T]) DFS(func(T))
// 广度优先遍历
func (t *Tree[T]) BFS(func(T))

package tree

import (
	"sort"
)

// Tree 本体
type Tree[T comparable] struct {
	Mp map[string]any
	//父节点的指针,辅助构造树
	parent *Tree[T]
}

// 增加子节点，同时关联子节点的父节点为当前节点
func (cur *Tree[T]) addChildren(config *Config, children ...*Tree[T]) {
	if len(children) > 0 {
		childrenMap := make([]map[string]any, 0, len(children))
		for _, elem := range children {
			childrenMap = append(childrenMap, elem.Mp)
		}
		if m, ok := cur.Mp[config.ChildrenKEY]; ok {
			cur.Mp[config.ChildrenKEY] = append(m.([]map[string]any), childrenMap...)
		} else {
			cur.Mp[config.ChildrenKEY] = childrenMap
		}
	}
	for _, node := range children {
		node.parent = cur
	}
}

// Config 配置类
type Config struct {
	IdKey       string
	ParentIdKey string
	//递归深度 从0即不限制
	Deep        int
	Name        string
	ChildrenKEY string
	//排序字段
	Sort string
}

var DefaultConfig = &Config{IdKey: "id", ParentIdKey: "parentId", Deep: -1, Name: "name", ChildrenKEY: "children", Sort: "sort"}

type Builder[T comparable] struct {
	root *Tree[T]
	//标记位,防止build被重复调用
	isBuild bool
	config  *Config
	//中间map
	idTreeMap map[T]*Tree[T]
	//按sortKey 对treeId 进行排序
	sortList []T
}

// NewBuilder 创建构造器
func NewBuilder[T comparable](config *Config, rootId T) *Builder[T] {
	root := &Tree[T]{Mp: map[string]any{}}
	root.Mp[config.IdKey] = rootId
	return &Builder[T]{root: root, config: config, idTreeMap: map[T]*Tree[T]{}}
}

// Append 向构造器中添加元素
func Append[T comparable, E any](builder *Builder[T], list []E, nodeParser func(E, *Tree[T])) {
	if builder.isBuild {
		panic("树已经被构造")
	}
	for _, elem := range list {
		node := &Tree[T]{Mp: map[string]any{}}
		nodeParser(elem, node)
		id := node.Mp[builder.config.IdKey]
		builder.idTreeMap[id.(T)] = node
		builder.sortList = append(builder.sortList, id.(T))
	}

	if builder.config.Sort != "" {
		sort.Slice(builder.sortList, func(i, j int) bool {
			id1 := builder.sortList[i]
			id2 := builder.sortList[j]
			sort1 := builder.idTreeMap[id1].Mp[builder.config.Sort].(int)
			sort2 := builder.idTreeMap[id2].Mp[builder.config.Sort].(int)
			return sort1 < sort2
		})
	}
}

// Build 构造tree
func (builder *Builder[T]) Build() *Tree[T] {

	if builder.isBuild {
		panic("树已经被构造")
	}
	flag := false
	config := builder.config

	for _, id := range builder.sortList {
		node := builder.idTreeMap[id]
		if id == builder.root.Mp[config.IdKey] {
			builder.root = node
			flag = true
			continue
		}
		parentId := node.Mp[config.ParentIdKey]
		if builder.root.Mp[config.IdKey] == parentId {
			builder.root.addChildren(config, node)
			continue
		}
		parentNode, ok := builder.idTreeMap[parentId.(T)]
		if ok {
			parentNode.addChildren(config, node)
		}
	}
	//todo deep剪枝
	builder.isBuild = true
	if !flag {
		return &Tree[T]{}
	}
	return builder.root
}

var MockList = []area{
	{1, -1, "**", 0},
	{2, 1, "北京市", -0},
	{3, 1, "上海市", 1},
	{4, 3, "浦东", 1},
	{5, 3, "徐汇区", 2},
	{6, 2, "朝阳区", 3},
	{7, 2, "海淀区", 4},
	{8, 9, "海淀区", 4},
}
func DemoNodeParser(x area, t2 *Tree[int]) {
	t2.Mp["id"] = x.Id
	t2.Mp["parentId"] = x.ParentId
	t2.Mp["name"] = x.Name
	t2.Mp["sort"] = x.Sort
}

builder := NewBuilder(DefaultConfig, rootId)
Append(builder, MockList , DemoNodeParser)
got := builder.Build()