美文网首页
java 树和森林操作

java 树和森林操作

作者: 田才 | 来源:发表于2023-04-14 12:50 被阅读0次

生成一棵树

例如有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;
    }

相关文章

  • 树和森林

    一、树的存储 1. 双亲表示法 双亲表示法使用一个顺序表来存储树中的节点,同时为表示节点间的关系,在每个节点中附设...

  • 树和森林

  • 树和森林

    1. 树:递归的定义,节点不相交。 2.森林:多个不相交的树的集合 树的表示法: 图 广义表 树的存储:比较...

  • 树和森林

    树和森林 树的存储结构: 双亲表示法 孩子表示法 利用图表示树 孩子兄弟表示法(二叉树表示法):链表中每个结点的两...

  • 百度面试总结

    1. 数据结构 链表 基本操作 java实现 B+树 基本操作 java实现 2. 算法 回文判断 3. 多线程 ...

  • Java集合系列-HashMap 1.8(二)

    接上篇Java集合系列-HashMap 1.8(一) 3.5 红黑树 3.5.1 树形化操作 3.5.1.1 操作...

  • 树和森林(六)

    1. 树的存储结构 双亲表示法孩子表示法利用图表示树孩子兄弟表示法(二叉树表示法):链表中每个结点的两指针域分别指...

  • Java_二叉树概念及基本操作

    树、森林和二叉树的转换 树转换为二叉树 森林转换为树 二叉树转换为树 二叉树转换为森林 代码

  • 树和森林,森林和二叉树的转换,树和森林的遍历

    1 树的存储结构 1)双亲表示法 用一组连续的存储空间来存储树的结点,同时在每个结点中附加一个指数器(整数域),用...

  • java学习路线

    javaSE java基础语法 java文件操作 java网络操作 java多线程 java数据库操作 java ...

网友评论

      本文标题:java 树和森林操作

      本文链接:https://www.haomeiwen.com/subject/fittjdtx.html