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

技术文章 > Java > Java 实现通用高效树结构转换算法2

在 Java 实现通用高效树结构转换算法 中介绍了一种转换树结构的算法。在微信公众号的回复中，404 N’F 指出 TreeNode 接口设计存在问题，经过沟通后发现确实有一种更适合直接使用的实现方式，本文就是基于这一新设计的实现。

TreeNewBee 新设计

图：左侧是新的实现，右侧为旧的实现

旧版本实现中定义了 TreeNode<T> 接口，因此想使用这个工具类，就需要先实现这个接口，会产生较强的耦合性，虽然算法简单，但使用起来不够便捷。怎么才能更方便呢？

答案就是 Lambda 和函数式接口。将 TreeNode<T> 里面的3个方法拆分成3个独立的函数式接口，这样就可以不直接实现接口而直接使用工具类，适配性更强。主要的缺点是针对同一对象或结构时代码复用性稍弱。

@FunctionalInterface
public interface GetParentId<T, R> {
  T getParentId(R node);
}

@FunctionalInterface
public interface GetId<T, R> {
  T getId(R node);
}

@FunctionalInterface
public interface AddChild<R, C> {
  void addChild(R parent, C child);
}

这3个接口都作为方法参数传递给构建树的方法，通过这3个函数式接口的组合来实现树结构的转换。

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

下面通过多个示例演示用法，并展示其更广泛的通用性。

示例

1. 方法引用

这是最常见的用法。如果转换树结构的对象本身就有类似上述3个接口的方法，就可以直接使用方法引用，示例如下：

static class Node {
  private Integer id;
  private Integer parentId;
  private String name;
  private List<Node> children = new ArrayList<>();

  public Node(Integer id, Integer parentId, String name) {
    this.id = id;
    this.parentId = parentId;
    this.name = name;
  }

  // Getters and setters
  public Integer getId() { return id; }
  public void setId(Integer id) { this.id = id; }
  public Integer getParentId() { return parentId; }
  public void setParentId(Integer parentId) { this.parentId = parentId; }
  public String getName() { return name; }
  public void setName(String name) { this.name = name; }
  public List<Node> getChildren() { return children; }
  public void setChildren(List<Node> children) { this.children = children; }

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

@Test
void testBuildTree() {
  // 准备测试数据
  List<Node> nodes = Arrays.asList(
    new Node(1, null, "根节点"),
    new Node(2, 1, "子节点1"),
    new Node(3, 1, "子节点2"),
    new Node(4, 2, "孙节点1"),
    new Node(5, 2, "孙节点2"),
    new Node(6, 3, "孙节点3")
  );

  // 使用 TreeNewBee 构建树结构
  List<Node> tree = TreeNewBee.buildTree(
    nodes,
    Node::getParentId,  // GetParentId lambda
    Node::getId,        // GetId lambda
    Node::addChild      // AddChild lambda
  );

  // 验证树结构
  assertEquals(1, tree.size(), "应该只有一个根节点");
}

这里直接使用方法引用，复用性不受影响。如果觉得 addChild 方法相比 getter、setter 不够常见，也可以去掉该方法，然后使用下面的方式：

tree = TreeNewBee.buildTree(
        nodes,
        Node::getParentId,  // GetParentId lambda
        Node::getId,        // GetId lambda
        (p, c) -> p.getChildren().add(c) // AddChild lambda
);

如果你的 children 默认不初始化，还可以这样处理：

tree = TreeNewBee.buildTree(
        nodes,
        Node::getParentId,  // GetParentId lambda
        Node::getId,        // GetId lambda
        (p, c) -> {
            if(p.getChildren() == null) {
                p.setChildren(new ArrayList<>());
            }
            p.getChildren().add(c);
        } // AddChild lambda
);

2. Map 类型

对于对象类型，有了getter、setter就基本离不开上面的几种情况。当使用 Map 时，就有了更加灵活的处理方式。下面是一个示例：

@Test
void testBuildTreeWithMapType() {
    // 使用Map类型作为树节点
    List<Map<String, Object>> mapNodes = Arrays.asList(
        createMapNode(100L, null, "根目录", new ArrayList<>()),
        createMapNode(200L, 100L, "文档", new ArrayList<>()),
        createMapNode(300L, 100L, "图片", new ArrayList<>()),
        createMapNode(400L, 200L, "工作文档", new ArrayList<>()),
        createMapNode(500L, 200L, "个人文档", new ArrayList<>()),
        createMapNode(600L, 300L, "头像", new ArrayList<>())
    );

    // 构建树结构
    List<Map<String, Object>> tree = TreeNewBee.buildTree(mapNodes,
            map -> (Long) map.get("parentId"),
            map -> (Long) map.get("id"),
            (parent, child) -> {
                @SuppressWarnings("unchecked")
                List<Map<String, Object>> children = 
                  (List<Map<String, Object>>) parent.get("children");
                children.add(child);
            });

    // 验证结果
    assertEquals(1, tree.size(), "应该只有一个根节点");
}

// 辅助方法创建Map节点
private Map<String, Object> createMapNode(Long id, Long parentId, 
  String name, List<Map<String, Object>> children) {
    Map<String, Object> map = new HashMap<>();
    map.put("id", id);
    map.put("parentId", parentId);
    map.put("name", name);
    map.put("children", children);
    return map;
}

从上面示例可以看到函数式接口的灵活性和通用性。关于算法的内容就介绍到这里，接下来看一个你可能没有注意到的方法引用用法。

有趣的 Node::addChild 参数

不知道你有没有注意到，buildTree 最后一个参数是 AddChild<R, C> 接口，其方法签名是 void addChild(R parent, C child)，有两个参数，无返回值。但是我们使用时传递的 Node::addChild，这个方法的定义如下：

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

这个方法无返回值，只有一个参数，和我们接口的定义并不一致，为什么可以使用呢？

根据Java语言规范（JLS）15.13节，方法引用有四种形式：

1. 静态方法引用：ClassName::staticMethod
2. 实例方法引用（绑定接收者）：instance::instanceMethod
3. 实例方法引用（未绑定接收者）：ClassName::instanceMethod
4. 构造方法引用：ClassName::new

Node::addChild 属于第3种：未绑定接收者的实例方法引用。

编译时的类型推断过程，JLS规定，编译器会根据目标类型进行类型推断：

// 目标函数式接口
AddChild<R, C> { void addChild(R parent, C child); }

// 方法引用 Node::addChild
// 编译器推断过程：
// 1. addChild是Node的实例方法，需要一个接收者对象
// 2. 目标接口有两个参数：parent 和 child
// 3. 第一个参数(parent)作为方法调用的接收者
// 4. 第二个参数(child)作为方法的实际参数

JLS 15.13.3规定了参数映射规则：

• 对于未绑定的实例方法引用 C::m
• 如果目标函数式接口有n个参数，则：
  • 第1个参数作为方法调用的接收者
  • 第2到第n个参数作为方法m的实际参数

通过函数式接口的重新设计，我们成功解决了旧版本中接口耦合性强的问题。新的 TreeNewBee 实现不仅保持了原有算法的高效性，还大大提升了使用的便捷性和适配性。无论是普通对象、Map 类型，还是其他自定义结构，都可以通过简单的 Lambda 表达式或方法引用轻松实现树结构转换。虽然在代码复用性上有所权衡，但这种设计更符合现代 Java 开发中”组合优于继承”的理念，真正做到了开箱即用。