在Java中，如何利用parent_id将扁平列表转换为树形结构？

编程语言 2026-07-09

我在练习Java的数据结构，想把一组扁平的节点列表转换成树形结构。

每个节点都有一个id、一个名称和一个parentId。如果parentId为 null，则将该节点视为根节点。

问题在于我可以把扁平列表打印出来，但不确定将每个子节点与其父节点连接起来的最佳方法。

这是我的类的一个简化版本：

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

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

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

    public Long getId() {
        return id;
    }

    public Long getParentId() {
        return parentId;
    }

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

示例输入：

[ 
  { "id": 1, "name": "Assets", "parentId": null },
  { "id": 2, "name": "Current Assets", "parentId": 1 },
  { "id": 3, "name": "Cash", "parentId": 2 }  
]

期望输出：

Assets

 └── Current Assets

      └── Cash

我尝试了使用嵌套循环，但我觉得随着列表增多，效率会变差。

在Java中，使用Map或其他数据结构来构建这棵树，有哪些更好的做法？

解决方案

设置

第一步是根据你的 parentIds正确填充你的 children 字段。这样你也可以向前遍历树，而不仅仅是向后遍历。

由于你是基于（唯一）ID来标识节点，你也应该有一种通过ID获取节点的方法，因此把这件事作为第一步。

我假设你已经有办法遍历到你迄今为止创建的所有节点，所以我们来：

Map<Long, Node> idToNode = new HashMap<>();
for (Node node : nodes) {
  idToNode.put(node.getId(), node);
}

// or

Map<Long, Node> idToNode = nodes.stream().collect(Collectors.toMap(
  Node::getId,
  Function.identity()
));

接下来根据 parentIds填充 children 字段：

Node root = null;
for (Node node : nodes) {
  Long parentId = node.getParentId();
  if (parentId == null) {
    root = node;
    continue;
  }

  Node parent = idToNode.get(parerntId);
  // Caution: This contains check is expensive. Use Set instead of List for large tree structures
  if (!parent.children.contains(node)) {
    parent.children.add(node);
  }
}

现在 children 已经正确设置，我们也知道 root。你现在可以开始向前遍历树。

向前遍历

最后一部分是打印。为此，我们需要一个普通的DFS遍历。看看这张来自Google搜索结果第一页的图片：

这种（递归）的通用结构将是：

public void printTree(Node root) {
  printTree(root, 0);
}

private void printTree(Node current, int level) {
  // TODO Do something with the node...

  // Relax children
  for (Node child : current.getChildren()) {
    printTree(child, level + 1);
  }
}

打印

现在来处理结构的实际打印。当前的 level 将作为缩进的来源，我们每层使用两个空格：

private void printTree(Node current, int level) {
  String indent = " ".repeat(level * 2);
  IO.println(indent + "├─");

  // Relax children
  for (Node child : current.getChildren()) {
    printTree(child, level + 1);
  }
}

这已经让我们非常接近目标：

├─Assets
  ├─Current Assets
    ├─Cash
    ├─Foo
  ├─Bar
  ├─Baz

现在做一些小调整来处理。

根节点没有 `├─`

对于根节点的特殊处理，没有前导 ├─：

private void printTree(Node current, int level) {
  if (level != 0) {
    String indent = " ".repeat(level * 2);
    IO.println(indent + "├─");
  }

  // Relax children
  for (Node child : current.getChildren()) {
    printTree(child, level + 1);
  }
}

结束符号 `└─`

最后一部分是最后一个条目的额外符号，因此它是 └─，而不是始终是 ├─。为此，你需要知道 // Relax children 的迭代是否处于最后一个元素。若以 ArrayList 作为 children 的底层结构，这很容易，因为我们可以改用基于索引的循环。否则你需要稍微灵活一些。

public void printTree(Node root) {
  printTree(root, 0, false);
}

private void printTree(Node current, int level, boolean isLast) {
  if (level != 0) {
    String indent = " ".repeat(level * 2);
    String symbol = isLast ? "└─" : "├─";
    IO.println(indent + symbol);
  }

  // Relax all children but last
  List<Node> children = current.getChildren();
  for (int i = 0; i < children.size() - 1; i++) {
    Node child = children.get(i);
    printTree(child, level + 1, false);
  }

  // And now the last child
  Node lastChild = children.get(children.size() - 1);
  printTree(lastChild, level + 1, true);
}

就这样：

Assets
  |─Current Assets
    ├─Cash
    └─Foo
  ├─Bar
  └─Baz

不中断的连接

如果你还想让例如 Current Assets 与 Bar 之间的连线继续，你需要修改标识部分，在每一级缩进打印一个 |：

private void printTree(Node current, int level, boolean isLast) {
  if (level != 0) {
    for (int i = 0; i < level - 1; i++) {
      String lead = "  │";
      IO.print(lead);
    }
    String symbol = isLast ? "└─" : "├─";
    IO.println("  " + symbol);
  }

  // Relax all children but last
  List<Node> children = current.getChildren();
  for (int i = 0; i < children.size() - 1; i++) {
    Node child = children.get(i);
    printTree(child, level + 1, false);
  }

  // And now the last child
  Node lastChild = children.get(children.size() - 1);
  printTree(lastChild, level + 1, true);
}

最终结果：

Assets
  ├─Current Assets
  │ ├─Cash
  │ └─Foo
  ├─Bar
  └─Baz

备注

迭代DFS

值得一提的是，这目前是一个递归解法。对于较大的树结构，它会有问题。如果你需要支持大规模，请考虑切换到迭代变体。其基本设定大致是：

Queue<Node> nodesToProcess = Collections.asLifoQueue(new ArrayDeque<>());
nodesToProcess.add(rootNode); // add all starting nodes

Set<Node> visitedNodes = new HashSet<>();
while (!nodesToProcess.isEmpty()) {
  // Settle node
  Node currentNode = nodesToProcess.poll();
  if (!visitedNodes.add(currentNode)) {
    continue; // Already visited before
  }

  // Do something with the node
  System.out.println(currentNode); // Replace by whatever you need

  // Relax all outgoing edges
  for (Node neighbor : currentNode.getNeighbors()) {
    nodesToProcess.add(neighbor);
  }
}

但你需要做一些修改，以维持缩进层次。