帮我用Java实现一个算法,已知树的节点treeId,父节点parentId,根据父节点查询所有子节点并且在拼成一棵树
时间: 2024-05-12 21:16:29 浏览: 86
树父节点递归获取树子节点
5星 · 资源好评率100%
以下是一个使用Java实现的算法,可以根据父节点查询所有子节点并拼成一棵树:
```java
import java.util.*;
public class TreeNode {
private int treeId;
private int parentId;
private List<TreeNode> children;
public TreeNode(int treeId, int parentId) {
this.treeId = treeId;
this.parentId = parentId;
this.children = new ArrayList<>();
}
public int getTreeId() {
return treeId;
}
public int getParentId() {
return parentId;
}
public List<TreeNode> getChildren() {
return children;
}
public void addChild(TreeNode child) {
children.add(child);
}
public static List<TreeNode> buildTree(List<TreeNode> nodes) {
Map<Integer, TreeNode> nodeMap = new HashMap<>();
for (TreeNode node : nodes) {
nodeMap.put(node.getTreeId(), node);
}
List<TreeNode> rootNodes = new ArrayList<>();
for (TreeNode node : nodes) {
if (node.getParentId() == 0) {
rootNodes.add(node);
} else {
TreeNode parent = nodeMap.get(node.getParentId());
if (parent != null) {
parent.addChild(node);
}
}
}
return rootNodes;
}
public static void main(String[] args) {
// 构造节点数据
List<TreeNode> nodes = new ArrayList<>();
nodes.add(new TreeNode(1, 0));
nodes.add(new TreeNode(2, 1));
nodes.add(new TreeNode(3, 1));
nodes.add(new TreeNode(4, 2));
nodes.add(new TreeNode(5, 4));
nodes.add(new TreeNode(6, 3));
nodes.add(new TreeNode(7, 3));
nodes.add(new TreeNode(8, 6));
nodes.add(new TreeNode(9, 7));
// 构建树
List<TreeNode> rootNodes = TreeNode.buildTree(nodes);
// 打印树
for (TreeNode rootNode : rootNodes) {
printTree(rootNode, 0);
}
}
private static void printTree(TreeNode node, int level) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < level; i++) {
sb.append(" ");
}
sb.append(node.getTreeId());
System.out.println(sb.toString());
for (TreeNode child : node.getChildren()) {
printTree(child, level + 1);
}
}
}
```
该算法的核心是 `buildTree` 方法,它接受一个节点列表作为参数,返回一个根节点列表。该方法首先遍历节点列表,将每个节点存储在一个 `Map` 中,以便可以根据节点的 `treeId` 快速查找节点。然后遍历节点列表,对于每个节点,如果 `parentId` 为 0,则将其添加到根节点列表中;否则,从 `Map` 中获取其父节点,如果父节点存在,则将该节点添加为父节点的子节点。最后返回根节点列表即可。
在 `main` 方法中,我们构造了一个节点列表,并使用 `buildTree` 方法构建了一棵树。然后调用 `printTree` 方法打印树的结构。该方法接受一个节点和一个层级作为参数,递归地打印树的结构。
阅读全文