建设一个电商网站的流程图,网站a记录的是做cname,类似WordPress的Python,桓台县旅游网站建设环境
我们有个需求#xff0c;数据库要存一个无限级联的tree#xff0c;比如菜单#xff0c;目录#xff0c;或者地区等数据#xff0c;现有两个问题#xff1a;
问如何设计表。怎么返回给前端一个无线级联的json数据。
思考
第一个问题
在设计表的时候#xff0c;…环境
我们有个需求数据库要存一个无限级联的tree比如菜单目录或者地区等数据现有两个问题
问如何设计表。怎么返回给前端一个无线级联的json数据。
思考
第一个问题
在设计表的时候我们保证每一条数据都有一个code和parent表示code即可就可以连成树tree。表设计如下
CREATE TABLE city_info (code varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT 行政区划代码,name varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT 名称,type char(1) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT 类型:1-省;2-市;3-县/区,short_name varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT 简称,parent varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT 所属行政区划,parents varchar(200) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT 所属行政区划分级
) ENGINE InnoDB CHARACTER SET utf8 COLLATE utf8_general_ci COMMENT 中国省市区县行政区域表 ROW_FORMAT Dynamic;
第二个问题
我的想法是通过一个sql查询查出来所有数据得到一个 list集合然后就回到了主题如何用java把list转tree。
准备环境
创建一个城市信息类
/*** 中国省市区县行政区域表* TableName tbl_city_info*/
TableName(value tbl_city_info)
Data
public class CityInfo implements Serializable {/*** 主键id*/TableId(value id, type IdType.AUTO)private Long id;/*** 行政区划代码*/TableField(value code)private String code;/*** 名称*/TableField(value name)private String name;/*** 类型:1-省;2-市;3-县/区*/TableField(value type)private String type;/*** 简称*/TableField(value short_name)private String shortName;/*** 所属行政区划*/TableField(value parent)private String parent;/*** 所属行政区划分级*/TableField(value parents)private String parents;/*** 所属行政区划分级* Mybatis-plus 映射字段时忽略字段*/TableField(exist false)private ListCityInfo childCityInfo;TableField(exist false)private static final long serialVersionUID 1L;
}创建一个list转成tree的工具类
public class TreeUtils{public static ListCityInfo buildTree1(ListCityInfo cityInfos) {// TODO : 第一种解法return null;}public static ListCityInfo buildTree2(ListCityInfo cityInfos) {// TODO : 第二种解法return null;}public static ListCityInfo buildTree3(ListCityInfo cityInfos) {// TODO : 第三种解法return null;}
}第一种方法递归
/*** 使用递归的方式* param cityInfos 所有的数据* return*/public ListCityInfo buildTree1(ListCityInfo cityInfos) {ListCityInfo cityInfoList new ArrayList(16);for (CityInfo cityInfo : cityInfos) {//找到根集合if (cityInfo.getParent().equals(0)) {cityInfoList.add(cityInfo);//添加子setChildren(cityInfos,cityInfo);}}return cityInfoList;}/*** 在所有集合数据中找到所有的子结果* param cityInfos 所以的数据* param parent 需要找的这个城市的所有的子数据*/public void setChildren(ListCityInfo cityInfos, CityInfo parent) {for (CityInfo cityInfo : cityInfos) {ListCityInfo childCityInfo parent.getChildCityInfo();//如果数据和要找的数据code和parent相等说明找到了if (cityInfo.getParent().equals(parent.getCode())) {//如果是第一次子结果是null需要赋值一个空数组if (CollectionUtils.isEmpty(childCityInfo)) {childCityInfo new ArrayList(16);}childCityInfo.add(cityInfo);parent.setChildCityInfo(childCityInfo);}}//如果上面遍历完了而且子数据还是空说明没有子数据直接返回if (CollectionUtils.isEmpty(parent.getChildCityInfo())) {return;}//如果有子数据需要找子数据是否有子数据就是找儿子的儿子一直递归下去就行了for (CityInfo cityInfo : parent.getChildCityInfo()) {setChildren(cityInfos,cityInfo);}}第二种方法两层循环 /*** 第二种方法两层循环* 第一层遍历是为找所有的根节点* 第二层遍历是为了找所有节点的子节点* * 这里只是返回所有的根节点因为所有的节点的子节点都找到了所以只要返回根节点子节点自己就带上了* param cityInfos 所有的数据* return*/public ListCityInfo buildTree2(ListCityInfo cityInfos) {ListCityInfo cityInfoList new ArrayList(16);for (CityInfo cityInfo : cityInfos) {//找到根集合if (cityInfo.getParent().equals(0)) {cityInfoList.add(cityInfo);}//找到本次遍历的节点的所有子节点这里子节点就是一层for (CityInfo child : cityInfos) {if (cityInfo.getCode().equals(child.getParent())) {ListCityInfo childCityInfo cityInfo.getChildCityInfo();if (CollectionUtils.isEmpty(childCityInfo)) {childCityInfo new ArrayList(16);cityInfo.setChildCityInfo(childCityInfo);}childCityInfo.add(child);}}}return cityInfoList;}
第三种方法两次遍历
/*** 第三种方法两层循环* 第一层遍历是为了找到所有父code下面的所有的子节点* 第二层遍历是为了给所有的节点设置子节点并且找到所有根节点* param cityInfos 所有的数据* return*/public ListCityInfo buildTree3(ListCityInfo cityInfos) {MapString, ListCityInfo cityInfoParentMap new HashMap(16);//本次循环是为了找到所有父code下面的所有的子节点for (CityInfo cityInfo : cityInfos) {String parent cityInfo.getParent();ListCityInfo children cityInfoParentMap.getOrDefault(parent, new ArrayList());children.add(cityInfo);cityInfoParentMap.put(parent, children);}ListCityInfo result new ArrayList(16);//在次循环是为了给所有的节点设置子节点
// for (CityInfo cityInfo : cityInfos) {
// cityInfo.setChildCityInfo(cityInfoParentMap.get(cityInfo.getCode()));
// }
// //最好一次循环是为了找到所有的根节点
// for (CityInfo cityInfo : cityInfos) {
// if (cityInfo.getParent().equals(0)) {
// result.add(cityInfo);
// }
// }//第二次和第三次可以合成一次循环for (CityInfo cityInfo : cityInfos) {cityInfo.setChildCityInfo(cityInfoParentMap.get(cityInfo.getCode()));if (cityInfo.getParent().equals(0)) {result.add(cityInfo);}}return result;}第三种方法两次遍历使用Java8stream流 /*** 第三种方法两层循环* 第一层遍历是为了找到所有父code下面的所有的子节点* 第二层遍历是为了给所有的节点设置子节点并且找到所有根节点* param cityInfos 所有的数据* return*/public ListCityInfo buildTree3_stream(ListCityInfo cityInfos) {//本次循环是为了找到所有父code下面的所有的子节点MapString, ListCityInfo cityInfoParenMap cityInfos.stream().collect(Collectors.groupingBy(CityInfo::getParent));//本次循环是为了给所有的节点设置子节点cityInfos.forEach(cityInfo - cityInfo.setChildCityInfo(cityInfoParenMap.get(cityInfo.getCode())));//是为了找到所有的根节点return cityInfos.stream().filter(cityInfo - cityInfo.getParent().equals(0)).collect(Collectors.toList());}注意Collectors.groupingBy()方法使用。查看此链接https://blog.csdn.net/qq_2662385590/article/details/132385605?spm1001.2014.3001.5502
三种方法对比
前两种方法的时间复杂度都和叶子节点的个数相关我们假设叶子节点个数为m
方法一: 用递归的方法时间复杂度等于O(n n-m* n)根据初始算法那篇文章的计算时间复杂度的方法可以得到最终时间复杂度是O(n2)方法二: 用两层嵌套循环的方法时间复杂度等于O(n n-m* n)和方法一的时间复杂度是一样的最终时间复杂度是O(n2)方法三:用两次遍历的方法时间复杂度等于O(3n)根据初始算法那篇文章的计算时间复杂度的方法可以得到最终时间复杂度是O(n)但它的空间复杂度比前两种方法稍微大了一点但是也是线性阶的所以影响不是特别大。所以第三种方法是个人觉得比较优的一种方法
方法代码执行次数时间复杂度代码复杂程度方法1O(n n-m* n)平方阶,O(n2)一般方法2O(n n-m* n)平方阶,O(n2)良好方法3O(3n)线性阶,O(n)复杂
