5

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

 1 year ago
source link: https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

"树形List"与"扁平List"互转（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":
                    []
                }
            ]
        }
    ]
}

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

内容导览

存储树的表结构

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

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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK