使用Go语言将扁平化数据构建为层级树结构-Golang-PHP中文网

使用Go语言将扁平化数据构建为层级树结构

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

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

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

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

OrgID	OrgName	parentID
A001	Dept	0
A002	subDept1	A001
A003	sub_subDept	A002
A006	gran_subDept	A003
A004	subDept2	A001

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

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

登录后复制

2. 数据模型定义

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

立即学习“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
)

登录后复制

解释：

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
}

登录后复制

解释：

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

Adobe Flex 简介中文WORD版

Flex是一个基于组件的开发框架，可以生成一个由Flash Player运行的富互联网应用程序。Flex将基于标准的语言和各种可扩展用户界面及数据访问组件结合起来，使得开发人员能够构建具有丰富数据演示、强大客户端逻辑和集成多媒体的应用程序。 Flex是一个建立在Flash平台上的富客户端应用开发工具包，Flex 作为富 Internet 应用（RIA）时代的新技术代表，自从 2007 年 Adobe 公司将其开源以来，Flex 就以前所未有的速度在成长。感兴趣的朋友可以过来看看

查看详情

// 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. 如何运行与测试

保存代码： 将上述完整代码保存为 tree_builder.go 文件。
准备输入数据： 创建一个文本文件，例如 input.txt，将您的扁平化表格数据粘贴进去。确保每行包含三个由空格分隔的字段：OrgID OrgName parentID。
```
A001 Dept 0
A002 subDept1 A001
A003 sub_subDept A002
A006 gran_subDept A003
A004 subDept2 A001
```
登录后复制
编译程序： 打开终端或命令行，导航到 tree_builder.go 文件所在的目录，然后执行以下命令：
```
go build -o tree_builder
```
登录后复制
这会生成一个名为 tree_builder (Windows 上是 tree_builder.exe) 的可执行文件。

运行程序： 通过管道将 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，

以上就是使用Go语言将扁平化数据构建为层级树结构的详细内容，更多请关注php中文网其它相关文章！