Golang中的递归数据结构解析与应用

以下是一个从扁平结构构建树形结构的递归实现：

package main

import "fmt"

// DataFlat 扁平节点
type DataFlat struct {
    IDGeoRegion int
    IDParent    int
    Description string
}

// GeoTree 树形节点
type GeoTree struct {
    IDGeoRegion int
    IDParent    int
    Description string
    Children    []*GeoTree
}

// BuildTree 构建树形结构的递归函数
func BuildTree(flatData []DataFlat, parentID int) []*GeoTree {
    var tree []*GeoTree
    
    for _, item := range flatData {
        if item.IDParent == parentID {
            node := &GeoTree{
                IDGeoRegion: item.IDGeoRegion,
                IDParent:    item.IDParent,
                Description: item.Description,
                Children:    BuildTree(flatData, item.IDGeoRegion),
            }
            tree = append(tree, node)
        }
    }
    
    return tree
}

// PrintTree 递归打印树形结构
func PrintTree(tree []*GeoTree, level int) {
    for _, node := range tree {
        indent := ""
        for i := 0; i < level; i++ {
            indent += "  "
        }
        fmt.Printf("%s%d: %s\n", indent, node.IDGeoRegion, node.Description)
        if len(node.Children) > 0 {
            PrintTree(node.Children, level+1)
        }
    }
}

func main() {
    dFlatlist := []DataFlat{}

    dFlat := DataFlat{IDGeoRegion: 1, IDParent: 0, Description: "Organisation"}
    dFlatlist = append(dFlatlist, dFlat)

    dFlat = DataFlat{IDGeoRegion: 2, IDParent: 1, Description: "Office"}
    dFlatlist = append(dFlatlist, dFlat)

    dFlat = DataFlat{IDGeoRegion: 3, IDParent: 2, Description: "Office Zürich"}
    dFlatlist = append(dFlatlist, dFlat)

    dFlat = DataFlat{IDGeoRegion: 4, IDParent: 2, Description: "Office Brazil"}
    dFlatlist = append(dFlatlist, dFlat)

    dFlat = DataFlat{IDGeoRegion: 5, IDParent: 1, Description: "Storage"}
    dFlatlist = append(dFlatlist, dFlat)

    dFlat = DataFlat{IDGeoRegion: 6, IDParent: 5, Description: "Storge Zürich"}
    dFlatlist = append(dFlatlist, dFlat)

    dFlat = DataFlat{IDGeoRegion: 7, IDParent: 5, Description: "Storge Brazil"}
    dFlatlist = append(dFlatlist, dFlat)

    // 构建树形结构
    tree := BuildTree(dFlatlist, 0)
    
    // 打印树形结构
    fmt.Println("树形结构:")
    PrintTree(tree, 0)
    
    // 访问特定节点
    fmt.Println("\n根节点及其子节点:")
    for _, root := range tree {
        fmt.Printf("根节点: %s (ID: %d)\n", root.Description, root.IDGeoRegion)
        for _, child := range root.Children {
            fmt.Printf("  子节点: %s (ID: %d)\n", child.Description, child.IDGeoRegion)
        }
    }
}

输出结果：

树形结构:
1: Organisation
  2: Office
    3: Office Zürich
    4: Office Brazil
  5: Storage
    6: Storge Zürich
    7: Storge Brazil

根节点及其子节点:
根节点: Organisation (ID: 1)
  子节点: Office (ID: 2)
  子节点: Storage (ID: 5)

如果需要更高效的实现，可以使用映射来减少递归搜索：

// BuildTreeEfficient 使用映射构建树形结构
func BuildTreeEfficient(flatData []DataFlat) []*GeoTree {
    // 创建映射：ID -> 节点
    nodeMap := make(map[int]*GeoTree)
    
    // 创建所有节点
    for _, item := range flatData {
        nodeMap[item.IDGeoRegion] = &GeoTree{
            IDGeoRegion: item.IDGeoRegion,
            IDParent:    item.IDParent,
            Description: item.Description,
            Children:    []*GeoTree{},
        }
    }
    
    // 构建树形结构
    var roots []*GeoTree
    for _, node := range nodeMap {
        if node.IDParent == 0 {
            roots = append(roots, node)
        } else {
            if parent, exists := nodeMap[node.IDParent]; exists {
                parent.Children = append(parent.Children, node)
            }
        }
    }
    
    return roots
}

这个实现的时间复杂度为O(n)，比纯递归实现更高效。