二叉树的层次遍历

简介: 层次遍历就是即逐层地,从左到右访问所有节点

1、层次遍历

       层次遍历就是即逐层地,从左到右访问所有节点。如下

2、方法实现思路

      对于层序遍历,无疑是一层一层结点查找。那我们能不能找一个队列,把每一层的结点依次放入队列中,这样我们就能实现程序遍历啦。

       首先创建一个队列,然后把根节点放入队列中。

       接着就把 queue 的头结点弹出,也就是A,放到 cur中去,并打印。此时 cur 指向 A结点

cur 设置的目的:方便我们把下一层结点结点放到队列当中。

队列特点: 先进先出。

  我们判断 cur 的左结点是否为空,如果不为空就把左结点放入队列中。同时我们也要判断cur的右节点,操做相同。

每弹出一个结点,就会把该节点的左右孩子插入到队列中(左右孩子不为空的情况下!),然后弹出队列头结点。

       也就是一层一层遍历,比如遍历完B后,把B的左右孩子放到C的后面,直到遍历完C后(第二层)才会遍历B的左右孩子(第三层)。

总结:

定义一个队列,把root根节点放入队列中。      

弹出对头节点,并遍历打印。

判断当前节点的左右孩子是否为null,如果不为null,则入队。

检测队列,如果队列为空,则说明层序遍历结束。

层次遍历对于二叉树来说算是比较基础的一种算法,其拓展了许多。例如判断二叉树是否为满二叉树等。

       大家还可以去做 leetcode 做一下这道题加以巩固:二叉树的层序遍历

3、代码实现

import java.util.Queue;//导入队列的包
public class BinaryTree {
    //内部类
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用
        public TreeNode(char val) {
            this.val = val;
        }
    }
    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //层序遍历
    void levelOrder(TreeNode root) {
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        TreeNode root = bt.createTree();
        bt.levelOrder(root);
    }
}

代码中树的形状,和代码结果如下

69a302c2f93bee8fc07f6dd60292fb46_68cb7b2798c2400f9fa076e685994715.png

注:

Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

       在使用时我们要导入 import java.util.Queue ;

Queue中的方法:

1681233338ce2ce78e0300e496271d3a_493a7e8b42e94734b3caa2a8f5be56e7.png

相关文章
|
机器学习/深度学习 监控 数据库
人脸识别主要流程2
【1月更文挑战第5天】
|
6月前
|
IDE 编译器 开发工具
4轴运动控制源代码(STM32 + GRBL 1.1移植版)
4轴运动控制源代码(STM32 + GRBL 1.1移植版)
416 1
|
6月前
|
人工智能 自然语言处理 安全
阿里云上线团队版Token Plan:一站式多模型订阅,解决企业规模化AI使用难题
阿里云上线团队版Token Plan,内置Qwen3.6、Kimi-K2.6等十余款主流多模态模型,支持坐席灵活分配、成本管控与多租户隔离,兼容Qoder、Cursor等主流Agent工具,提供标准/高级/尊享三档套餐,一站式解决企业AI规模化使用痛点。
595 1
|
8月前
|
存储 人工智能 自然语言处理
一文搞懂!OpenClaw到底是什么?可以做什么?怎样去部署?
2026年初走红的开源AI智能体OpenClaw(昵称“小龙虾”),主打“用自然语言指挥电脑”,支持本地部署、系统级操作与跨应用自动化。具备文件管理、邮件处理、代码辅助、客服响应、风控预警等实用能力,兼顾隐私安全与低门槛部署,是个人与企业专属的私有化“数字员工”。
3236 2
|
7月前
|
缓存 人工智能 运维
企业级 LLM 成本治理:Claude Code 缓存机制与 API 架构优化实践
本文介绍企业级LLM成本治理实践:基于Claude前缀缓存机制,通过统一提示词模板、稳定模型配置与会话管理,实现84%缓存命中率、76%成本降低;并结合API网关架构优化,兼顾降本、合规、多模型兼容与运维效率。
1179 0
|
存储 负载均衡 容灾
海量数据如何“安家”?一文读懂哈希、范围和一致性哈希三大分片策略
将单机系统扩展为分布式架构时,数据分布是核心。哈希、范围及一致性哈希分片策略各有优劣:哈希均匀但扩缩容代价大;范围利于查询却易热点;一致性哈希平衡了动态伸缩与负载,广泛用于现代分布式系统。
1026 3
|
缓存 IDE 开发工具
Flutter Demo 的快速编译与运行
Flutter Demo 的快速编译与运行
799 15
|
机器学习/深度学习 SQL 数据采集
大数据行业权威认证盘点:这些证书让你的简历更受大厂青睐
这些认证不仅能够为求职者提供有力的能力证明,更能帮助HR快速识别符合岗位要求的技术人才。对于希望进入大数据领域的从业者来说,选择适合自身职业规划的认证,将大大提升职业竞争力。
|
关系型数据库 Serverless 定位技术
PostgreSQL GIS函数判断两条线有交点的函数是什么?
PostgreSQL GIS函数判断两条线有交点的函数是什么?
1250 60
|
机器学习/深度学习 人工智能 监控
业余AI与专业AI的区别,就在这些评估指标上
如何知道你训练的AI模型是天才还是学渣?本文用轻松幽默的方式带你了解机器学习的各类评估指标,让你不仅能说出模型的好坏,还能找到改进的方向,避免在实际应用中翻车。
881 8