master

分支 (1)

管理

管理

master

java-se
/
src
/
test
/
java
/
org
/
example
/
se
/
RecursionTreeTest.java

package org.example.se;

import cn.hutool.core.util.StrUtil;
import com.fasterxml.jackson.core.type.TypeReference;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.junit.jupiter.api.Test;

import java.io.File;
import java.io.IOException;
import java.net.URL;
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;

/**
 * Java 实现树型数据递归，类似 Oracle 的 start with...connect by prior
 *
 * @author wangMaoXiong
 * @version 1.0
 * @date 2023/4/23 20:50
 */
public class RecursionTreeTest {

    /**
     * 查询某个节点下面的全部子孙节点(不含自己)——向下递归
     *
     * @param id           ：节点ID
     * @param treeDataList ：需要遍历的数据
     * @return ：返回自己下面的全部子孙节点
     */
    public static List<TreeDataDO> getChildNodes(String id, List<TreeDataDO> treeDataList) {
        List<TreeDataDO> returnDataList = new ArrayList<>();
        for (TreeDataDO treeDataDO : treeDataList) {
            if (StrUtil.equals(treeDataDO.getPid(), id)) {
                // 添加子节点
                returnDataList.add(treeDataDO);
                // 递归添加子节点下面的子节点
                returnDataList.addAll(getChildNodes(treeDataDO.getId(), treeDataList));
            }
        }
        return returnDataList;
    }

    /**
     * 查询某个节点下面的全部子孙节点(不含自己)——向下递归
     *
     * @param id           ：节点ID
     * @param treeDataList ：需要遍历的数据
     * @return ：返回自己下面的全部子孙节点
     */
    public static List<TreeDataDO> getChildEleList(String id, List<TreeDataDO> treeDataList) {
        List<TreeDataDO> returnDataList = new ArrayList<>();
        /**
         * Optional.ofNullable(xxx).orElse(new ArrayList<>())：如果集合为null则返回一个空集合
         * filter：返回条件成立的元素
         * forEach：遍历集合
         */
        Optional.ofNullable(treeDataList).orElse(new ArrayList<>())
                .stream()
                .filter(treeDataDO -> StrUtil.equals(treeDataDO.getPid(), id))
                .forEach(treeDataDO -> {
                    System.out.println("====" + treeDataDO);
                    // 添加子节点
                    returnDataList.add(treeDataDO);
                    // 递归添加子节点下面的子节点
                    returnDataList.addAll(getChildEleList(treeDataDO.getId(), treeDataList));
                });
        return returnDataList;
    }

    /**
     * 查询某个节点上面的全部父、祖父节点(不含自己)——向上递归
     *
     * @param pid          ：父节点ID
     * @param treeDataList ：需要遍历的数据
     * @return ：返回自己上面的全部父节点(包含父节点的父节点)
     */
    public static List<TreeDataDO> getParentNodes(String pid, List<TreeDataDO> treeDataList) {
        List<TreeDataDO> returnDataList = new ArrayList<>();
        for (TreeDataDO treeDataDO : treeDataList) {
            if (StrUtil.equals(treeDataDO.getId(), pid)) {
                // 添加父节点
                returnDataList.add(treeDataDO);
                // 递归添加父节点上面的父节点
                returnDataList.addAll(getParentNodes(treeDataDO.getPid(), treeDataList));
                // 父节点只会有一个，找到了，则直接返回，不用再继续.
                return returnDataList;
            }
        }
        return returnDataList;
    }

    /**
     * 查询某个节点上面的全部父、祖父节点(不含自己)——向上递归
     *
     * @param pid          ：父节点ID
     * @param treeDataList ：需要遍历的数据
     * @return ：返回自己上面的全部父节点(包含父节点的父节点)
     */
    public static List<TreeDataDO> getParentEleList(String pid, List<TreeDataDO> treeDataList) {
        List<TreeDataDO> returnDataList = new ArrayList<>();
        /**
         * Optional.ofNullable(xxx).orElse(new ArrayList<>())：如果集合为null则返回一个空集合
         * filter：返回条件成立的元素
         * forEach：遍历集合
         */
        Optional.ofNullable(treeDataList).orElse(new ArrayList<>())
                .stream()
                .filter(treeDataDO -> StrUtil.equals(treeDataDO.getId(), pid))
                .forEach(treeDataDO -> {
                    // 添加父节点
                    returnDataList.add(treeDataDO);
                    // 递归添加父节点上面的父节点
                    returnDataList.addAll(getParentEleList(treeDataDO.getPid(), treeDataList));
                });
        return returnDataList;
    }

    /**
     * 根据父节点ID向上递归检查是否存在死循环
     *
     * @param pId          ：当前检查节点的父节点ID
     * @param ids          ：当前节点ID以及父节点(包括父节点的父节点)的ID。
     *                     会自动修改其中的值，如 [id2, id3, id2]、[id3, id2, id3]、[id4, id2, id3, id2]：第三种情况不需要提示，前两个已经包含了它。
     * @param treeDataList ：全部单位内部结构数据
     * @param maxLoopCount ：最大递归次数，理论上递归方法自己是不会死循环的，但还是保险一点，也没有级次会超过10级的。
     * @return 存在死循环时返回 true。
     */
    private boolean isDeadCycle(String pId, List<String> ids, List<TreeDataDO> treeDataList, int maxLoopCount) {
        // System.out.println("----" + maxLoopCount);
        for (TreeDataDO treeDataDO : treeDataList) {
            String id = treeDataDO.getId();
            // System.out.println("--------" + pId +" ids=" + ids + " id=" + id);
            if (StrUtil.equals(id, pId)) {
                // 如果父节点的ID已经存在了，则说明配置处于死循环了，退出递归，此时开始和结束的元素值是一样的。
                if (ids.contains(id)) {
                    // 添加父节点
                    ids.add(id);
                    return true;
                }
                // 添加父节点
                ids.add(id);
                // 当父节点没有父节点时，退出递归。
                pId = treeDataDO.getPid();
                if (StrUtil.isBlank(pId) || StrUtil.equals("0", pId)) {
                    return false;
                }
                // 当递归次数达到上限时，退出循环.
                maxLoopCount--;
                if (maxLoopCount <= 0) {
                    return false;
                }
                // 递归获取父节点
                return isDeadCycle(pId, ids, treeDataList, maxLoopCount);
            }
        }
        return false;
    }

    /**
     * 获取树型结构数据，实际项目中来自数据库。
     *
     * @return
     * @throws IOException
     */
    private List<TreeDataDO> getTreeDataList() throws IOException {
        URL url = RecursionTreeTest.class.getClassLoader().getResource("data/recursionTreeData.json");
        File file = new File(url.getPath());
        ObjectMapper objectMapper = new ObjectMapper();
        List<TreeDataDO> treeDataDOList = objectMapper.readValue(file, new TypeReference<List<TreeDataDO>>() {
        });
        return treeDataDOList;
    }

    private List<TreeDataDO> getErrorTreeDataList() throws IOException {
        URL url = RecursionTreeTest.class.getClassLoader().getResource("data/recursionErrorTreeData.json");
        File file = new File(url.getPath());
        ObjectMapper objectMapper = new ObjectMapper();
        List<TreeDataDO> treeDataDOList = objectMapper.readValue(file, new TypeReference<List<TreeDataDO>>() {
        });
        return treeDataDOList;
    }

    @Test
    public void testGetChildNodes0() throws IOException {
        List<TreeDataDO> treeDataList = getTreeDataList();
        // List<TreeDataDO> childNodes = getChildNodes("0", treeDataList);
        List<TreeDataDO> childNodes = getChildEleList("0", treeDataList);
        // TreeDataDO{id='1', pid='0', name='父节点1 - 展开'}
        // TreeDataDO{id='11', pid='1', name='父节点11 - 折叠'}
        // TreeDataDO{id='111', pid='11', name='叶子节点111'}
        // TreeDataDO{id='112', pid='11', name='叶子节点112'}
        // TreeDataDO{id='113', pid='11', name='叶子节点113'}
        // TreeDataDO{id='114', pid='11', name='叶子节点114'}
        // TreeDataDO{id='12', pid='1', name='父节点12 - 折叠'}
        // TreeDataDO{id='121', pid='12', name='叶子节点121'}
        // TreeDataDO{id='122', pid='12', name='叶子节点122'}
        // TreeDataDO{id='123', pid='12', name='叶子节点123'}
        // TreeDataDO{id='124', pid='12', name='叶子节点124'}
        // TreeDataDO{id='1241', pid='124', name='叶子节点1241'}
        // TreeDataDO{id='13', pid='1', name='父节点13 - 没有子节点'}
        // TreeDataDO{id='2', pid='0', name='父节点2 - 折叠'}
        // TreeDataDO{id='21', pid='2', name='父节点21 - 展开'}
        // TreeDataDO{id='211', pid='21', name='叶子节点211'}
        // TreeDataDO{id='212', pid='21', name='叶子节点212'}
        // TreeDataDO{id='213', pid='21', name='叶子节点213'}
        // TreeDataDO{id='214', pid='21', name='叶子节点214'}
        // TreeDataDO{id='22', pid='2', name='父节点22 - 折叠'}
        // TreeDataDO{id='221', pid='22', name='叶子节点221'}
        // TreeDataDO{id='222', pid='22', name='叶子节点222'}
        // TreeDataDO{id='223', pid='22', name='叶子节点223'}
        // TreeDataDO{id='224', pid='22', name='叶子节点224'}
        // TreeDataDO{id='23', pid='2', name='父节点23 - 折叠'}
        // TreeDataDO{id='231', pid='23', name='叶子节点231'}
        // TreeDataDO{id='232', pid='23', name='叶子节点232'}
        // TreeDataDO{id='233', pid='23', name='叶子节点233'}
        // TreeDataDO{id='234', pid='23', name='叶子节点234'}
        // TreeDataDO{id='3', pid='0', name='父节点3 - 没有子节点'}
        childNodes.stream().forEach(item -> System.out.println(item));
    }

    @Test
    public void testGetChildNodes1() throws IOException {
        List<TreeDataDO> treeDataList = getTreeDataList();
        // List<TreeDataDO> childNodes = getChildNodes("1", treeDataList);
        List<TreeDataDO> childNodes = getChildEleList("1", treeDataList);
        // TreeDataDO{id='11', pid='1', name='父节点11 - 折叠'}
        // TreeDataDO{id='111', pid='11', name='叶子节点111'}
        // TreeDataDO{id='112', pid='11', name='叶子节点112'}
        // TreeDataDO{id='113', pid='11', name='叶子节点113'}
        // TreeDataDO{id='114', pid='11', name='叶子节点114'}
        // TreeDataDO{id='12', pid='1', name='父节点12 - 折叠'}
        // TreeDataDO{id='121', pid='12', name='叶子节点121'}
        // TreeDataDO{id='122', pid='12', name='叶子节点122'}
        // TreeDataDO{id='123', pid='12', name='叶子节点123'}
        // TreeDataDO{id='124', pid='12', name='叶子节点124'}
        // TreeDataDO{id='1241', pid='124', name='叶子节点1241'}
        // TreeDataDO{id='13', pid='1', name='父节点13 - 没有子节点'}
        childNodes.stream().forEach(item -> System.out.println(item));
    }

    @Test
    public void testGetChildNodes2() throws IOException {
        List<TreeDataDO> treeDataList = getTreeDataList();
        List<TreeDataDO> childNodes = getChildNodes("12", treeDataList);
        // List<TreeDataDO> childNodes = getChildEleList("12", treeDataList);
        // TreeDataDO{id='121', pid='12', name='叶子节点121'}
        // TreeDataDO{id='122', pid='12', name='叶子节点122'}
        // TreeDataDO{id='123', pid='12', name='叶子节点123'}
        // TreeDataDO{id='124', pid='12', name='叶子节点124'}
        // TreeDataDO{id='1241', pid='124', name='叶子节点1241'}
        childNodes.stream().forEach(item -> System.out.println(item));
    }

    @Test
    public void testGetChildNodes3() throws IOException {
        List<TreeDataDO> treeDataList = getTreeDataList();
        // []
        // List<TreeDataDO> childNodes = getChildNodes("13", treeDataList);
        // []
        List<TreeDataDO> childNodes = getChildEleList("13", treeDataList);
        childNodes.stream().forEach(item -> System.out.println(item));
    }

    @Test
    public void testGetParentNodes1() throws IOException {
        List<TreeDataDO> treeDataList = getTreeDataList();
        List<TreeDataDO> parentNodes = getParentNodes("124", treeDataList);
        // TreeDataDO{id='124', pid='12', name='叶子节点124'}
        // TreeDataDO{id='12', pid='1', name='父节点12 - 折叠'}
        // TreeDataDO{id='1', pid='0', name='父节点1 - 展开'}
        parentNodes.stream().forEach(item -> System.out.println(item));
        System.out.println("=====================");

        List<TreeDataDO> parentEleList = getParentEleList("124", treeDataList);
        // TreeDataDO{id='124', pid='12', name='叶子节点124'}
        // TreeDataDO{id='12', pid='1', name='父节点12 - 折叠'}
        // TreeDataDO{id='1', pid='0', name='父节点1 - 展开'}
        parentEleList.stream().forEach(item -> System.out.println(item));
    }

    /**
     * 检查整个树型结构是否存在死循环配置
     *
     * @throws IOException
     */
    @Test
    public void testIsDeadCycle() throws IOException {
        // 最大递归次数，理论上递归方法自己是不会死循环的，但还是保险一点，也没有级次会超过10级的。
        int maxLoopCount = 100;
        List<TreeDataDO> treeDataList = getErrorTreeDataList();
        List<List<String>> deadCycleIds = new ArrayList<>();
        for (TreeDataDO dataMap : treeDataList) {
            String parentId = dataMap.getPid();
            String id = dataMap.getId();
            if (StrUtil.isBlank(parentId) || StrUtil.equals("0", parentId)) {
                // 如果没有父节点，则不检查
                continue;
            }
            // System.out.println("id=" + id);
            List<String> ids = new ArrayList<>();
            ids.add(id);
            isDeadCycle(parentId, ids, treeDataList, maxLoopCount);
            if (ids.size() >= 2 && StrUtil.equals(ids.get(0), ids.get(ids.size() - 1))) {
                //  [id2, id3, id2]、[id3, id2, id3]、[id4, id2, id3, id2]：第三种情况不需要提示，前两个已经包含了它
                deadCycleIds.add(ids);
            }
        }
        System.out.println("以下节点存在死循环：\r");
        for (List<String> deadCycleIdList : deadCycleIds) {
            System.out.println("\t" + StrUtil.join("->", deadCycleIdList));
        }
        // 以下节点存在死循环：
        // 	113->213->113
        // 	12->22->123->12
        // 	123->12->22->123
        // 	213->113->213
        // 	22->123->12->22
    }

}

class TreeDataDO {
    // 节点ID
    private String id;
    // 父节点ID
    private String pid;
    // 节点名称
    private String name;

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public String getPid() {
        return pid;
    }

    public void setPid(String pid) {
        this.pid = pid;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeDataDO{" +
                "id='" + id + '\'' +
                ", pid='" + pid + '\'' +
                ", name='" + name + '\'' +
                '}';
    }
}