适合表示层级关系的树形数据结构-Golang-PHP中文网

适合表示层级关系的树形数据结构

DDD

发布： 2025-09-09 20:38:01

原创

1038人浏览过

适合表示层级关系的树形数据结构

在处理少量节点且层级关系相对固定的场景下，选择合适的树形数据结构至关重要。针对诸如建模层级包含关系，并需要频繁进行父节点、子节点查找以及按ID查找节点等操作的需求，一种简单而有效的方案是采用带有父节点引用和子节点列表的树结构，并辅以ID到节点的映射。

数据结构设计

我们可以定义一个简单的树节点结构，包含以下几个关键字段：

ID: 节点的唯一标识符。
Parent: 指向父节点的引用（指针）。根节点的Parent可以为null。
Children: 一个存储子节点引用的列表（数组或链表）。
Data: 存储节点相关数据的字段（根据实际需求定义）。

type Node struct {
    ID       string
    Parent   *Node
    Children []*Node
    Data     interface{} // 可以根据需要替换为具体的数据类型
}

登录后复制

核心操作实现

基于上述数据结构，我们可以方便地实现以下核心操作：

查找父节点： 直接访问节点的Parent字段即可。
查找子节点： 直接遍历节点的Children列表即可。
按ID查找节点： 可以通过遍历整个树来实现，但效率较低。更高效的方法是维护一个全局的ID到节点的映射（Map），通过ID直接获取节点引用。

var nodeMap map[string]*Node

// 初始化节点映射
func init() {
    nodeMap = make(map[string]*Node)
}

// 添加节点到映射
func addNodeToMap(node *Node) {
    nodeMap[node.ID] = node
}

// 通过ID查找节点
func findNodeByID(id string) *Node {
    return nodeMap[id]
}

登录后复制

双向遍历

由于每个节点都持有父节点的引用和子节点的列表，因此可以轻松地实现双向遍历。向上遍历只需访问Parent字段，向下遍历只需遍历Children列表。

添加和重排节点

凡人网络购物系统jsp版(JspShop)

基于jsp+javabean+access(mysql)三层结构的动态购物网站，v1.2包含v1.0中未公开的数据库连接的java源文件一，网站前台功能：产品二级分类展示：一级分类－－二级分类－－产品列表－－详细介绍（名称，图片，市场价，会员价，是否推荐，功能介绍等）产品搜索：关键字模糊搜索定购产品：选择商品－－确认定购－－填写收货人信息－－选择付款方式－－订单号自动生成（限登录用户）

查看详情

由于子节点列表的存在，添加节点非常简单。只需要创建一个新的节点，设置其Parent，并将其添加到父节点的Children列表中。重排节点也类似，只需要从原父节点的Children列表中移除该节点，并将其添加到新父节点的Children列表中，同时更新节点的Parent字段。

示例代码

以下是一个简单的Go语言示例，展示了如何创建树结构、添加节点以及查找节点：

package main

import "fmt"

type Node struct {
    ID       string
    Parent   *Node
    Children []*Node
    Data     string
}

var nodeMap map[string]*Node

func init() {
    nodeMap = make(map[string]*Node)
}

func addNodeToMap(node *Node) {
    nodeMap[node.ID] = node
}

func findNodeByID(id string) *Node {
    return nodeMap[id]
}

func main() {
    // 创建根节点
    root := &Node{ID: "root", Data: "Root Node"}
    addNodeToMap(root)

    // 创建子节点
    child1 := &Node{ID: "child1", Parent: root, Data: "Child 1"}
    addNodeToMap(child1)
    child2 := &Node{ID: "child2", Parent: root, Data: "Child 2"}
    addNodeToMap(child2)

    root.Children = []*Node{child1, child2}

    // 查找节点
    foundNode := findNodeByID("child1")
    if foundNode != nil {
        fmt.Printf("Found node with ID: %s, Data: %s\n", foundNode.ID, foundNode.Data)
        fmt.Printf("Parent ID: %s\n", foundNode.Parent.ID)
    }

    // 遍历子节点
    fmt.Println("Children of root node:")
    for _, child := range root.Children {
        fmt.Printf("  ID: %s, Data: %s\n", child.ID, child.Data)
    }
}

登录后复制

注意事项