非递归实现树形下拉菜单

默语

发布于 2024-11-25 15:00:09

10200

代码可运行

文章被收录于专栏：JAVAJAVA

运行总次数：0

代码可运行

非递归实现树形下拉菜单

博主默语带您 Go to New World. ✍ 个人主页—— 默语的博客👦🏻 优秀内容 《java 面试题大全》 《java 专栏》 《idea技术专区》 《spring boot 技术专区》 《MyBatis从入门到精通》 《23种设计模式》 《经典算法学习》 《spring 学习》 《MYSQL从入门到精通》数据库是开发者必会基础之一~ 🍩惟余辈才疏学浅，临摹之作或有不妥之处，还请读者海涵指正。☕🍭 🪁 吾期望此文有资助于尔，即使粗浅难及深广，亦备添少许微薄之助。苟未尽善尽美，敬请批评指正，以资改进。！💻⌨

默语是谁？

大家好，我是默语，别名默语博主，擅长的技术领域包括Java、运维和人工智能。我的技术背景扎实，涵盖了从后端开发到前端框架的各个方面，特别是在Java 性能优化、多线程编程、算法优化等领域有深厚造诣。

目前，我活跃在CSDN、掘金、阿里云和 51CTO等平台，全网拥有超过10万的粉丝，总阅读量超过1400 万。统一 IP 名称为默语或者默语博主。我是 CSDN 博客专家、阿里云专家博主和掘金博客专家，曾获博客专家、优秀社区主理人等多项荣誉，并在 2023 年度博客之星评选中名列前 50。我还是 Java 高级工程师、自媒体博主，北京城市开发者社区的主理人，拥有丰富的项目开发经验和产品设计能力。希望通过我的分享，帮助大家更好地了解和使用各类技术产品，在不断的学习过程中，可以帮助到更多的人，结交更多的朋友.

我的博客内容涵盖广泛，主要分享技术教程、Bug解决方案、开发工具使用、前沿科技资讯、产品评测与使用体验。我特别关注云服务产品评测、AI 产品对比、开发板性能测试以及技术报告，同时也会提供产品优缺点分析、横向对比，并分享技术沙龙与行业大会的参会体验。我的目标是为读者提供有深度、有实用价值的技术洞察与分析。

好的，我会更详细地讲解 非递归实现树形下拉菜单 的完整思路和代码，同时为每一部分都加上清晰的注释，让初学者也能看懂。这次我们会以逐步实现的方式讲解每一步的逻辑。

非递归实现树形下拉菜单

什么是非递归实现？

在递归中，函数会自己调用自己。非递归实现是用 队列（Queue） 或 栈（Stack） 来替代函数调用栈，从而手动管理需要处理的数据，逐步完成任务。

目标

构造一个树形结构，比如：

一级分类A
└── 二级分类A1
    └── 三级分类A1-1
一级分类B
└── 二级分类B1

我们希望用非递归方法，将 parentId 表示层级关系的分类数据构建成上面的树状结构。

实现步骤（以队列方式为例）

1. 准备数据

首先，我们有一组表示分类层次的数据，例如：

List<Category> categories = new ArrayList<>();
categories.add(new Category(1L, "一级分类A", 0L));
categories.add(new Category(2L, "二级分类A1", 1L));
categories.add(new Category(3L, "三级分类A1-1", 2L));
categories.add(new Category(4L, "一级分类B", 0L));
categories.add(new Category(5L, "二级分类B1", 4L));

每个分类有一个 id（唯一标识）、一个 parentId（父节点ID）和 name（分类名称）。
parentId = 0 的分类是根节点。

我们需要将这些分类转化为树形结构。

2. Category 类定义

构造一个实体类 Category，包含以下属性：

public class Category {
    private Long id;          // 分类的唯一标识
    private String name;      // 分类的名称
    private Long parentId;    // 父分类的ID
    private List<Category> children; // 子分类列表

    // 构造方法
    public Category(Long id, String name, Long parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
        this.children = new ArrayList<>();
    }

    // Getters 和 Setters 方法（省略）

    @Override
    public String toString() {
        return "Category{" +
               "id=" + id +
               ", name='" + name + '\'' +
               ", parentId=" + parentId +
               ", children=" + children +
               '}';
    }
}

3. 非递归构建树

用队列来管理所有未处理的节点：

初始化队列，将所有的根节点（parentId = 0）加入到队列中。
从队列中取出一个节点，检查其 id 是否与其他节点的 parentId 相等。
- 如果相等，则将这些节点作为当前节点的子节点。
- 同时，将这些子节点也加入到队列中，等待进一步处理。
当队列为空时，树形结构已完成。

完整代码（队列实现）

import java.util.*;

public class CategoryTreeBuilder {

    /**
     * 构建树形结构（非递归方式，使用队列实现）
     *
     * @param categories 所有分类数据
     * @return 树形分类数据
     */
    public List<Category> buildTree(List<Category> categories) {
        // 创建一个 Map，用于快速查找节点
        Map<Long, Category> categoryMap = new HashMap<>();

        // 用于存储最终的根节点集合
        List<Category> result = new ArrayList<>();

        // 初始化：将所有分类放入Map中，并找出根节点
        for (Category category : categories) {
            category.setChildren(new ArrayList<>()); // 初始化子节点列表
            categoryMap.put(category.getId(), category); // 按ID存储到Map
            if (category.getParentId() == 0L) {
                result.add(category); // 根节点加入结果集
            }
        }

        // 用队列管理所有根节点
        Queue<Category> queue = new LinkedList<>(result);

        // 处理队列中的每个节点
        while (!queue.isEmpty()) {
            // 从队列中取出当前节点
            Category current = queue.poll();

            // 遍历所有分类，找到当前节点的子节点
            for (Category category : categories) {
                if (category.getParentId().equals(current.getId())) {
                    current.getChildren().add(category); // 添加为子节点
                    queue.add(category); // 将子节点加入队列
                }
            }
        }

        return result; // 返回树形结构
    }

    public static void main(String[] args) {
        // 示例数据
        List<Category> categories = new ArrayList<>();
        categories.add(new Category(1L, "一级分类A", 0L));
        categories.add(new Category(2L, "二级分类A1", 1L));
        categories.add(new Category(3L, "三级分类A1-1", 2L));
        categories.add(new Category(4L, "一级分类B", 0L));
        categories.add(new Category(5L, "二级分类B1", 4L));

        // 构建树形结构
        CategoryTreeBuilder builder = new CategoryTreeBuilder();
        List<Category> tree = builder.buildTree(categories);

        // 打印结果
        System.out.println(tree);
    }
}

输出结果

运行程序后，输出如下树形结构：

Category{id=1, name='一级分类A', parentId=0, children=[
    Category{id=2, name='二级分类A1', parentId=1, children=[
        Category{id=3, name='三级分类A1-1', parentId=2, children=[]}
    ]}
]}
Category{id=4, name='一级分类B', parentId=0, children=[
    Category{id=5, name='二级分类B1', parentId=4, children=[]}
]}