Java 实现通用高效树结构转换算法

在众多 Java 应用场景中，我们常常会遇到这样一个需求：将一组扁平的数据列表转化为树状结构。比如说，处理菜单数据时，数据库里存储的可能是一条条孤立的菜单记录，每条记录包含自身 ID 和父菜单 ID，而前端展示却需要一个完整的菜单树；再如组织架构数据，数据库中的员工信息是分散的，若要直观呈现部门与员工的层级关系，也需要构建树结构。那么，如何高效、通用地实现这种转换呢？今天我们就来详细探讨一下。

1、算法核心思路剖析

要把扁平的节点列表转化为树状结构，我们可以采用以下几个关键步骤：

1.1 节点映射

首先，我们需要把节点列表转换为一个 Map，这个 Map 的键是节点的 ID，值是对应的节点对象。这样做的好处是，后续查找某个节点时，时间复杂度能控制在 $O(1)$，大大提高了查找效率。

1.2 树的构建

接着，我们遍历整个节点列表，为每个节点找到它的父节点，然后把该节点添加到其父节点的子节点列表中。

1.3 筛选根节点

最后，从所有节点中筛选出那些没有父节点的节点，这些节点就是树的根节点。

2、代码详细实现

2.1 接口定义

我们先定义一个 TreeNode 接口，这个接口规定了树节点的基本行为：

public interface TreeNode<T> {
    T getParentId();
    T getId();
    <C extends TreeNode<T>> void addChild(C child);
}

这个接口包含三个重要方法：

• getParentId()：用于获取节点的父节点 ID。
• getId()：获取节点自身的 ID。
• addChild(C child)：将一个子节点添加到当前节点的子节点列表中。

2.2 构建树的核心方法

下面是实现树构建的通用 buildTree 方法：

import java.util.*;
import java.util.stream.Collectors;

public class TreeUtil {
    public static <T, R extends TreeNode<T>> List<R> buildTree(List<R> nodes) {
        // 输入验证
        if (nodes == null) {
            return new ArrayList<>();
        }
        // nodes 转换为 id, node 的 Map
        Map<T, R> nodeMap = nodes.stream().collect(Collectors.toMap(TreeNode::getId, n -> n));
        for (R node : nodes) {
            T parentId = node.getParentId();
            if (parentId == null) {
                continue;
            }
            R parent = nodeMap.get(parentId);
            if (parent != null) {
                parent.addChild(node);
            } else {
                // 处理找不到父节点的情况，这里可以记录日志
                System.err.println("Parent node with id " + parentId + " not found for node " + node.getId());
            }
        }
        return nodes.stream().filter(n -> n.getParentId() == null).collect(Collectors.toList());
    }
}

这个方法的具体实现步骤如下：

1. 输入验证：对传入的节点列表进行检查，如果列表为 null，则直接返回一个空列表，避免后续出现空指针异常。
2. 节点映射：利用 Java 8 的 Stream API，将节点列表转换为 Map，方便后续快速查找节点。
3. 构建树：遍历节点列表，为每个节点查找其父节点。若找到父节点，则将该节点添加到父节点的子节点列表中；若未找到，则输出错误信息，这里可以根据实际需求添加更完善的日志记录。
4. 筛选根节点：再次使用 Stream API，筛选出所有没有父节点的节点，这些节点构成了树的根节点列表。

3、单元测试验证

为了确保 buildTree 方法的正确性，我们使用 JUnit 5 编写了单元测试：

import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.jupiter.api.Assertions.assertEquals;

class TreeUtilTest {
    static class TestNode implements TreeUtil.TreeNode<Integer> {
        private final Integer id;
        private final Integer parentId;
        private final List<TestNode> children = new ArrayList<>();

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

        @Override
        public Integer getParentId() {
            return parentId;
        }

        @Override
        public Integer getId() {
            return id;
        }

        @Override
        public <C extends TreeUtil.TreeNode<Integer>> void addChild(C child) {
            children.add((TestNode) child);
        }

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

    @Test
    void testBuildTree() {
        // 创建测试节点
        TestNode root = new TestNode(1, null);
        TestNode child1 = new TestNode(2, 1);
        TestNode child2 = new TestNode(3, 1);
        TestNode grandChild = new TestNode(4, 2);

        List<TestNode> nodes = List.of(root, child1, child2, grandChild);

        // 构建树
        List<TestNode> tree = TreeUtil.buildTree(nodes);

        // 验证根节点数量
        assertEquals(1, tree.size());
        // 验证根节点的子节点数量
        assertEquals(2, tree.get(0).getChildren().size());
        // 验证子节点的子节点数量
        assertEquals(1, tree.get(0).getChildren().get(0).getChildren().size());
    }
}

在这个单元测试中，我们创建了一个简单的树结构，包含根节点、子节点和孙节点。然后调用 buildTree 方法构建树，并通过 assertEquals 方法验证树的结构是否符合预期，包括根节点数量、根节点的子节点数量以及子节点的子节点数量等。

4、总结与优势

通过 TreeNode 接口和 buildTree 方法，我们实现了一个高效且通用的树结构转换算法。该算法具有以下优势：

• 时间复杂度低：整个算法的时间复杂度为 O(n)，因为只需要对节点列表进行一次遍历。同时，利用 Map 存储节点，查找父节点的时间复杂度为 O(1)，提高了整体性能。
• 通用性强：通过泛型和接口的使用，该方法可以处理不同类型的节点数据，只要节点类实现了 TreeNode 接口即可。
• 健壮性高：添加了输入验证和异常处理，避免了空指针异常，并且对找不到父节点的情况进行了处理，增强了代码的稳定性。

希望通过本文的介绍，大家能更好地理解和运用这个树结构转换算法，在实际开发中提高效率。