生成一棵树
例如有list 数组，需要整理成森林
public class Tree {
private Integer id;
private String code;
private String name;
protected Integer pid;
private List<Tree> children;
}
public static List<Tree> initByList() {
List<Tree> lists = new ArrayList<>();
// 第一层的节点
lists.add(new Tree(1, 0));
// 第二层的节点
lists.add(new Tree(11, 1));
lists.add(new Tree(12, 1));
lists.add(new Tree(13, 1));
// 第三层的节点
lists.add(new Tree(111, 11));
lists.add(new Tree(112, 11));
lists.add(new Tree(113, 11));
lists.add(new Tree(114, 11));
lists.add(new Tree(115, 11));
lists.add(new Tree(116, 11));
lists.add(new Tree(121, 12));
lists.add(new Tree(122, 12));
lists.add(new Tree(123, 12));
// 第四层的节点
lists.add(new Tree(1131, 113));
lists.add(new Tree(1132, 113));
lists.add(new Tree(1161, 116));
lists.add(new Tree(1231, 123));
lists.add(new Tree(1232, 123));
//另一颗树
// 第一层的节点
lists.add(new Tree(2, 0));
// 第二层的节点
lists.add(new Tree(21, 2));
lists.add(new Tree(22, 2));
lists.add(new Tree(23, 2));
Collections.shuffle(lists);
return lists;
}
整理一棵树有两个思路，根据父亲找儿子、根据儿子找父亲。
根据父亲找儿子
//找儿子: 根据条件 整理一棵森林
public static List<Tree> organizationByCondition(List<Tree> trees, Predicate<Tree> rootPredicate) {
List<Tree> roots = new ArrayList<>();
for (Tree tree : trees) {
//是 root 节点
if (rootPredicate.test(tree)) {
roots.add(organizationByRoot(trees,tree));
}
}
return roots;
}
//找儿子: 根据根节点 整理一棵树
private static Tree organizationByRoot(List<Tree> trees, Tree root) {
//需要找儿子节点的集合
Queue<Tree> immediately = new ArrayDeque<>();
immediately.add(root);
while (!immediately.isEmpty()) {
Tree t = immediately.poll();
for (Tree c : trees) {
if (Objects.equals(c.getPid(), t.getId())) {
t.getChildren().add(c);
//如果找到了孩子，那么添加到队列继续找孩子的孩子
immediately.add(c);
}
}
}
return root;
}
根据儿子找父亲
//找父亲:根据条件 整理一棵森林
public static List<Tree> organization(List<Tree> trees) {
List<Tree> roots = new ArrayList<>();
Queue<Tree> chaos = new ArrayDeque<>(trees);
//查找自己的父亲
while (!chaos.isEmpty()) {
Tree t = chaos.poll();
if (!findParent(trees, t)) {
//没有父亲节点那么,认为是根节点
roots.add(t);
}
//此处可处理排序问题
}
return roots;
}
private static boolean findParent(List<Tree> immediately, Tree t) {
for (Tree parent : immediately) {
if (Objects.equals(parent.getId(), t.getPid())) {
parent.getChildren().add(t);
return true;
}
}
return false;
}
将一颗树重新变换回list
/**
* 换成list
*/
public List<Tree> treeToList(Tree init) {
List<Tree> R = new ArrayList<>();
//先进先出
Queue<Tree> queue = new ArrayDeque<>();
queue.add(init);
while (!queue.isEmpty()) {
Tree poll = queue.poll();
R.add(poll);
System.out.println(poll.getName());
List<Tree> children = poll.getChildren();
if (children == null || children.isEmpty()) {
continue;
}
for (Tree child : children) {
if (child != null)
queue.add(child);
}
}
return R;
}
查找符合条件的节点
/**
* 查找一个符合条件的节点
*/
public Tree findOneByCondition(Tree init, Predicate<Tree> predicate1) {
//先进先出
Queue<Tree> queue = new ArrayDeque<>();
queue.add(init);
while (!queue.isEmpty()) {
Tree poll = queue.poll();
if (predicate1.test(poll)) return poll;
List<Tree> children = poll.getChildren();
if (children == null || children.isEmpty()) {
continue;
}
for (Tree child : children) {
if (child != null)
queue.add(child);
}
}
return null;
}
/**
* 查找所有符合条件的节点
*/
public List<Tree> findListByCondition(Tree init, Predicate<Tree> predicate1) {
List<Tree> r = new ArrayList<>();
//先进先出
Queue<Tree> queue = new ArrayDeque<>();
queue.add(init);
while (!queue.isEmpty()) {
Tree poll = queue.poll();
if (predicate1.test(poll)) {
r.add(poll);
}
List<Tree> children = poll.getChildren();
if (children == null || children.isEmpty()) {
continue;
}
for (Tree child : children) {
if (child != null)
queue.add(child);
}
}
return r;
}
查找指定层级: 这个需要两个队列分别存放父亲、儿子集合。然后来回交换，每交换一次，即一层遍历结束。
/**
* 查找指定层级的节点
*/
public Map<Integer, List<Tree>> findByLevel(Tree init, Predicate<Integer> predicate) {
Map<Integer, List<Tree>> R = new HashMap<>();
//如果需要获取第一个
if (predicate.test(0)) {
putAvoidNull(R, 0, init);
}
Queue<Tree> parent = new ArrayDeque<>();
Queue<Tree> children = new ArrayDeque<>();
parent.add(init);
int layer = 0;
while (!parent.isEmpty() || !children.isEmpty()) {
if (!parent.isEmpty()) { // parent队列不为空时, 将头节点的子节点放入children队列.
Tree node = parent.poll();
if (node.getChildren() != null) {
node.getChildren().forEach(child -> children.add(child));
}
} else {
layer++;
for (Tree child : children) {
if (predicate.test(layer)) {
putAvoidNull(R, layer, child);
}
}
// 将parent队列替换为children 队列
parent.addAll(children);
// 清空children队列
children.clear();
}
}
return R;
}
查找树的全路径：有两种方法1 递归 2非递归方法
递归方式不推荐
/**
* 根据查询条件, 纵向查找全路径
*/
public void findPathByCondition(Tree root, String path, List<String> pathList, Predicate<Tree> predicate1) {
//已经查找到退出循环
if (!pathList.isEmpty()) {
return;
}
if (predicate1.test(root)) {
path = path + root.getName();
pathList.add(path); //将结果保存在list中
} else { //非叶子节点
path = path + "/" + root.getName(); //进行子节点的递归
List<Tree> iterator = root.getChildren();
for (Tree tree : iterator) {
findPathByCondition(tree, path, pathList, predicate1);
}
}
}
推荐非递归方式
/**
* 非递归版本
*
* @param root
* @param predicate
* @return
*/
public static List<Tree> findPath(Tree root, Predicate<Tree> predicate) {
if (root == null) {
return null;
}
Stack<Tree> path = new Stack<>();
int level = 0;
//支持最大100层 index 是层数, value 元素数量
int[] layer = new int[100];
Stack<Tree> s = new Stack<>();
s.push(root);
//根节点是第0层
layer[level]++;
while (!s.isEmpty()) {
//查找仍有数据的层
while (layer[level] < 1){
level--;
path.pop();
}
Tree temp = s.pop();
path.push(temp);
//已经找到该节点
if (predicate.test(temp)) {
return path;
}
//记录当前层元素数量
layer[level]--;
List<Tree> children = temp.getChildren();
if (children == null || children.isEmpty()) {
path.pop();
continue;
}
level++;
//递归子节点
for (Tree child : children) {
s.push(child);
layer[level]++;
}
}
return null;
}
