Go语言构建层级树结构教程

本教程详细阐述了如何利用Go语言，将具有父子关系的扁平化表格数据高效地转换为内存中的树形结构。通过定义简洁的节点类型、运用哈希映射实现父节点的快速查找与关联，以及设计递归函数进行树的构建与可视化展示，我们提供了一套完整的解决方案，旨在帮助开发者理解并实现此类数据转换，并附带了可运行的代码示例。

1. 理解树形数据结构与扁平化数据

在许多应用场景中，数据天然具有层级关系，例如组织架构、文件系统或评论回复链。然而，这些层级数据在数据库或CSV文件中常常以扁平化的表格形式存储，每行记录包含一个唯一的ID、名称以及一个指向其父节点的ID。我们的目标就是将这种扁平化的父子关系数据转换为内存中的树形结构，以便于进行层级遍历、查找和展示。

例如，以下表格展示了一个简化的部门层级结构：

其中 parentID 为 "0" 的节点被视为根节点。我们希望将其转换为如下所示的树形结构：

Dept
--subDept1
----sub_subDept
------gran_subDept
--subDept2

2. 数据模型定义

为了在Go语言中表示树形结构，我们需要定义一个节点类型，该节点包含其自身的名称以及一个指向其所有子节点的切片。同时，为了高效地根据ID查找节点，我们还需要一个全局的哈希映射。

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strings"
)

// Node 定义了树中的一个节点
type Node struct {
    Name     string    // 节点的名称
    Children []*Node   // 节点的子节点列表
}

var (
    // nodeTable 用于通过ID快速查找已创建的节点
    nodeTable = map[string]*Node{}
    // root 指向树的根节点。本示例假设只有一个根节点。
    root      *Node
)

解释：

• Node 结构体：Name 存储节点的显示名称，Children 是一个 *Node 类型的切片，用于存储当前节点的所有子节点。
• nodeTable：这是一个 map[string]*Node，其键是节点的唯一ID（如OrgID），值是指向该节点的指针。这个映射在构建树时至关重要，它允许我们通过 parentID 快速找到对应的父节点。
• root：一个 *Node 类型的全局变量，用于存储整个树的根节点。本示例代码假定只有一个根节点，其 parentID 为 "0"。

3. 核心逻辑实现

3.1 添加节点 (add 函数)

add 函数负责创建新节点，并将其正确地插入到树中。它根据 parentID 判断节点是根节点还是普通子节点。

// add 函数用于创建新节点并将其添加到树结构中
// id: 当前节点的唯一标识
// name: 当前节点的显示名称
// parentId: 当前节点的父节点标识
func add(id, name, parentId string) {
    fmt.Printf("add: id=%v name=%v parentId=%v\n", id, name, parentId)

    // 创建一个新的节点实例
    node := &Node{Name: name, Children: []*Node{}}

    // 根据 parentId 判断节点类型
    if parentId == "0" {
        // 如果 parentId 为 "0"，则当前节点是根节点
        root = node
    } else {
        // 否则，当前节点是子节点，需要找到其父节点
        parent, ok := nodeTable[parentId]
        if !ok {
            // 如果父节点不存在，打印错误并跳过
            fmt.Printf("add: parentId=%v: not found, skipping node %v\n", parentId, id)
            return
        }
        // 将当前节点添加到父节点的 Children 列表中
        parent.Children = append(parent.Children, node)
    }

    // 将新创建的节点添加到 nodeTable 中，以便后续查找
    nodeTable[id] = node
}

解释：

1. 创建一个新的 Node 实例，并初始化其 Name 和空的 Children 切片。
2. 如果 parentId 是 "0"，则将此节点设置为全局 root。
3. 如果 parentId 不是 "0"，则尝试从 nodeTable 中查找对应的父节点。
   • 如果父节点不存在，表示数据可能存在问题（例如，父节点ID引用了不存在的节点），此时会打印错误并跳过当前节点的处理。
   • 如果找到父节点，则将新创建的节点添加到父节点的 Children 切片中。
4. 最后，无论节点是根还是子，都将其存储到 nodeTable 中，以便其他节点可以将其作为父节点引用。

3.2 数据输入与解析 (scan 函数)

scan 函数负责从标准输入读取数据，解析每一行，并调用 add 函数来构建树。

// scan 函数从标准输入读取数据，解析每行并调用 add 函数构建树
func scan() {
    input := os.Stdin
    reader := bufio.NewReader(input)
    lineCount := 0
    for {
        lineCount++
        line, err := reader.ReadString('\n') // 读取一行直到换行符
        if err == io.EOF {
            break // 文件结束
        }
        if err != nil {
            fmt.Printf("error reading lines: %v\n", err)
            return
        }
        // 使用 strings.Fields 分割字符串，默认按空格或制表符分割
        tokens := strings.Fields(line)
        if t := len(tokens); t != 3 {
            // 检查每行是否有3个字段 (OrgID, OrgName, parentID)
            fmt.Printf("bad input line %v: tokens=%d [%v], expected 3 fields\n", lineCount, t, line)
            continue
        }
        // 调用 add 函数处理当前行数据
        add(tokens[0], tokens[1], tokens[2])
    }
}

解释：

• 使用 bufio.NewReader 从 os.Stdin 读取输入。
• 循环读取每一行，直到遇到 io.EOF (文件结束)。
• strings.Fields(line) 会将一行字符串按空白字符（空格、制表符等）分割成字符串切片。
• 检查 tokens 的长度是否为3，确保输入格式正确。
• 将解析出的 OrgID、OrgName 和 parentID 传递给 add 函数。

3.3 树形结构展示 (showNode 和 show 函数)

showNode 函数使用递归的方式遍历树并打印节点名称，通过 prefix 参数实现层级缩进。show 函数作为入口，调用 showNode 从根节点开始展示。

// showNode 递归地显示树中的每个节点及其子节点
// node: 当前要显示的节点
// prefix: 用于缩进的字符串，表示当前节点的层级
func showNode(node *Node, prefix string) {
    if prefix == "" {
        // 根节点不加前缀，单独打印
        fmt.Printf("%v\n", node.Name)
    } else {
        // 子节点加上缩进前缀
        fmt.Printf("%v%v\n", prefix, node.Name)
    }
    // 递归遍历所有子节点
    for _, n := range node.Children {
        showNode(n, prefix+"--") // 子节点的缩进增加 "--"
    }
}

// show 函数是显示树结构的入口
func show() {
    if root == nil {
        fmt.Printf("show: root node not found, tree is empty\n")
        return
    }
    fmt.Printf("\nRESULT:\n")
    showNode(root, "") // 从根节点开始显示，初始前缀为空
}

解释：

• showNode 是一个递归函数。它首先打印当前节点的名称，并根据 prefix 参数决定是否添加缩进。
• 然后，它遍历当前节点的所有 Children，并对每个子节点递归调用 showNode，同时将 prefix 增加 "--"，以实现逐级缩进的效果。
• show 函数简单地检查 root 是否存在，如果存在，则调用 showNode 开始展示。

4. 完整代码示例

将上述所有部分组合起来，构成一个完整的Go程序：

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strings"
)

// Node 定义了树中的一个节点
type Node struct {
    Name     string    // 节点的名称
    Children []*Node   // 节点的子节点列表
}

var (
    // nodeTable 用于通过ID快速查找已创建的节点
    nodeTable = map[string]*Node{}
    // root 指向树的根节点。本示例假设只有一个根节点。
    root      *Node
)

// add 函数用于创建新节点并将其添加到树结构中
// id: 当前节点的唯一标识
// name: 当前节点的显示名称
// parentId: 当前节点的父节点标识
func add(id, name, parentId string) {
    fmt.Printf("add: id=%v name=%v parentId=%v\n", id, name, parentId)

    // 创建一个新的节点实例
    node := &Node{Name: name, Children: []*Node{}}

    // 根据 parentId 判断节点类型
    if parentId == "0" {
        // 如果 parentId 为 "0"，则当前节点是根节点
        root = node
    } else {
        // 否则，当前节点是子节点，需要找到其父节点
        parent, ok := nodeTable[parentId]
        if !ok {
            // 如果父节点不存在，打印错误并跳过
            fmt.Printf("add: parentId=%v: not found, skipping node %v\n", parentId, id)
            return
        }
        // 将当前节点添加到父节点的 Children 列表中
        parent.Children = append(parent.Children, node)
    }

    // 将新创建的节点添加到 nodeTable 中，以便后续查找
    nodeTable[id] = node
}

// scan 函数从标准输入读取数据，解析每行并调用 add 函数构建树
func scan() {
    input := os.Stdin
    reader := bufio.NewReader(input)
    lineCount := 0
    for {
        lineCount++
        line, err := reader.ReadString('\n') // 读取一行直到换行符
        if err == io.EOF {
            break // 文件结束
        }
        if err != nil {
            fmt.Printf("error reading lines: %v\n", err)
            return
        }
        // 使用 strings.Fields 分割字符串，默认按空格或制表符分割
        tokens := strings.Fields(line)
        if t := len(tokens); t != 3 {
            // 检查每行是否有3个字段 (OrgID, OrgName, parentID)
            fmt.Printf("bad input line %v: tokens=%d [%v], expected 3 fields\n", lineCount, t, line)
            continue
        }
        // 调用 add 函数处理当前行数据
        add(tokens[0], tokens[1], tokens[2])
    }
}

// showNode 递归地显示树中的每个节点及其子节点
// node: 当前要显示的节点
// prefix: 用于缩进的字符串，表示当前节点的层级
func showNode(node *Node, prefix string) {
    if prefix == "" {
        // 根节点不加前缀，单独打印
        fmt.Printf("%v\n", node.Name)
    } else {
        // 子节点加上缩进前缀
        fmt.Printf("%v%v\n", prefix, node.Name)
    }
    // 递归遍历所有子节点
    for _, n := range node.Children {
        showNode(n, prefix+"--") // 子节点的缩进增加 "--"
    }
}

// show 函数是显示树结构的入口
func show() {
    if root == nil {
        fmt.Printf("show: root node not found, tree is empty\n")
        return
    }
    fmt.Printf("\nRESULT:\n")
    showNode(root, "") // 从根节点开始显示，初始前缀为空
}

// main 函数是程序的入口点
func main() {
    fmt.Printf("main: reading input from stdin\n")
    scan() // 读取并解析输入数据
    fmt.Printf("main: reading input from stdin -- done\n")
    show() // 显示构建好的树结构
    fmt.Printf("main: end\n")
}

5. 如何运行与测试

1. 保存代码： 将上述完整代码保存为 tree_builder.go 文件。

2. 准备输入数据： 创建一个文本文件，例如 input.txt，将您的扁平化表格数据粘贴进去。确保每行包含三个由空格分隔的字段：OrgID OrgName parentID。

   A001 Dept 0
   A002 subDept1 A001
   A003 sub_subDept A002
   A006 gran_subDept A003
   A004 subDept2 A001

3. 编译程序： 打开终端或命令行，导航到 tree_builder.go 文件所在的目录，然后执行以下命令：

   go build -o tree_builder

   这会生成一个名为 tree_builder (Windows 上是 tree_builder.exe) 的可执行文件。

4. 运行程序： 通过管道将 input.txt 的内容作为标准输入传递给程序：

   cat input.txt | ./tree_builder

   或者在 Windows 上：

   type input.txt | .\tree_builder.exe

   您将看到程序打印的调试信息和最终的树形结构输出：

   main: reading input from stdin
   add: id=A001 name=Dept parentId=0
   add: id=A002 name=subDept1 parentId=A001
   add: id=A003 name=sub_subDept parentId=A002
   add: id=A006 name=gran_subDept parentId=A003
   add: id=A004 name=subDept2 parentId=A001
   main: reading input from stdin -- done
   
   RESULT:
   Dept
   --subDept1
   ----sub_subDept
   ------gran_subDept
   --subDept2
   main: end

6. 注意事项与潜在优化

• 单一根节点假设： 当前代码假定树只有一个根节点，即只有一个 parentID 为 "0" 的记录。如果存在多个根节点，root 变量将只保存最后处理的那个根节点。要支持多个根节点，可以将 root 修改为 []*Node 类型，并在 parentId == "0" 时将节点添加到这个切片中。
• 输入数据顺序： 尽管 nodeTable 的存在使得 add 函数能够处理父节点在其子节点之后出现的情况（只要父节点最终被处理），但在实际应用中，如果父节点总是先于其子节点出现，处理逻辑会更直观且可能略高效。
• 错误处理：
  • 循环引用： 当前代码没有检测循环引用（例如 A 的父是 B，