构建数据树的几种方式

概述

在设计一个树形结构的数据接口时，通常需要将扁平的数据库记录转换为嵌套的树形结构。以下是一些最佳实践来组合成树形结构的数据：

• 递归查询：

从根节点开始，递归地查询子节点。

每次查询都基于当前的父ID来找到所有子节点。

• 邻接列表：

在内存中构建一个以ID为键的字典，每个键对应的值是一个包含其子节点ID的列表。

遍历数据库记录，根据父ID将子节点ID添加到相应列表中。

• 嵌套集模型（Nested Set Model）：

这种方法不直接使用父ID，而是使用左右值来表示节点的层次结构。

查询时可以直接获取整个子树，但插入和更新操作较为复杂。

邻接列表

示例

节点类（TreeNode）：

import java.util.ArrayList;
import java.util.List;

public class TreeNode {
    private int id;
    private Integer parentId; // 父节点ID，可以为null
    private List<TreeNode> children = new ArrayList<>(); // 子节点列表

    public TreeNode(int id, Integer parentId) {
        this.id = id;
        this.parentId = parentId;
    }

    public int getId() {
        return id;
    }

    public Integer getParentId() {
        return parentId;
    }

    public List<TreeNode> getChildren() {
        return children;
    }

    public void addChild(TreeNode child) {
        this.children.add(child);
    }
}

构建类（TreeBuilder）：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TreeBuilder {
    public static List<TreeNode> buildTree(List<TreeNode> flatData) {
        Map<Integer, TreeNode> nodeMap = new HashMap<>();
        List<TreeNode> roots = new ArrayList<>();

        // 将所有节点存储在一个Map中，以便通过ID快速访问
        for (TreeNode node : flatData) {
            nodeMap.put(node.getId(), node);
        }

        // 遍历所有节点，根据父ID建立树形结构
        for (TreeNode node : flatData) {
            Integer parentId = node.getParentId();
            if (parentId == null) {
                // 如果父ID为空，则该节点是根节点
                roots.add(node);
            } else {
                // 将当前节点添加到其父节点的子节点列表中
                TreeNode parent = nodeMap.get(parentId);
                if (parent != null) {
                    parent.addChild(node);
                }
            }
        }

        return roots;
    }

    public static void main(String[] args) {
        // 示例数据
        List<TreeNode> flatData = new ArrayList<>();
        flatData.add(new TreeNode(1, null));
        flatData.add(new TreeNode(2, 1));
        flatData.add(new TreeNode(3, 1));
        flatData.add(new TreeNode(4, 2));
        // ... 添加更多节点

        // 构建树
        List<TreeNode> roots = buildTree(flatData);

        // 打印树结构（简单的深度优先遍历）
        printTree(roots, "");
    }

    private static void printTree(List<TreeNode> nodes, String prefix) {
        for (TreeNode node : nodes) {
            System.out.println(prefix + "Node: " + node.getId());
            if (!node.getChildren().isEmpty()) {
                printTree(node.getChildren(), prefix + "  ");
            }
        }
    }
}

输出结果：

Node: 1
  Node: 2
    Node: 4
  Node: 3

通过demo，我们也可以观察到：

1.nodeMap与flatData与roots中存储的TreeNode为同个对象，而不是不同个对象，在遍历flatData时，先取根节点到roots中，后面取nodeMap中的TreeNode添加flatData遍历到的子节点，到最后我们可以观察到roots的字节点是完整的。

2.TreeNode里的每个子节点与nodeMap/flatData/roots也是同一个，flatData传入的4个节点，可以看到TreeNode(2, 1)先加进了TreeNode(1, null)，然后TreeNode(4, 2)才加进TreeNode(2, 1)，如果不是同一个，那么最后的树应该只有两个层次，而不是三个。

3.本质原理是借助每个节点在处理环节的唯一存在，将各自的子节点加入自身。