“树形List“与“扁平List“互转（Java实现）

水深无声 2024-03-22 16:19 59阅读 0赞

**背景：**在平时的开发中，我们时常会遇到下列场景

1.  公司的**组织架构**的数据存储与展示
2.  文件夹**层级**的数据存储与展示
3.  评论系统中，**父评论与诸多子评论**的数据存储与展示
4.  ......

对于这种有层级的结构化数据，就像是一棵**树**一样。在关系型数据库中，通常将一个个的节点信息存储到表中，通过一个字段（例如，pid），指向其父节点。而在数据展示的时候，我们又希望它是呈现层级的，例如：

id  name        pid
    1   总公司       -1
    2   上海分公司    1
    3   浙江分公司    1
    4   闵行区分公司  2
    5   嘉兴分公司    3
    
    {
        "id": 1,
        "name": "总公司",
        "pid": -1,
        "branch":
        [
            {
                "id": 2,
                "name": "上海分公司",
                "pid": 1,
                "branch":
                [
                    {
                        "id": 4,
                        "name": "闵行区分公司",
                        "pid": 2,
                        "branch":
                        []
                    }
                ]
            },
            {
                "id": 3,
                "name": "浙江分公司",
                "pid": 1,
                "branch":
                [
                    {
                        "id": 5,
                        "name": "嘉兴分公司",
                        "pid": 3,
                        "branch":
                        []
                    }
                ]
            }
        ]
    }

所以，本文的主要内容就是提供几种方案，实现这两类数据的转换方式。

**内容导览**

*  [存储树的表结构][Link 1]
 *  [扁平List转树形List][List_List]
    
     *  [双层for][for]
     *  [递归][Link 2]
     *  [转换为Map][Map]
     *  [栈][Link 3]
 *  [树形List转扁平List][List_List 1]
    
     *  [递归][Link 4]
     *  [栈][Link 5]

--------------------

## 存储树的表结构 ##

如何在一张数据库表中表示一颗树结构中的所有节点信息，这里有一个示例：

DROP TABLE IF EXISTS zj_city;
    CREATE TABLE zj_city (
        id BIGINT NOT NULL AUTO_INCREMENT,
        name VARCHAR(50) COMMENT '节点名称',
        pid int NOT NULL COMMENT '父节点',
    
        create_time DATETIME DEFAULT now() COMMENT '创建时间: 年-月-日 时:分:秒',
        update_time DATETIME DEFAULT now() ON UPDATE now() COMMENT '更新时间',
        is_deleted BIT DEFAULT 0 COMMENT '是否删除：0-false-未删除;1-true-已删除',
        PRIMARY KEY (id)
    )COMMENT '浙江城市';
    
    INSERT INTO zj_city(name, pid) VALUES
    ('浙江省',0),
    ('金华市',1),
    ('嘉兴市',1),
    ('杭州市',1),
    ('宁波市',1);
    
    INSERT INTO zj_city(name, pid) VALUES
    ('下城区',4),
    ('钱塘区',4),
    ('西湖区',4),
    ('上城区',4);
    
    INSERT INTO zj_city(name, pid) VALUES
    ('南湖区',3),
    ('秀洲区',3),
    ('桐乡市',3),
    ('平湖市',3),
    ('海宁市',3);
    
    INSERT INTO zj_city(name, pid) VALUES
    ('梧桐街道',12),
    ('凤鸣街道',12),
    ('龙翔街道',12),
    ('崇福镇',12),
    ('乌镇镇',12),
    ('高桥镇',12),
    ('河山镇',12),
    ('濮院镇',12);
    
    SELECT * from zj_city;

## 扁平List转树形List ##

**应用场景**

*  公司组织结构
 *  省市级
 *  评论系统中，父评论与诸多子评论
 *  其他层级展示的数据

### 双层for ###

**主要思想：**外层循环-找父节点；内层循环-找子节点；因为每个元素都会找一遍，所有最终得到完整的树

import com.alibaba.fastjson.JSON;
    import com.ks.boot.entity.CityEntity;
    import org.junit.jupiter.api.BeforeEach;
    import org.junit.jupiter.api.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class TreeListDemo {
        List<CityEntity> cityEntities;
        /**
         * id  name  pid
         * 1   浙江   0
         * 2   杭州   1
         * 3   嘉兴   1
         * 4   南湖   3
         * 5   桐乡   3
         * 6   余杭   2
         * 7   西湖   2
         * 8   云南   0
         * 9   昆明   8
         * 10  昭通   8
         */
        @BeforeEach
        public void init() {
            cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                    "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                    "{\"id\":3,\"name\":\"嘉兴\",\"pid\":1},\n" +
                    "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                    "{\"id\":5,\"name\":\"桐乡\",\"pid\":3},\n" +
                    "{\"id\":6,\"name\":\"余杭\",\"pid\":2},\n" +
                    "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                    "{\"id\":8,\"name\":\"云南\",\"pid\":0},\n" +
                    "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                    "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
        }
    
        @Test
        public void testList2Tree() {
            List<CityEntity> resultTree = list2Tree(this.cityEntities);
            System.out.println(JSON.toJSONString(resultTree));
        }
    
        /**
         * 双层for，List转Tree
         * 主要思想：外层循环-找父节点；内层循环-找子节点；因为每个元素都会找一遍，所有最终得到完整的树
         * 时间复杂度：N^2；空间复杂度：N
         */
        public List<CityEntity> list2Tree(List<CityEntity> cityEntities) {
            List<CityEntity> resultCities = new ArrayList<>();
            for (CityEntity city : cityEntities) {
                if(0 == city.getPid()) { //根节点、顶级节点，直接放入最终返回结果的List
                    resultCities.add(city);
                }
                for (CityEntity curCity : cityEntities) { //根据当前city找它的子节点
                    if(city.getId().equals(curCity.getPid())) {
                        if(city.getSubCityList() == null) { //还没有任何子节点，new一个空的放进去
                            city.setSubCityList(new ArrayList<>());
                        }
                        city.getSubCityList().add(curCity);
                    }
                }
            }
    
            return resultCities;
        }
    }
    
    public class CityEntity {
        private Long id;
        private String name;
        private Long pid;
    
        private List<CityEntity> subCityList;
    
        getter/setter
    }

### 递归 ###

**主要思想**：获取所有根节点、顶级节点，再从List中查找根节点的子节点；

import com.alibaba.fastjson.JSON;
    import com.ks.boot.entity.CityEntity;
    import org.junit.jupiter.api.BeforeEach;
    import org.junit.jupiter.api.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class TreeListDemo {
        List<CityEntity> cityEntities;
        /**
         * id  name  pid
         * 1   浙江   0
         * 2   杭州   1
         * 3   嘉兴   1
         * 4   南湖   3
         * 5   桐乡   3
         * 6   余杭   2
         * 7   西湖   2
         * 8   云南   0
         * 9   昆明   8
         * 10  昭通   8
         */
        @BeforeEach
        public void init() {
            cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                    "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                    "{\"id\":3,\"name\":\"嘉兴\",\"pid\":1},\n" +
                    "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                    "{\"id\":5,\"name\":\"桐乡\",\"pid\":3},\n" +
                    "{\"id\":6,\"name\":\"余杭\",\"pid\":2},\n" +
                    "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                    "{\"id\":8,\"name\":\"云南\",\"pid\":0},\n" +
                    "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                    "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
        }
    
        /**
         * 递归，List转Tree
         * 主要思想：获取所有根节点、顶级节点，再从List中查找根节点的子节点；
         * 时间复杂度：N*(1+N)/2，O(N^2)，因为递归方法中，最好是List的第一元素就是要找的子节点，最坏是
         * List的最后一个元素是子节点
         */
        @Test
        public void testList2Tree() {
            List<CityEntity> resultCities = new ArrayList<>();
            for (CityEntity city : cityEntities) {
                if(0 == city.getPid()) { //获取所有根节点、顶级节点，再根据根节点进行递归
                    CityEntity topCity = findChild(cityEntities, city); //此时的topCity已经包含它的所有子节点
                    resultCities.add(topCity);
                }
            }
    
            System.out.println(JSON.toJSONString(resultCities));
        }
    
        /**
         *
         * @param cityEntities 在那个里面找
         * @param curCity 找谁的子节点
         * @return curCity的子节点
         */
        public CityEntity findChild(List<CityEntity> cityEntities, CityEntity curCity) {
            for (CityEntity city : cityEntities) {
                if(curCity.getId().equals(city.getPid())) {
                    if(null == curCity.getSubCityList()) {
                        curCity.setSubCityList(new ArrayList<>());
                    }
                    CityEntity subChild = findChild(cityEntities, city); //每次递归，都从头开始查找有没有city的子节点
                    curCity.getSubCityList().add(subChild);
                }
            }
            return curCity;
        }
    
    }
    
    public class CityEntity {
        private Long id;
        private String name;
        private Long pid;
    
        private List<CityEntity> subCityList;
    
        getter/setter
    }

### 转换为Map ###

**主要思想**：

*  在双层for的解法中，由于内层for也需要遍历以便List，造成时间复杂度上身为平方级
 *  如果内层for不需要遍历完整的List，而是事先预处理到Map中，寻找时直接从Map中获取，则时间复杂度降为LogN

import com.alibaba.fastjson2.JSON;
    import org.junit.jupiter.api.BeforeEach;
    import org.junit.jupiter.api.Test;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.stream.Collectors;
    
    public class TreeListDemo {
        List<CityEntity> cityEntities;
        /**
         * id  name  pid
         * 1   浙江   0
         * 2   杭州   1
         * 3   嘉兴   1
         * 4   南湖   3
         * 5   桐乡   3
         * 6   余杭   2
         * 7   西湖   2
         * 8   云南   0
         * 9   昆明   8
         * 10  昭通   8
         */
        @BeforeEach
        public void init() {
            cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                    "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                    "{\"id\":3,\"name\":\"嘉兴\",\"pid\":1},\n" +
                    "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                    "{\"id\":5,\"name\":\"桐乡\",\"pid\":3},\n" +
                    "{\"id\":6,\"name\":\"余杭\",\"pid\":2},\n" +
                    "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                    "{\"id\":8,\"name\":\"云南\",\"pid\":0},\n" +
                    "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                    "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
        }
    
        /**
         * 在双层for的解法中，由于内层for也需要遍历以便List，造成时间复杂度上身为平方级
         * 如果内层for不需要遍历完整的List，而是事先预处理到Map中，寻找时直接从Map中获取，则时间复杂度降为LogN
         */
        @Test
        public void list2tree() {
            //收集每个PID下的节点为Map
            Map<Long, List<CityEntity>> cityMapByPid = cityEntities.stream().collect(Collectors.groupingBy(CityEntity::getPid));
    
            List<CityEntity> resultCityList = new ArrayList<>();
            for (CityEntity city : cityEntities) {
                if(0 == city.getPid()) { //根节点、顶点
                    resultCityList.add(city);
                }
    
                List<CityEntity> citiesByPid = cityMapByPid.get(city.getId());
                if(null != citiesByPid && citiesByPid.size() > 0) { //有子节点
                    if(null == city.getSubCityList()) {
                        city.setSubCityList(new ArrayList<>());
                    }
                    city.getSubCityList().addAll(citiesByPid); //塞入
                }
            }
    
            System.out.println(JSON.toJSONString(resultCityList));
        }
    
        /**
         * 简化写法：在收集到Map时，对于没有子节点的节点，创建一个空的塞入到Map中
         */
        @Test
        public void list2tree4Simple() {
            List<CityEntity> resultCityList = new ArrayList<>();
    
            //保存每个PID下的子节点
            Map<Long, List<CityEntity>> cityMapByPid = new HashMap<>();
            for (CityEntity city : cityEntities) { //收集每个PID下的子节点
                //获取当前PID对应的子节点List，如果没有则创建一个空的List塞入
                //这个设计得很巧妙
                List<CityEntity> children = cityMapByPid.getOrDefault(city.getPid(), new ArrayList<>());
                children.add(city); //插入当前元素
                cityMapByPid.put(city.getPid(), children);
            }
    
            for (CityEntity city : cityEntities) {
                if(0 == city.getPid()) { //根节点、顶点
                    resultCityList.add(city);
                }
                city.setSubCityList(cityMapByPid.get(city.getId()));
            }
    
            System.out.println(JSON.toJSONString(resultCityList));
        }
    }

### 栈 ###

**主要思想**

*  收集根节点、顶级节点，存入resultList，并且压栈
 *  循环出栈，栈元素Cur
    
     *  找Cur的所有子元素为child
     *  如果child不为空，则再压入栈中。这一步的目的是，再一次找child的子元素

import com.alibaba.fastjson2.JSON;
    import org.junit.jupiter.api.BeforeEach;
    import org.junit.jupiter.api.Test;
    
    import java.util.*;
    import java.util.stream.Collectors;
    
    public class TreeListDemo {
        List<CityEntity> cityEntities;
        /**
         * id  name  pid
         * 1   浙江   0
         * 2   杭州   1
         * 3   嘉兴   1
         * 4   南湖   3
         * 5   桐乡   3
         * 6   余杭   2
         * 7   西湖   2
         * 8   云南   0
         * 9   昆明   8
         * 10  昭通   8
         */
        @BeforeEach
        public void init() {
            cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                    "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                    "{\"id\":3,\"name\":\"嘉兴\",\"pid\":1},\n" +
                    "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                    "{\"id\":5,\"name\":\"桐乡\",\"pid\":3},\n" +
                    "{\"id\":6,\"name\":\"余杭\",\"pid\":2},\n" +
                    "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                    "{\"id\":8,\"name\":\"云南\",\"pid\":0},\n" +
                    "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                    "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
        }
    
        /**
         * 主要思想：
         *  收集根节点、顶级节点，存入resultList，并且压栈
         *  循环出栈，栈元素Cur
         *      找Cur的所有子元素为child
         *      如果child不为空，则再压入栈中。这一步的目的是，再一次找child的子元素
         * 时间复杂度：N(过滤出所有跟节点) + 常数(出栈) * N(遍历List找当前节点的子元素)
         */
        @Test
        public void list2tree() {
            List<CityEntity> resultCityList = new ArrayList<>();
    
            Stack<CityEntity> stack = new Stack<>();
            resultCityList = cityEntities.stream().filter(ele -> 0 == ele.getPid()).collect(Collectors.toList());
            stack.addAll(resultCityList); //根节点、顶点入栈
    
            while(!stack.isEmpty()) {
                CityEntity curCity = stack.pop();
                List<CityEntity> child = cityEntities.stream().filter(ele -> curCity.getId().equals(ele.getPid())).collect(Collectors.toList());
                if(!child.isEmpty()) { //这一步处理的原因是：当没有子元素，不显示该个字段。流处理后没有元素只会返回空List，不会返回null
                    curCity.setSubCityList(child);
                }
                if(!child.isEmpty()) {
                    stack.addAll(child);
                }
            }
    
            System.out.println(JSON.toJSONString(resultCityList));
        }
    }

## 树形List转扁平List ##

### 递归 ###

**主要思想：**遍历树节点，一个树节点如果有子树，则再次递归此子树，直到没有子树为止

import com.alibaba.fastjson2.JSON;
    import org.junit.jupiter.api.BeforeEach;
    import org.junit.jupiter.api.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * id  name  pid
     * 1   浙江   0
     * 2   杭州   1
     * 3   嘉兴   1
     * 4   南湖   3
     * 5   桐乡   3
     * 6   余杭   2
     * 7   西湖   2
     * 8   云南   0
     * 9   昆明   8
     * 10  昭通   8
     */
    public class ListTreeDemo {
        List<CityEntity> treeList;
    
        @BeforeEach
        public void init() {
            treeList = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0,\"subCityList\":[" +
                    "{\"id\":2,\"name\":\"杭州\",\"pid\":1,\"subCityList\":[{\"id\":6,\"name\":\"余杭\",\"pid\":2},{\"id\":7,\"name\":\"西湖\",\"pid\":2}]}," +
                    "{\"id\":3,\"name\":\"嘉兴\",\"pid\":1,\"subCityList\":[{\"id\":4,\"name\":\"南湖\",\"pid\":3},{\"id\":5,\"name\":\"桐乡\",\"pid\":3}]}]}," +
                    "{\"id\":8,\"name\":\"云南\",\"pid\":0,\"subCityList\":[{\"id\":9,\"name\":\"昆明\",\"pid\":8},{\"id\":10,\"name\":\"昭通\",\"pid\":8}]}]", CityEntity.class);
        }
    
        @Test
        public void tree2list() {
            List<CityEntity> resList = new ArrayList<>();
    
            //这一层for的目的是：遍历根节点
            for (CityEntity city : treeList) {
                reversion(city,resList);
            }
            System.out.println(JSON.toJSONString(resList));
        }
        public void reversion(CityEntity curNode, List<CityEntity> resList) {
            resList.add(beanCopy(curNode));
    
            List<CityEntity> subCityList = curNode.getSubCityList();
            if(subCityList != null && !subCityList.isEmpty()) {
                for (CityEntity city : subCityList) { //递归寻找子节点的子节点们
                    reversion(city, resList);
                }
            }
            
            //递归的出口就是subCityList为null或者empty
        }
    
        private CityEntity beanCopy(CityEntity source) {
            CityEntity res = new CityEntity();
            res.setId(source.getId());
            res.setName(source.getName());
            res.setPid(source.getPid());
            return res;
        }
    }

### 栈 ###

**主要思想**

1.  依次遍历树形List，当前节点为Cur
    
    1.  将Cur收集到某个存储结果的List
    2.  如果Cur有子树，压入某个栈中
2.  依次弹出栈元素，当前弹出的元素为StackSubTree
    
    1.  如果StackSubTree还有子树，继续压栈
    2.  如果StackSubTree没有子树，则放入结果List

import com.alibaba.fastjson2.JSON;
    import org.junit.jupiter.api.BeforeEach;
    import org.junit.jupiter.api.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * id  name  pid
     * 1   浙江   0
     * 2   杭州   1
     * 3   嘉兴   1
     * 4   南湖   3
     * 5   桐乡   3
     * 6   余杭   2
     * 7   西湖   2
     * 8   云南   0
     * 9   昆明   8
     * 10  昭通   8
     */
    public class ListTreeDemo {
        List<CityEntity> treeList;
    
        @BeforeEach
        public void init() {
            treeList = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0,\"subCityList\":[" +
                    "{\"id\":2,\"name\":\"杭州\",\"pid\":1,\"subCityList\":[{\"id\":6,\"name\":\"余杭\",\"pid\":2},{\"id\":7,\"name\":\"西湖\",\"pid\":2}]}," +
                    "{\"id\":3,\"name\":\"嘉兴\",\"pid\":1,\"subCityList\":[{\"id\":4,\"name\":\"南湖\",\"pid\":3},{\"id\":5,\"name\":\"桐乡\",\"pid\":3}]}]}," +
                    "{\"id\":8,\"name\":\"云南\",\"pid\":0,\"subCityList\":[{\"id\":9,\"name\":\"昆明\",\"pid\":8},{\"id\":10,\"name\":\"昭通\",\"pid\":8}]}]", CityEntity.class);
        }
    
        /**
         * 1. 依次遍历树形List，当前节点为Cur
         *   a) 将Cur收集到某个存储结果的List
         *   b) 如果Cur有子树，压入某个栈中
         * 2. 依次弹出栈元素，当前弹出的元素为StackSubTree
         *   a) 如果StackSubTree还有子树，继续压栈
         *   b) 如果StackSubTree没有子树，则放入结果List
         */
        @Test
        public void tree2list() {
            List<CityEntity> resList = new ArrayList<>();
    
            Stack<List<CityEntity>> stack = new Stack<>();
    
            for (CityEntity curCity : treeList) {
                resList.add(beanCopy(curCity));
                if (curCity.getSubCityList() != null && !curCity.getSubCityList().isEmpty()) {
                    stack.push(curCity.getSubCityList());
                }
            }
    
            while (!stack.isEmpty()) {
                List<CityEntity> subTree = stack.pop();
                for (CityEntity city : subTree) {
                    if (city.getSubCityList() != null && !city.getSubCityList().isEmpty()) {
                        stack.push(city.getSubCityList());
                    } else {
                        resList.add(beanCopy(city));
                    }
                }
            }
    
            System.out.println(JSON.toJSONString(resList));
        }
    
        private CityEntity beanCopy(CityEntity source) {
            CityEntity res = new CityEntity();
            res.setId(source.getId());
            res.setName(source.getName());
            res.setPid(source.getPid());
            return res;
        }
    }

[Link 1]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vc
[List_List]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vd
[for]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57ve
[Link 2]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vf
[Map]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vg
[Link 3]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vh
[List_List 1]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vi
[Link 4]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vj
[Link 5]: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vk