package com.estate.expert.admin.utils.tree.helper;
|
|
import com.estate.expert.admin.utils.tree.TreeNode;
|
import lombok.extern.slf4j.Slf4j;
|
|
import java.util.ArrayDeque;
|
import java.util.Deque;
|
import java.util.List;
|
|
/**
|
* 树的构建器
|
*
|
* 主要用于从一棵树生成另外一个相同结构的树
|
*
|
*/
|
@Slf4j
|
public class TreeHelper {
|
|
/**
|
* 构建新树
|
*
|
* 采用深度优先遍历
|
* 自上而下遍历
|
* 适合层级树，可以较快的裁剪掉不需要的路径
|
*/
|
public static <T, K> TreeNode<K> convertTree(TreeNode<T> node, NodeConvertor<T, K> convertor, NodeFilter<T> filter) {
|
if(!filter.shouldAdd(node))
|
return null;
|
|
TreeNode<K> newNode = cloneNode(node);
|
newNode.setData(convertor.convert(node, newNode));
|
|
for (TreeNode<T> child : node.getChildren().values()) {
|
var newChild = convertTree(child, convertor, filter);
|
if(newChild != null)
|
newNode.addChild(newChild);
|
}
|
return newNode;
|
}
|
|
/**
|
* 单纯转换树，不进行裁剪
|
*/
|
public static <T, K> TreeNode<K> convertTree(TreeNode<T> node, NodeConvertor<T, K> convertor) {
|
return convertTree(node ,convertor, (n) -> true);
|
}
|
|
/**
|
* 裁剪树
|
*/
|
public static <T> TreeNode<T> pruneTree(TreeNode<T> node, NodeFilter<T> filter) {
|
return convertTree(node , (n, newNode)->{
|
return n.getData();
|
}, filter);
|
}
|
|
/**
|
* 按层级裁剪树
|
*/
|
public static <T> TreeNode<T> pruneTreeByLevels(TreeNode<T> node, List<Integer> levels) {
|
// 创建一个新的空节点作为新树的根节点
|
TreeNode<T> newRoot = cloneNode(node);
|
newRoot.setData(node.getData());
|
|
// 创建一个栈，用于存放当前正在处理的节点路径
|
Deque<TreeNode<T>> path = new ArrayDeque<>();
|
path.push(newRoot);
|
|
// 使用深度优先搜索遍历原始树
|
dfsPrune(node, 0, levels, path);
|
|
return newRoot;
|
}
|
|
/**
|
* 将路径转换为id
|
* @param path 路径
|
* @return id
|
*/
|
private static int pathToId(String path){
|
var parts = path.split("/");
|
int id = 0;
|
for(var part : parts){
|
if(part.isEmpty())
|
continue;
|
id = id * 1000 + Integer.parseInt(part);
|
}
|
return id;
|
}
|
|
/**
|
* 深度优先搜索裁剪树
|
* @param node 节点
|
* @param level 层级
|
* @param levels 层级列表
|
* @param path 路径
|
*/
|
private static <T> void dfsPrune(TreeNode<T> node, int level, List<Integer> levels, Deque<TreeNode<T>> path) {
|
if (levels.contains(level)) {
|
// 如果当前层级在指定的层级列表中，就复制当前节点到新树中
|
TreeNode<T> newNode = cloneNode(node);
|
|
// 由于存在跨层合并的情况，所以需要重新计算id，避免id冲突
|
var fullId = pathToId(node.getPath());
|
newNode.setId(fullId);
|
newNode.setData(node.getData());
|
path.peek().addChild(newNode);
|
path.push(newNode);
|
}
|
|
// 遍历子节点
|
for (TreeNode<T> child : node.getChildren().values()) {
|
dfsPrune(child, level + 1, levels, path);
|
}
|
|
if (levels.contains(level)) {
|
// 如果当前层级在指定的层级列表中，就从路径中移除当前节点
|
path.pop();
|
}
|
}
|
|
/**
|
* 自下而上遍历树
|
* 用于计算结果求解，需要先求解子节点的结果
|
*/
|
public static <T> void travel(TreeNode<T> node, NodeVisitor<T> visitor) {
|
if(node == null)
|
return;
|
for (TreeNode<T> child : node.getChildren().values()) {
|
travel(child, visitor);
|
}
|
visitor.visit(node);
|
}
|
|
/**
|
* 广度优先遍历树
|
* @param node 节点
|
* @param visitor 访问器
|
*/
|
public static <T> void bfsTravel(TreeNode<T> node, NodeVisitor<T> visitor){
|
var queue = new java.util.LinkedList<TreeNode<T>>();
|
queue.add(node);
|
|
while (!queue.isEmpty()){
|
var n = queue.poll();
|
visitor.visit(n);
|
queue.addAll(n.getChildren().values());
|
}
|
}
|
|
/**
|
* 打印树
|
* @param node 节点
|
*/
|
public static <T> void printTree(TreeNode<T> node){
|
if(node == null)
|
return;
|
bfsTravel(node, (n) -> {
|
log.info("{}", n);
|
});
|
}
|
|
/**
|
* 克隆节点
|
* @param node 节点
|
* @return 克隆节点
|
*/
|
private static <T, K> TreeNode<K> cloneNode(TreeNode<T> node) {
|
TreeNode<K> newNode = new TreeNode<>();
|
newNode.setId(node.getId());
|
newNode.setPath(node.getPath());
|
newNode.setName(node.getName());
|
return newNode;
|
}
|
|
}
|
