服务器之家：专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - "树形List"与"扁平List"互转（Java实现）

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

2023-05-12 01:06未知服务器之家 Java教程

形如公司的组织架构这种数据需要使用“树”这种数据结构来表示和存储。在纯数据表示的时候，我们使用缩进来指明树的层级关系；在存储的时候，我们通常将一个个的树节点信息存储于关系型数据中。那么如何在这两种数据方

形如公司的组织架构这种数据需要使用“树”这种数据结构来表示和存储。在纯数据表示的时候，我们使用缩进来指明树的层级关系；在存储的时候，我们通常将一个个的树节点信息存储于关系型数据中。那么如何在这两种数据方式之间转换呢？本文将提供一些思路来解决这个问题。

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

  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":
                    []
                }
            ]
        }
    ]
}

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

内容导览

  • 存储树的表结构
  • 扁平List转树形List
    • 双层for
    • 递归
    • 转换为Map
    • 栈
  • 树形List转扁平List
    • 递归
    • 栈

存储树的表结构

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

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;
    }
}

 

延伸 · 阅读

精彩推荐
最近更新
编辑推荐
阅读排行
热门标签
501 　 406 　 415 　 1433 　 2000 　 401 　 330 　 GOF23 　 new 　 newInstance 　 Hibernate 　 volatile 　 集合 　 spring 　 consul 　 critical 　 嵌套循环 　 注册服务 　 堆栈类 　 supplyAsync 　 遍历 　 设计模式 　 观察者模式 　 小数 　 JAVA8 　 写入文件 　 回车 　 制表符 　 排列组合 　 Java 　
© 2019-2023 服务器之家(www.zzvips.com) 版权所有关于我们联系我们版权申明网站地图