树状结构数据
在业务开发过程在一些菜单上经常会遇到树状结构的数据。我们要知道树状结构数据的
树状数据结构特点
自身有ID、有父级ID（顶级的父级ID是空），有子集数据（是否为空无所谓）
所以我们得到一个类
import java.util.ArrayList;
import java.util.List;
public class TreeNode {
private int id;
private int parentId;
private String name;
private List<TreeNode> children = new ArrayList<>();
// 构造函数、getter和setter方法略...
}针对于树的工具封装如下：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class TreeUtils {
/**
* 遍历树，获取某节点下所有子树的数据
*/
public static List<TreeNode> getSubTree(List<TreeNode> treeNodes, int nodeId) {
for (TreeNode node : treeNodes) {
if (node.getId() == nodeId) {
return collectChildren(node);
}
}
return new ArrayList<>();
}
private static List<TreeNode> collectChildren(TreeNode node) {
List<TreeNode> subTree = new ArrayList<>();
subTree.add(node);
for (TreeNode child : node.getChildren()) {
subTree.addAll(collectChildren(child));
}
return subTree;
}
/**
* 从树上剔除指定ID的节点及其子节点
*/
public static List<TreeNode> removeNode(List<TreeNode> treeNodes, int nodeId) {
List<TreeNode> result = new ArrayList<>();
for (TreeNode node : treeNodes) {
if (node.getId() != nodeId) {
result.add(node);
node.setChildren(removeNode(node.getChildren(), nodeId));
}
}
return result;
}
/**
* 将树结构转换为List
*/
public static List<TreeNode> flattenTree(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
list.add(current);
queue.addAll(current.getChildren());
}
return list;
}
/**
* 将树结构转换为Map，以节点ID为键
*/
public static Map<Integer, TreeNode> convertTreeToMap(TreeNode root) {
Map<Integer, TreeNode> map = new HashMap<>();
fillMapWithTree(map, root);
return map;
}
private static void fillMapWithTree(Map<Integer, TreeNode> map, TreeNode node) {
map.put(node.getId(), node);
for (TreeNode child : node.getChildren()) {
fillMapWithTree(map, child);
}
}
/**
* 将List转换为树结构
*/
public static List<TreeNode> convertListToTree(List<TreeNode> list) {
Map<Integer, TreeNode> idNodeMap = new HashMap<>();
List<TreeNode> rootNodes = new ArrayList<>();
// 创建所有节点的映射
for (TreeNode node : list) {
idNodeMap.put(node.getId(), node);
}
// 构建树
for (TreeNode node : list) {
TreeNode parent = idNodeMap.get(node.getParentId());
if (parent != null) {
parent.getChildren().add(node);
} else {
rootNodes.add(node);
}
}
return rootNodes;
}
/**
* 将Map转换为树结构
*/
public static List<TreeNode> convertMapToTree(Map<Integer, TreeNode> map) {
List<TreeNode> roots = new ArrayList<>();
for (TreeNode node : map.values()) {
if (map.containsKey(node.getParentId())) {
TreeNode parent = map.get(node.getParentId());
parent.getChildren().add(node);
} else {
roots.add(node);
}
}
return roots;
}
/**
* 判断两个节点是否有相同的父节点
*/
public static boolean haveSameParent(TreeNode node1, TreeNode node2) {
return node1.getParentId() == node2.getParentId();
}
/**
* 判断两个节点的祖先节点是否一致
*/
public static boolean haveCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
List<Integer> ancestors1 = getAncestors(root, node1);
List<Integer> ancestors2 = getAncestors(root, node2);
// 查找两个列表是否有共同元素
for (Integer ancestor1 : ancestors1) {
if (ancestors2.contains(ancestor1)) {
return true;
}
}
return false;
}
/**
* 获取从根节点到指定节点的所有祖先节点的ID列表
*/
private static List<Integer> getAncestors(TreeNode root, TreeNode node) {
Map<Integer, TreeNode> nodeMap = convertTreeToMap(root);
List<Integer> ancestors = new ArrayList<>();
int parentId = node.getParentId();
while (parentId != 0) { // 假设根节点的parentId为0
ancestors.add(parentId);
TreeNode parentNode = nodeMap.get(parentId);
if (parentNode == null) {
break; // 如果父节点为空，则到达树的顶端
}
parentId = parentNode.getParentId();
}
return ancestors;
}
}注意，这里的方法都是基于TreeNode类的简单实现，实际使用时可能需要根据你的具体业务逻辑进行调整。例如，节点的唯一标识可以是其他类型而非int，树的遍历可以使用递归或非递归方式等。
特殊说明： 上述文章均是作者实际操作后产出。烦请各位，请勿直接盗用！转载记得标注原文链接：www.zanglikun.com 第三方平台不会及时更新本文最新内容。如果发现本文资料不全，可访问本人的Java博客搜索：标题关键字。以获取全部资料 ?
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录