如何在 Go 中合并两个具有相同结构的树（TreeData）-Golang-PHP中文网

如何在 Go 中合并两个具有相同结构的树（TreeData）

本文介绍一种基于递归的、深度优先的树合并方法，适用于结构相同的嵌套树形数据（如目录结构），通过名称匹配自动合并同名节点，并合并其子节点。

本文介绍一种基于递归的、深度优先的树合并方法，适用于结构相同的嵌套树形数据（如目录结构），通过名称匹配自动合并同名节点，并合并其子节点。

在 Go 中合并两个具有相同结构的树（如 TreeData），核心思想是：按节点 Name 字段进行递归匹配与合并。当两棵树中存在同名节点时，将其子树递归合并；若仅存在于其中一棵树，则直接保留。该方案天然适配您提供的 JSON 树结构，且无需外部依赖，完全使用标准库即可实现。

使用Go语言搭建家庭相册系统-相关课件

下载

✅ 合并逻辑说明

根节点必须一致（如示例中均为 "."），否则应先校验或定义策略（如抛错/忽略）；
对每个层级的 Children 切片，遍历 tree1 的子节点，在 tree2 中查找 Name 相同的节点；
若找到匹配项，则递归合并二者 Children；否则将 tree1 的子节点原样保留；
最后将 tree2 中未被匹配的子节点追加到结果中（确保不丢失数据）。

? 完整可运行代码示例

package main

import (
    "encoding/json"
    "fmt"
)

type TreeData struct {
    Name     string    `json:"name"`
    Depth    int       `json:"depth"`
    Children []TreeData `json:"children,omitempty"`
}

// MergeTrees 深度合并两棵树：以 tree1 为基准，将 tree2 中同名节点的子树合并进来
func MergeTrees(tree1, tree2 TreeData) TreeData {
    // 根节点必须一致（可按需调整策略）
    if tree1.Name != tree2.Name {
        panic(fmt.Sprintf("cannot merge trees with different root names: %q vs %q", tree1.Name, tree2.Name))
    }

    // 初始化结果树（复用 tree1 的根信息）
    result := TreeData{
        Name:  tree1.Name,
        Depth: tree1.Depth,
    }

    // 构建 children 映射：name → index，便于快速查找
    tree2ChildMap := make(map[string]int)
    for i, child := range tree2.Children {
        tree2ChildMap[child.Name] = i
    }

    // 遍历 tree1 的子节点，尝试合并
    mergedChildren := make([]TreeData, 0, len(tree1.Children)+len(tree2.Children))
    usedInTree2 := make(map[string]bool)

    for _, c1 := range tree1.Children {
        if idx, exists := tree2ChildMap[c1.Name]; exists {
            // 名称匹配：递归合并子树
            merged := MergeTrees(c1, tree2.Children[idx])
            mergedChildren = append(mergedChildren, merged)
            usedInTree2[c1.Name] = true
        } else {
            // tree1 独有：直接保留
            mergedChildren = append(mergedChildren, c1)
        }
    }

    // 添加 tree2 中未被使用的子节点（tree2 独有）
    for _, c2 := range tree2.Children {
        if !usedInTree2[c2.Name] {
            mergedChildren = append(mergedChildren, c2)
        }
    }

    result.Children = mergedChildren
    return result
}

// 示例用法（含 JSON 解析验证）
func main() {
    // 原始 JSON 数据（已补全缺失逗号和字段）
    json1 := `{
        "name": ".",
        "depth": 1,
        "children": [
            {
                "name": "com",
                "depth": 2,
                "children": [
                    {
                        "name": "didi",
                        "depth": 3,
                        "children": [
                            {
                                "name": "dev",
                                "depth": 4,
                                "children": null
                            }
                        ]
                    }
                ]
            }
        ]
    }`

    json2 := `{
        "name": ".",
        "depth": 1,
        "children": [
            {
                "name": "com",
                "depth": 2,
                "children": [
                    {
                        "name": "didi",
                        "depth": 3,
                        "children": [
                            {
                                "name": "influxdb",
                                "depth": 4,
                                "children": [
                                    {
                                        "name": "cluster-one",
                                        "depth": 5,
                                        "children": null
                                    }
                                ]
                            }
                        ]
                    }
                ]
            }
        ]
    }`

    var t1, t2 TreeData
    json.Unmarshal([]byte(json1), &t1)
    json.Unmarshal([]byte(json2), &t2)

    merged := MergeTrees(t1, t2)
    out, _ := json.MarshalIndent(merged, "", "    ")
    fmt.Println(string(out))
}