Java高效两次遍历加载出树状结构菜单(算法复杂度O(2n))

Myth丶恋晨 2022-10-13 05:22 2阅读 0赞

网上找了一堆，都是说递归，递归是可以，但是如果层数过多响应会很慢，我们可以利用Java的引用传递的**特性来两次遍历就加载出树状结构**，**引用传递是指：** A里面引B对象（B里面有个C属性，但是这时是空的），给B对象添加C属性，然后通过A调用B也能调用到添加的C属性，这种现象产生的原因是Java中对象引用引用的是地址值，地址指向的B存储的地方，所以B改变后A通过地址找到B也跟着改变，有兴趣的小伙伴可以下去自查。  
**话不多说，直接上代码：**

package com.example.demo.test;
    
    import java.util.Arrays;
    import java.util.List;
    import java.util.Objects;
    
    /** * @Author: Daisen.Z * @Date: 2021/7/6 15:02 * @Version: 1.0 * @Description: 演示用的菜单类 */
    public class MenuPojo { 
    
        private Integer id;
        private Integer partentId;
        private List<MenuPojo> childs;
    
        public MenuPojo(Integer id, Integer partentId) { 
            this.id = id;
            this.partentId = partentId;
        }
    
        public List<MenuPojo> getChilds() { 
            return childs;
        }
    
        public void setChilds(List<MenuPojo> childs) { 
            this.childs = childs;
        }
    
        public Integer getId() { 
            return id;
        }
    
        public void setId(Integer id) { 
            this.id = id;
        }
    
        public Integer getPartentId() { 
            return partentId;
        }
    
        public void setPartentId(Integer partentId) { 
            this.partentId = partentId;
        }
    
        @Override
        public String toString() { 
            return "MenuPojo{" +
                    "id=" + id +
                    ", partentId=" + partentId +
                    ", childs=" + (Objects.isNull(childs) ?  "" : Arrays.toString(childs.toArray()))+
                    '}';
        }
    }

加载树状结构的算法：

package com.example.demo.test;
    
    import cn.hutool.json.JSONUtil;
    
    import java.util.*;
    
    /** * @Author: Daisen.Z * @Date: 2021/7/6 15:03 * @Version: 1.0 * @Description: */
    public class TestCreateMenu { 
    
        public static void main(String[] args) { 
        // 模拟查询出的数据结果
            List<MenuPojo> menuPojos = new ArrayList<>();
            MenuPojo menuPojo = new MenuPojo(1, 0); // 两个一级菜单1，2
            MenuPojo menuPojo1 = new MenuPojo(2, 0);
            MenuPojo menuPojo2 = new MenuPojo(3, 1);
            MenuPojo menuPojo3 = new MenuPojo(4, 1);
            MenuPojo menuPojo6 = new MenuPojo(7, 1);
            MenuPojo menuPojo4 = new MenuPojo(5, 2);
            MenuPojo menuPojo5 = new MenuPojo(6, 3);
            menuPojos.add(menuPojo);
            menuPojos.add(menuPojo1);
            menuPojos.add(menuPojo2);
            menuPojos.add(menuPojo3);
            menuPojos.add(menuPojo4);
            menuPojos.add(menuPojo5);
            menuPojos.add(menuPojo6);
    
    
    // 真正加载树状结构的算法
            List<MenuPojo> menus = new ArrayList<>();
            Map<Integer,MenuPojo> menuIdAndObj = new HashMap<>();
            for (MenuPojo pojo : menuPojos) {  // 第一步先找出所有的一级菜单
                if (0 == pojo.getPartentId()){ 
                    menus.add(pojo);
                }
                // 这里需要将id与实体记录下来
                menuIdAndObj.put(pojo.getId(),pojo);
            }
    
            for (MenuPojo pojo : menuPojos) {   // 第二步遍历构建，每个菜单加入到自己的父菜单的子集中
                if (0 == pojo.getPartentId()){  // 如果是一级菜单，不需要找爸爸，直接跳过
                    continue;
                }
                // 每个子菜单找到自己的直接父菜单，并加入到父菜单的子菜单集合中
                MenuPojo parentMenu = menuIdAndObj.get(pojo.getPartentId());
                if (Objects.isNull(parentMenu.getChilds())){ // 如果还没有子菜单集合，新建一个集合并添加菜单到子菜单
                    parentMenu.setChilds(new ArrayList<>());
                }
                parentMenu.getChilds().add(pojo);
            }
    		// 这里打印是为了更直观一点，小伙伴通过debug也可以看到数据结构
            System.out.println(JSONUtil.toJsonStr(menus));
        }
    
    }

打印出的结果：

[
        { 
            "partentId":0,
            "childs":[
                { 
                    "partentId":1,
                    "childs":[
                        { 
                            "partentId":3,
                            "id":6
                        }
                    ],
                    "id":3
                },
                { 
                    "partentId":1,
                    "id":4
                },
                { 
                    "partentId":1,
                    "id":7
                }
            ],
            "id":1
        },
        { 
            "partentId":0,
            "childs":[
                { 
                    "partentId":2,
                    "id":5
                }
            ],
            "id":2
        }
    ]

# *不要崇拜哥，哥只是个传说* #

## 记得一键三连哦！ ##