Java 無限級樹結構遞歸構建實戰

業務場景

企業級應用常需處理樹狀資料：組織架構、選單權限、商品分類、地區劃分等。資料庫通常採用鄰接表模型（id, parent_id, name），需在記憶體中構建樹結構供前端渲染或業務邏輯使用。

遞歸構建核心思路

1. 查詢根節點：parent_id IS NULL OR parent_id = 0。
2. 遞歸查找子節點：對每個節點，查詢 parent_id = 當前節點.id 的記錄。
3. 組裝樹節點物件：將子節點列表設定到父節點的 children 欄位。
4. 終止條件：查無子節點時返回空列表。

實體類設計

@Data
public class TreeNode<T> {
    private T id;
    private T parentId;
    private String label;
    private List<TreeNode<T>> children = new ArrayList<>();
    private Map<String, Object> extraProps = new HashMap<>(); // 擴展屬性
    
    public void addChild(TreeNode<T> child) {
        children.add(child);
    }
}

通用遞歸構建器實現

public class TreeBuilder<T> {
    private final List<TreeNode<T>> allNodes;
    private final Map<T, List<TreeNode<T>>> parentChildrenMap = new HashMap<>();

    public TreeBuilder(List<TreeNode<T>> nodes) {
        this.allNodes = nodes;
        buildIndex();
    }

    // 建立父ID -> 子節點列表 索引，O(n) 預處理
    private void buildIndex() {
        for (TreeNode<T> node : allNodes) {
            parentChildrenMap.computeIfAbsent(node.getParentId(), k -> new ArrayList<>()).add(node);
        }
    }

    // 公開入口：構建完整樹（多根節點）
    public List<TreeNode<T>> buildForest() {
        List<TreeNode<T>> roots = new ArrayList<>();
        for (TreeNode<T> node : allNodes) {
            if (isRoot(node)) {
                buildSubTree(node);
                roots.add(node);
            }
        }
        return roots;
    }

    // 判斷是否為根節點
    private boolean isRoot(TreeNode<T> node) {
        return node.getParentId() == null || 
               (node.getParentId() instanceof Number && ((Number) node.getParentId()).longValue() == 0);
    }

    // 遞歸構建子樹
    private void buildSubTree(TreeNode<T> parent) {
        List<TreeNode<T>> children = parentChildrenMap.get(parent.getId());
        if (children != null && !children.isEmpty()) {
            for (TreeNode<T> child : children) {
                buildSubTree(child); // 先構建孫子節點
                parent.addChild(child); // 再掛載到父節點
            }
        }
    }

    // 單根節點構建（指定根ID）
    public TreeNode<T> buildTree(T rootId) {
        TreeNode<T> root = findNode(rootId);
        if (root != null) {
            buildSubTree(root);
        }
        return root;
    }

    private TreeNode<T> findNode(T id) {
        return allNodes.stream().filter(n -> n.getId().equals(id)).findFirst().orElse(null);
    }
}

資料庫查詢優化：單次查詢 + 記憶體組裝

@Repository
public class DeptRepository {
    @Autowired private JdbcTemplate jdbcTemplate;

    public List<TreeNode<Long>> buildDeptTree() {
        // 一次查出所有部門
        String sql = "SELECT id, parent_id, name, sort_order FROM sys_dept ORDER BY sort_order";
        List<TreeNode<Long>> nodes = jdbcTemplate.query(sql, (rs, rowNum) -> {
            TreeNode<Long> node = new TreeNode<>();
            node.setId(rs.getLong("id"));
            node.setParentId(rs.getLong("parent_id"));
            node.setLabel(rs.getString("name"));
            node.getExtraProps().put("sort", rs.getInt("sort_order"));
            return node;
        });
        
        // 記憶體中構建樹
        return new TreeBuilder<>(nodes).buildForest();
    }
}

進階場景：獲取節點及所有下級 ID（原文案例優化）

@Service
public class EmployeeService {
    @Autowired private JdbcTemplate jdbcTemplate;

    // 獲取指定員工及其所有下屬 ID（遞歸 CTE 或記憶體遞歸）
    public List<Long> getSubordinateIds(Long supervisorId) {
        // 方案一：資料庫遞歸 CTE（PostgreSQL/Oracle/MySQL 8.0+）
        String cteSql = "WITH RECURSIVE sub_tree AS (" +
            "  SELECT employee_id FROM tbl_system_user WHERE employee_id = ?" +
            "  UNION ALL" +
            "  SELECT u.employee_id FROM tbl_system_user u " +
            "  INNER JOIN sub_tree st ON u.supervisor_id = st.employee_id" +
            ") SELECT employee_id FROM sub_tree";
        return jdbcTemplate.queryForList(cteSql, Long.class, supervisorId);

        // 方案二：記憶體遞歸（通用，適合中小數據量）
        // 1. 查所有員工建立索引
        // 2. 遞歸收集子孫 ID
    }
}

效能與遞歸深度考量

遞歸棧溢位防護

// 尾遞歸優化（Java 不支援 TCO，需手動轉迭代）
public List<TreeNode<T>> buildForestIterative() {
    List<TreeNode<T>> roots = new ArrayList<>();
    Deque<TreeNode<T>> stack = new ArrayDeque<>();
    
    // 找根節點入棧
    for (TreeNode<T> node : allNodes) {
        if (isRoot(node)) {
            roots.add(node);
            stack.push(node);
        }
    }
    
    // 迭代構建
    while (!stack.isEmpty()) {
        TreeNode<T> parent = stack.pop();
        List<TreeNode<T>> children = parentChildrenMap.get(parent.getId());
        if (children != null) {
            for (TreeNode<T> child : children) {
                parent.addChild(child);
                stack.push(child);
            }
        }
    }
    return roots;
}

總結

無限級樹構建是後端開發高頻需求。掌握「單次查詢 + 記憶體索引 + 遞歸/迭代組裝」模式，並根據數據量級選擇 CTE、閉包表等進階方案，能優雅解決 90% 的樹結構業務場景。記住：先優化查詢，再優化演算法，最後才考慮架構變更。