您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java 樹形結構構建演算法：從扁平資料到遞迴樹的高效實現

編輯：Java 綜合教學

Java 樹形結構構建演算法：從扁平資料到遞迴樹的高效實現

前端樹形元件 (如 Ant Design Tree、Element UI Tree、zTree) 要求資料為巢狀結構，而資料庫通常儲存扁平的父子關係表。本文提供高效、通用的 Java 樹構建工具類，支援單根/多根、大資料量、層級計算、葉子節點標記。

一、資料模型定義

@Data
@NoArgsConstructor
@AllArgsConstructor
public class TreeNode<T> {
    private String id;           // 節點唯一標識
    private String parentId;     // 父節點 ID，根節點為 "0" 或 null
    private String name;         // 顯示名稱
    private T data;              // 業務擴充資料
    private Integer level;       // 層級深度 (根=1)
    private Boolean leaf;        // 是否葉子節點
    private List<TreeNode<T>> children = new ArrayList<>(); // 子節點列表
    
    // 輔助方法
    public void addChild(TreeNode<T> child) {
        children.add(child);
        child.setLevel(this.level + 1);
    }
}

二、核心演算法：O(n) 時間複雜度單次遍歷構建

public class TreeBuilder<T> {
    
    /**
     * 構建樹形結構
     * @param nodes 扁平節點列表
     * @param rootParentId 根節點的 parentId 值 (通常為 "0" 或 null)
     * @return 根節點列表 (森林)
     */
    public List<TreeNode<T>> build(List<TreeNode<T>> nodes, String rootParentId) {
        if (nodes == null || nodes.isEmpty()) return Collections.emptyList();
        
        // 1. 建立 ID -> Node 映射 (O(n))
        Map<String, TreeNode<T>> nodeMap = new HashMap<>(nodes.size() * 2);
        for (TreeNode<T> node : nodes) {
            nodeMap.put(node.getId(), node);
        }
        
        // 2. 識別根節點並建立父子關係 (O(n))
        List<TreeNode<T>> roots = new ArrayList<>();
        for (TreeNode<T> node : nodes) {
            String pid = node.getParentId();
            if (rootParentId != null && rootParentId.equals(pid) || 
                rootParentId == null && (pid == null || "0".equals(pid))) {
                node.setLevel(1);
                roots.add(node);
            } else {
                TreeNode<T> parent = nodeMap.get(pid);
                if (parent != null) {
                    parent.addChild(node);
                } else {
                    // 孤兒節點：父節點不存在，視為根節點處理或記錄警告
                    node.setLevel(1);
                    roots.add(node);
                }
            }
        }
        
        // 3. 標記葉子節點 (可選，遍歷時同步完成)
        markLeafNodes(roots);
        
        return roots;
    }
    
    private void markLeafNodes(List<TreeNode<T>> nodes) {
        for (TreeNode<T> node : nodes) {
            if (node.getChildren().isEmpty()) {
                node.setLeaf(true);
            } else {
                node.setLeaf(false);
                markLeafNodes(node.getChildren());
            }
        }
    }
}

三、進階功能擴充

1. 計算樹深度 (Rowspan for 表格合併)

public int calculateMaxDepth(TreeNode<T> root) {
    if (root == null) return 0;
    if (root.getChildren().isEmpty()) return root.getLevel();
    int max = 0;
    for (TreeNode<T> child : root.getChildren()) {
        max = Math.max(max, calculateMaxDepth(child));
    }
    return max;
}

2. 計算葉子節點總數 (Colspan for 表格合併)

public int calculateLeafCount(TreeNode<T> root) {
    if (root == null) return 0;
    if (root.getChildren().isEmpty()) return 1;
    int count = 0;
    for (TreeNode<T> child : root.getChildren()) {
        count += calculateLeafCount(child);
    }
    return count;
}

3. 樹節點搜尋與路徑追蹤

// 根據 ID 查找節點
public TreeNode<T> findNode(List<TreeNode<T>> roots, String targetId) {
    for (TreeNode<T> root : roots) {
        TreeNode<T> found = dfsFind(root, targetId);
        if (found != null) return found;
    }
    return null;
}

private TreeNode<T> dfsFind(TreeNode<T> node, String targetId) {
    if (node.getId().equals(targetId)) return node;
    for (TreeNode<T> child : node.getChildren()) {
        TreeNode<T> found = dfsFind(child, targetId);
        if (found != null) return found;
    }
    return null;
}

// 獲取從根到目標節點的路徑
public List<TreeNode<T>> getPath(List<TreeNode<T>> roots, String targetId) {
    List<TreeNode<T>> path = new ArrayList<>();
    for (TreeNode<T> root : roots) {
        if (dfsPath(root, targetId, path)) return path;
    }
    return Collections.emptyList();
}

private boolean dfsPath(TreeNode<T> node, String targetId, List<TreeNode<T>> path) {
    path.add(node);
    if (node.getId().equals(targetId)) return true;
    for (TreeNode<T> child : node.getChildren()) {
        if (dfsPath(child, targetId, path)) return true;
    }
    path.remove(path.size() - 1);
    return false;
}

四、大資料量優化策略 (10萬+ 節點)

分頁載入 (Lazy Load)：前端僅請求根節點，展開時動態載入子節點 (後端提供 getChildrenByParentId API)
虛擬滾動：前端只渲染可視區域節點
資料庫端遞迴 CTE：PostgreSQL/Oracle/MySQL 8.0+ 支援 WITH RECURSIVE 直接查詢子樹
緩存樹結構：Redis 存儲序列化樹，變更時增量更新
並行構建：ForkJoinPool 平行處理多棵獨立子樹

五、完整測試範例

@Test
public void testBuildTree() {
    List<TreeNode<String>> nodes = Arrays.asList(
        new TreeNode<>("1", "0", "系統管理", null),
        new TreeNode<>("2", "1", "用戶管理", null),
        new TreeNode<>("3", "1", "角色管理", null),
        new TreeNode<>("4", "2", "新增用戶", null),
        new TreeNode<>("5", "2", "編輯用戶", null),
        new TreeNode<>("6", "0", "業務模組", null),
        new TreeNode<>("7", "6", "訂單管理", null)
    );
    
    TreeBuilder<String> builder = new TreeBuilder<>();
    List<TreeNode<String>> roots = builder.build(nodes, "0");
    
    // 驗證
    assertEquals(2, roots.size()); // 系統管理、業務模組
    assertEquals(2, roots.get(0).getChildren().size()); // 用戶、角色
    assertEquals(2, roots.get(0).getChildren().get(0).getChildren().size()); // 新增、編輯
    assertTrue(roots.get(0).getChildren().get(0).getChildren().get(0).getLeaf());
    
    // JSON 序列化輸出前端
    String json = new ObjectMapper().writeValueAsString(roots);
    System.out.println(json);
}