Java实现树形List与扁平List互转的示例代码

作者:HACKYLE 时间:2023-03-15 00:18:23 

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

  • 公司的组织架构的数据存储与展示

  • 文件夹层级的数据存储与展示

  • 评论系统中,父评论与诸多子评论的数据存储与展示

  • ......

对于这种有层级的结构化数据,就像是一棵一样。在关系型数据库中,通常将一个个的节点信息存储到表中,通过一个字段(例如,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;
   }
}

主要思想

依次遍历树形List,当前节点为Cur

  • 将Cur收集到某个存储结果的List

  • 如果Cur有子树,压入某个栈中

依次弹出栈元素,当前弹出的元素为StackSubTree

  • 如果StackSubTree还有子树,继续压栈

  • 如果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;
   }
}

来源:https://www.cnblogs.com/hackyle/p/structured-data-convert-of-tree-and-list.html#mcetoc_1gvv3d1t57vc

标签:Java,树形,扁平,List
0
投稿

猜你喜欢

  • 浅谈Android Studio 4.1 更新内容

    2021-09-17 11:27:30
  • Java基于注解的Excel导出方式

    2021-12-31 04:55:08
  • Android之在linux终端执行shell脚本直接打印当前运行app的日志的实现方法

    2021-06-12 23:41:08
  • java Spring的启动原理详解

    2022-09-02 04:39:59
  • Android实现读取NFC卡卡号示例

    2021-08-06 21:08:39
  • java8 集合 多字段 分组 统计个数代码

    2022-12-07 21:03:34
  • 详细聊聊C#的并发机制优秀在哪

    2023-03-04 15:41:18
  • Spring和SpringBoot之间的区别

    2022-09-28 11:47:38
  • Java基础高级综合练习题扑克牌的创建

    2023-09-08 06:56:19
  • 详解Java多态对象的类型转换与动态绑定

    2021-10-12 06:59:59
  • Kotlin Thread线程与UI更新详解

    2021-10-10 00:18:22
  • 线程池中使用spring aop事务增强

    2021-08-06 06:37:19
  • Springboot与Maven多环境配置的解决方案

    2023-11-29 08:53:58
  • @CacheEvict 清除多个key的实现方式

    2023-11-21 08:28:04
  • AQS同步组件Semaphore信号量案例剖析

    2023-11-27 14:27:04
  • C# 创建单例的多种方式

    2023-03-17 05:23:48
  • 详解Spring中的Environment外部化配置管理

    2023-11-23 05:24:24
  • 一文让你搞懂如何手写一个redis分布式锁

    2023-11-29 02:46:30
  • C#模拟实现QQ窗体功能

    2021-07-17 02:49:11
  • Android studio实现简单计算器的编写

    2022-08-21 05:58:55
  • asp之家 软件编程 m.aspxhome.com