当前关注："树形List"与"扁平List"互转（Java实现）

来源：博客园

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

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

id  name        pid1   总公司       -12   上海分公司    13   浙江分公司    14   闵行区分公司  25   嘉兴分公司    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":                    []                }            ]        }    ]}

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

(资料图)

内容导览

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

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;

应用场景

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

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 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 resultTree = list2Tree(this.cityEntities);        System.out.println(JSON.toJSONString(resultTree));    }    /**     * 双层for，List转Tree     * 主要思想：外层循环-找父节点；内层循环-找子节点；因为每个元素都会找一遍，所有最终得到完整的树     * 时间复杂度：N^2；空间复杂度：N     */    public List list2Tree(List cityEntities) {        List 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 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 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 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 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 subCityList;    getter/setter}

主要思想：

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 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> cityMapByPid = cityEntities.stream().collect(Collectors.groupingBy(CityEntity::getPid));        List resultCityList = new ArrayList<>();        for (CityEntity city : cityEntities) {            if(0 == city.getPid()) { //根节点、顶点                resultCityList.add(city);            }            List 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 resultCityList = new ArrayList<>();        //保存每个PID下的子节点        Map> cityMapByPid = new HashMap<>();        for (CityEntity city : cityEntities) { //收集每个PID下的子节点            //获取当前PID对应的子节点List，如果没有则创建一个空的List塞入            //这个设计得很巧妙            List 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));    }}

主要思想

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 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 resultCityList = new ArrayList<>();        Stack 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 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));    }}

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

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 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 resList = new ArrayList<>();        //这一层for的目的是：遍历根节点        for (CityEntity city : treeList) {            reversion(city,resList);        }        System.out.println(JSON.toJSONString(resList));    }    public void reversion(CityEntity curNode, List resList) {        resList.add(beanCopy(curNode));        List 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;    }}

主要思想

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 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 resList = new ArrayList<>();        Stack> 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 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;    }}

标签：