文章目錄
- 1. 前言
- 2. 樹結構
- 3. 具體實現邏輯
- 3.1 TreeNode
- 3.2 TreeUtils
- 3.3 例子
- 4. 小結
1. 前言
樹結構的生成在項目中應該都比較常見，比如部門結構樹的生成，目錄結構樹的生成，但是大家有沒有想過，如果在一個項目中有多個樹結構，那么每一個都要定義一個生成方法顯然是比較麻煩的，所以我們就想寫一個通用的生成樹方法，下面就來看下如何來寫。
2. 樹結構
看上面的圖，每一個節點都會有三個屬性
- parentId 表示父節點 ID，根節點的父結點 ID = null
- id 表示當前節點 ID，這個 ID 用來標識一個節點
- children 是當前節點的子節點
那么上面來介紹完基本的幾個屬性，下面就來看下具體的實現了。
3. 具體實現邏輯
3.1 TreeNode
TreeNode 是公共節點，就是頂層父類，里面的屬性就是上面圖中的三個。
@Data
@AllArgsConstructor
@NoArgsConstructor
@Accessors(chain = true)
public class TreeNode<T, V> {private T parentId;private T id;private List<TreeNode<T, V>> children;public TreeNode(T parentId, T id) {this.parentId = parentId;this.id = id;}public void addChild(TreeNode<T, 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 TreeNode<T, V>> List<V> buildTree(List<V> flatList) {if (flatList == null || flatList.isEmpty()) {return null;}Map<T, TreeNode<T, V>> nodeMap = new HashMap<>();for (TreeNode<T, V> node : flatList) {nodeMap.put(node.getId(), node);}// 查找根節點List<V> rootList = new ArrayList<>();for (V node : flatList) {// 如果父節點為空，就是一個根節點if (node.getParentId() == null) {rootList.add(node);} else {// 父節點不為空，就是子節點TreeNode<T, 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 TreeNode<T, V>> List<V> buildTreeWithCompare(List<V> flatList, Comparator<V> comparator) {if (flatList == null || flatList.isEmpty()) {return Collections.emptyList(); // 返回空列表而不是null，這通常是一個更好的實踐}// 子節點分組Map<T, List<V>> childGroup = flatList.stream().filter(v -> v.getParentId() != null).collect(Collectors.groupingBy(V::getParentId));// 找出父節點List<V> 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 TreeNode<T, V>> void buildTreeRecursive(V parent, Map<T, List<V>> childGroup, Comparator<V> comparator) {List<V> 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 TreeNode<T, V>> long findTreeNodeCount(TreeNode<T, V> root) {if (root == null) {return 0;}long res = 1;List<TreeNode<T, V>> children = root.getChildren();if (children == null || children.isEmpty()) {return res;}for (TreeNode<T, V> child : children) {res += findTreeNodeCount(child);}return res;
}
上面是傳入一個根節點，獲取這棵樹的節點數，而下面的就是傳入一個集合來分別獲取節點數，里面也是調用了上面的 findTreeNodeCount 方法去獲取。
/*** 查詢給定集合的節點數** @param nodes 根節點集合* @param <T>* @param <V>* @return*/
public static <T, V extends TreeNode<T, V>> HashMap<V, Long> findTreeNodeCount(List<V> nodes) {if (nodes == null || nodes.isEmpty()) {return new HashMap<>(); // 返回空列表而不是null，這通常是一個更好的實踐}HashMap<V, Long> map = new HashMap<>();for (V root : nodes) {map.put(root, findTreeNodeCount(root));}return map;
}
下面再給一下獲取數的深度的方法。
// 查找樹的最大深度
private static <T, V extends TreeNode<T, V>> int getMaxDepthV(TreeNode<T, 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 TreeNode<T, V>> int getMaxDepth(V root) {return getMaxDepthV(root);
}
最后，我們拿到一棵樹之后，肯定有時候會希望在里面查找一些具有特定屬性的節點，比如某個節點名字是不是以 xx 開頭 … ，這時候就可以用下面的方法。
// 查找所有具有特定屬性的節點
public static <T, V extends TreeNode<T, V>> List<V> findAllNodesByProperty(TreeNode<T, V> root, Function<V, Boolean> predicate) {if (root == null) {return Collections.emptyList();}List<V> result = new ArrayList<>();// 符合屬性值if (predicate.apply((V) root)) {result.add((V) root);}if (root.getChildren() == null || root.getChildren().isEmpty()) {return result;}for (TreeNode<T, V> child : root.getChildren()) {result.addAll(findAllNodesByProperty(child, predicate));}return result;
}
好了，方法就這么多了，其他方法如果你感興趣也可以繼續補充下去，那么這些方法是怎么用的呢？范型的好處要怎么體現呢？下面就來看個例子。
3.3 例子
首先我們有一個部門類，里面包括部門的名字，然后我需要對這個部門集合來構建一棵部門樹。
@Data
@ToString
@NoArgsConstructor
public class Department extends TreeNode<String, 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) {List<Department> 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"));List<Department> departments = TreeUtils.buildTreeWithCompare(flatList, (o1, o2) -> {return o2.getName().compareTo(o1.getName());});Department root = departments.get(0);List<Department> 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(name=East Sales), Department(name=East Sales Team 2), Department(name=East Sales Team 1)]
3
{Department(name=East Sales)=3, Department(name=East Sales Team 2)=1, Department(name=East Sales Team 1)=1}4. 小結
工具類就寫好了，從例子就可以看出范型的好處了，用了范型之后只要實現類繼承了 TreeNode，就可以直接用 TreeUtils 里面的方法，并且返回的還是具體的實現類，而不是 TreeNode。
如有錯誤，歡迎指出！！！
