目录
对于这种有层级的结构化数据,就像是一棵树一样。在关系型数据库中,通常将一个个的节点信息存储到表中,通过一个字段(例如,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; } }
做猪小侠源码的代理,提供一站式服务
如果你不懂得搭建网站或者服务器,小程序,源码之类的怎么办? 第一通过本站学习各种互联网的技术 第二就是联系客服,我帮帮你搭建(当然要收取部分的费用) 第三成为我们的代理,我们提供整套的服务。