生成一棵樹
例如有l(wèi)ist 數(shù)組，需要整理成森林
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<>();
// 第一層的節(jié)點
lists.add(new Tree(1, 0));
// 第二層的節(jié)點
lists.add(new Tree(11, 1));
lists.add(new Tree(12, 1));
lists.add(new Tree(13, 1));
// 第三層的節(jié)點
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));
// 第四層的節(jié)點
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));
//另一顆樹
// 第一層的節(jié)點
lists.add(new Tree(2, 0));
// 第二層的節(jié)點
lists.add(new Tree(21, 2));
lists.add(new Tree(22, 2));
lists.add(new Tree(23, 2));
Collections.shuffle(lists);
return lists;
}
整理一棵樹有兩個思路，根據(jù)父親找兒子、根據(jù)兒子找父親。
根據(jù)父親找兒子
//找兒子: 根據(jù)條件 整理一棵森林
public static List<Tree> organizationByCondition(List<Tree> trees, Predicate<Tree> rootPredicate) {
List<Tree> roots = new ArrayList<>();
for (Tree tree : trees) {
//是 root 節(jié)點
if (rootPredicate.test(tree)) {
roots.add(organizationByRoot(trees,tree));
}
}
return roots;
}
//找兒子: 根據(jù)根節(jié)點 整理一棵樹
private static Tree organizationByRoot(List<Tree> trees, Tree root) {
//需要找兒子節(jié)點的集合
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);
//如果找到了孩子，那么添加到隊列繼續(xù)找孩子的孩子
immediately.add(c);
}
}
}
return root;
}
根據(jù)兒子找父親
//找父親:根據(jù)條件 整理一棵森林
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)) {
//沒有父親節(jié)點那么,認為是根節(jié)點
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;
}
查找符合條件的節(jié)點
/**
* 查找一個符合條件的節(jié)點
*/
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;
}
/**
* 查找所有符合條件的節(jié)點
*/
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;
}
查找指定層級: 這個需要兩個隊列分別存放父親、兒子集合。然后來回交換，每交換一次，即一層遍歷結(jié)束。
/**
* 查找指定層級的節(jié)點
*/
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隊列不為空時, 將頭節(jié)點的子節(jié)點放入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非遞歸方法
遞歸方式不推薦
/**
* 根據(jù)查詢條件, 縱向查找全路徑
*/
public void findPathByCondition(Tree root, String path, List<String> pathList, Predicate<Tree> predicate1) {
//已經(jīng)查找到退出循環(huán)
if (!pathList.isEmpty()) {
return;
}
if (predicate1.test(root)) {
path = path + root.getName();
pathList.add(path); //將結(jié)果保存在list中
} else { //非葉子節(jié)點
path = path + "/" + root.getName(); //進行子節(jié)點的遞歸
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 是層數(shù), value 元素數(shù)量
int[] layer = new int[100];
Stack<Tree> s = new Stack<>();
s.push(root);
//根節(jié)點是第0層
layer[level]++;
while (!s.isEmpty()) {
//查找仍有數(shù)據(jù)的層
while (layer[level] < 1){
level--;
path.pop();
}
Tree temp = s.pop();
path.push(temp);
//已經(jīng)找到該節(jié)點
if (predicate.test(temp)) {
return path;
}
//記錄當前層元素數(shù)量
layer[level]--;
List<Tree> children = temp.getChildren();
if (children == null || children.isEmpty()) {
path.pop();
continue;
}
level++;
//遞歸子節(jié)點
for (Tree child : children) {
s.push(child);
layer[level]++;
}
}
return null;
}
