企业网站配色,大连承揽营销型网站公司,ui设计的就业前景,宠物美容网站建设合同书文章目录 1. 前言2. 树结构3. 具体实现逻辑3.1 TreeNode3.2 TreeUtils3.3 例子 4. 小结 1. 前言
树结构的生成在项目中应该都比较常见#xff0c;比如部门结构树的生成#xff0c;目录结构树的生成#xff0c;但是大家有没有想过#xff0c;如果在一个项目中有多个树结构比如部门结构树的生成目录结构树的生成但是大家有没有想过如果在一个项目中有多个树结构那么每一个都要定义一个生成方法显然是比较麻烦的所以我们就想写一个通用的生成树方法下面就来看下如何来写。 2. 树结构 看上面的图每一个节点都会有三个属性
parentId 表示父节点 ID根节点的父结点 ID nullid 表示当前节点 ID这个 ID 用来标识一个节点children 是当前节点的子节点
那么上面来介绍完基本的几个属性下面就来看下具体的实现了。 3. 具体实现逻辑
3.1 TreeNode
TreeNode 是公共节点就是顶层父类里面的属性就是上面图中的三个。
Data
AllArgsConstructor
NoArgsConstructor
Accessors(chain true)
public class TreeNodeT, V {private T parentId;private T id;private ListTreeNodeT, V children;public TreeNode(T parentId, T id) {this.parentId parentId;this.id id;}public void addChild(TreeNodeT, V treeNode){if(children null){children new ArrayList();}children.add(treeNode);}}TreeNode 里面的 id 都是用的范型其中 T 就是 id 的类型因为这个 id 有可能是 Long、Int、String … 类型不一定是 Long。另一个 V 就是具体的节点类型。
使用范型的好处就是扩展性高不需要把属性写死。 3.2 TreeUtils
这个是工具类专门实现树的构建以及一些其他的方法下面一个一个来看。首先是创建树的方法
/*** 构建一棵树** param flatList* param T* param V* return*/
public static T, V extends TreeNodeT, V ListV buildTree(ListV flatList) {if (flatList null || flatList.isEmpty()) {return null;}MapT, TreeNodeT, V nodeMap new HashMap();for (TreeNodeT, V node : flatList) {nodeMap.put(node.getId(), node);}// 查找根节点ListV rootList new ArrayList();for (V node : flatList) {// 如果父节点为空就是一个根节点if (node.getParentId() null) {rootList.add(node);} else {// 父节点不为空就是子节点TreeNodeT, V parent nodeMap.get(node.getParentId());if (parent ! null) {parent.addChild(node);} else {rootList.add(node);}}}return rootList;
}整体时间复杂度O(n)创建的时候传入节点集合然后返回根节点集合。里面的逻辑是首先放到一个 nodeMap 中然后遍历传入的集合根据 parentId 进行不同的处理。逻辑不难看注释即可。但是创建树的时候有时候我们希望根据某个顺序对树进行排序比如同一层的我想根据名字或者 id 进行排序顺序或者倒序都可以那么就可以使用下面的方法。
/**
* 构建一棵排序树
*
* param flatList
* param comparator
* param T
* param V
* return
*/
public static T, V extends TreeNodeT, V ListV buildTreeWithCompare(ListV flatList, ComparatorV comparator) {if (flatList null || flatList.isEmpty()) {return Collections.emptyList(); // 返回空列表而不是null这通常是一个更好的实践}// 子节点分组MapT, ListV childGroup flatList.stream().filter(v - v.getParentId() ! null).collect(Collectors.groupingBy(V::getParentId));// 找出父节点ListV roots flatList.stream().filter(v - v.getParentId() null).sorted(comparator) // 根据提供的比较器对根节点进行排序.collect(Collectors.toList());// 构建树for (V root : roots) {buildTreeRecursive(root, childGroup, comparator);}return roots;
}private static T, V extends TreeNodeT, V void buildTreeRecursive(V parent, MapT, ListV childGroup, ComparatorV comparator) {ListV children childGroup.get(parent.getId());if (children ! null) {// 对子节点进行排序children.sort(comparator);// 将排序后的子节点添加到父节点中children.forEach(parent::addChild);// 递归对子节点继续处理children.forEach(child - buildTreeRecursive(child, childGroup, comparator));}
}这里面是使用的递归其实也可以使用层次遍历的方式来写或者直接用第一个 buildTree 方法来往里面套也行。
上面这两个是关键的方法那么下面再给出一些其他的非必要方法比如查询节点数。下面这个方法就是获取以 root 为根的数的节点数。
/*** 查询以 root 为根的树的节点数** param root* param T* param V* return*/
private static T, V extends TreeNodeT, V long findTreeNodeCount(TreeNodeT, V root) {if (root null) {return 0;}long res 1;ListTreeNodeT, V children root.getChildren();if (children null || children.isEmpty()) {return res;}for (TreeNodeT, V child : children) {res findTreeNodeCount(child);}return res;
}上面是传入一个根节点获取这棵树的节点数而下面的就是传入一个集合来分别获取节点数里面也是调用了上面的 findTreeNodeCount 方法去获取。
/*** 查询给定集合的节点数** param nodes 根节点集合* param T* param V* return*/
public static T, V extends TreeNodeT, V HashMapV, Long findTreeNodeCount(ListV nodes) {if (nodes null || nodes.isEmpty()) {return new HashMap(); // 返回空列表而不是null这通常是一个更好的实践}HashMapV, Long map new HashMap();for (V root : nodes) {map.put(root, findTreeNodeCount(root));}return map;
}下面再给一下获取数的深度的方法。
// 查找树的最大深度
private static T, V extends TreeNodeT, V int getMaxDepthV(TreeNodeT, V root) {if (root null || root.getChildren() null || root.getChildren().isEmpty()) {return 1;}return 1 root.getChildren().stream().mapToInt(TreeUtils::getMaxDepthV).max().getAsInt();
}public static T, V extends TreeNodeT, V int getMaxDepth(V root) {return getMaxDepthV(root);
}最后我们拿到一棵树之后肯定有时候会希望在里面查找一些具有特定属性的节点比如某个节点名字是不是以 xx 开头 … 这时候就可以用下面的方法。
// 查找所有具有特定属性的节点
public static T, V extends TreeNodeT, V ListV findAllNodesByProperty(TreeNodeT, V root, FunctionV, Boolean predicate) {if (root null) {return Collections.emptyList();}ListV result new ArrayList();// 符合属性值if (predicate.apply((V) root)) {result.add((V) root);}if (root.getChildren() null || root.getChildren().isEmpty()) {return result;}for (TreeNodeT, V child : root.getChildren()) {result.addAll(findAllNodesByProperty(child, predicate));}return result;
}好了方法就这么多了其他方法如果你感兴趣也可以继续补充下去那么这些方法是怎么用的呢范型的好处要怎么体现呢下面就来看个例子。 3.3 例子
首先我们有一个部门类里面包括部门的名字然后我需要对这个部门集合来构建一棵部门树。
Data
ToString
NoArgsConstructor
public class Department extends TreeNodeString, Department {private String name;public Department(String id, String parentId, String name){super(parentId, id);this.name name;}}构建的方法如下
public class Main {public static void main(String[] args) {ListDepartment flatList new ArrayList();flatList.add(new Department(1, null, Sales));flatList.add( new Department(2, 1, East Sales));flatList.add( new Department(3, 1,West Sales));flatList.add( new Department(4, 2,East Sales Team 1));flatList.add( new Department(5, 2,East Sales Team 2));flatList.add( new Department(6, 3,West Sales Team 1));ListDepartment departments TreeUtils.buildTreeWithCompare(flatList, (o1, o2) - {return o2.getName().compareTo(o1.getName());});Department root departments.get(0);ListDepartment nodes TreeUtils.findAllNodesByProperty(root, department - department.getName().startsWith(East));System.out.println(nodes);System.out.println(TreeUtils.getMaxDepth(root));System.out.println(TreeUtils.findTreeNodeCount(nodes));}}
可以看下 buildTreeWithCompare 的输出 其他的输出如下
[Department(nameEast Sales), Department(nameEast Sales Team 2), Department(nameEast Sales Team 1)]
3
{Department(nameEast Sales)3, Department(nameEast Sales Team 2)1, Department(nameEast Sales Team 1)1} 4. 小结
工具类就写好了从例子就可以看出范型的好处了用了范型之后只要实现类继承了 TreeNode就可以直接用 TreeUtils 里面的方法并且返回的还是具体的实现类而不是 TreeNode。 如有错误欢迎指出
