JAVA非递归生成无限级菜单树的较简代码实现。（非泛用型工具包，仅总结逻辑）

2023-06-13 09:46 由一蛋双簧（滑稽）发表于 #后端开发

这是一个根据列表生成一个树状结构的较简单实现。搜了搜看起来好像没多少人总结过这种实现。写上来整理一下自己的思路，请大家用用看看，应该用起来问题不大？反正我没遇到BUG。

实现的时间复杂度为O（N），空间复杂度应该还是O（N）吧。不过GPT说O（1）可能是因为java的对象实现hash链表是引用而不是新建一个新对象？

好的。首先表明这个方法实现的前提条件：

1：列表包含的实体类必须有id和pid（也就是父类ID）两个属性。另外。需要重写实体类子类列表的get方法。当列表为空时候new一个列表。（这个其实也是为了防止空指针，嫌弃麻烦的可以在下面的构造中加入判断空列表）

2其根节点必须是0或者某个特定的数字。（为空也行。但是你得在获取自己的父节点时判断pid是否为空，并且给他赋值一个永远无法用到的值。这个键值对应的节点子节点列表即为所需的菜单树）

这些都不太影响实现的时间复杂度。只是为了处理异常情况的解决办法。所以可以忽略。除了那个id和pid。不过讲真。一个树结构没这两个属性也挺离谱的。

废话少说。上代码。

首先生成无限级分类树的代码。列表实体类与所需实体类不同也不是大问题。

list<menuVo> nodeList = 获得list的方法();
Hashmap<menuVO> hashMap =new Hashmap<>()； 
 for(menuVO node : nodeList){
  //添加自身节点。如果已经有自身节点代表之前遍历过他的子类。把之前放入的子类拿出来赋给自己。再将自己放回表内。提供给后续子类使用。
            menuVO now = hashMap.get(node.getId());
                if(now!=null){
                   node.setChildren(now.getChildren());
             }
              //如果在这里过滤区分条件。无法确保节点存在。如果作为父类节点被子类创建。会存在一个没有赋值的节点存在。且在接下来的查找父类时会将无值对象存放入父类子列表中。
                hashMap.put(node.getId(),node);

                //寻找自己的父类节点。没有就代表父类结点未遍历、自己创一个先用着。等到遍历到父类节点时再由父类转换子类对象。
                menuVO parent = hashMap.getOrDefault(node.getPid(),new menuVO());

                //选择条件放在这里。判断是否需要加入node.
　　　　　　　　　if(选择判断语句){

　　　　　　　　　　　　parent.getChildren().add(node);//似乎这么塞也行，但是还得存放一下父类。因为如果hashmap里没有映射。父类塞完之后没有用,如果hashmap内存在父类。shikeyi直接影响父类对象。

                　　hashMap.put(node.getPid(),parent);
　　　　　　　　　　}
    }

该实现具体的逻辑就是遍历整个列表。在一个hashmap中一个结点只有两个身份。一个是特定节点的子节点。一个是它自身节点。只要将这两个身份实现。最后获得的根节点，其下属的子节点列表就是整个菜单树。不需要关心某个节点有多少子节点。只需要关心我是谁。需要放在hash表的哪里？我的父节点是谁。我需要把我放在他的子节点链表下。这样可以不需要对节点进行排序。也能实现构造逻辑树。如果有排序需求的话。。。最后的时候对其进行一下排序。不过这样的话时间复杂度就上去了。（这里可能需要优化一下？不过卖点就是不排序直接生成啊。）

以下是写的操作列表的工具类。这个确实是可以拿来用的。不说时间复杂度了。反正应该是最简了吧。除非再改一改数据结构

第一获取节点

 private menuVO getByCode(List<menuVO> list, String code) {

        for (int i = 0; i < list.size(); i++) {
            menuVO vo = list.get(i);
            if (code.equals(vo.getCode())) {//看他自己是不是这个节点
                return vo;
            }
            vo = vo.getChildren().size() > 0 ? getByCode(vo.getChildren(), code) : null;
            if (vo != null) {
                return vo;
            }
        }
        return null;
    }

第二，删除特定节点

private Boolean removeByCode(List<menuVO> list, String code) {

        for (int i = 0; i < list.size(); i++) {
            menuVO vo = list.get(i);
            if (code.equals(vo.getCode())) {
                list.remove(i);
                return true;
            }
            if (vo.getChildren().size() > 0 ? removeByCode(vo.getChildren(), code) : false) {//没子节点就不递归了，
                return true;
            }
        }
        return false;
    }

第三增加节点.那不是跟删除差不多？穿参不一样罢了。