java 树和森林操作

生成一棵树

例如有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()) {
            Tree temp = s.pop();
            //查找仍有数据的层
            while (layer[level] < 1){
                level--;
                path.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;
    }