二叉树层序遍历

傷城~ 2022-10-29 01:46 163阅读 0赞

# 二叉树的层序遍历 #

# 简介 #

在数据结构的学习过程中，最为重要的便是遍历了，在之前的文章中，已经阐述过了一些内容，主要是如下所示：

[原创 数据结构-树与深度优先遍历][_-]

[原创 二叉树之使用栈实现深度优先遍历][Link 1]

除了深度优先遍历之外，对于树结构还有一种层序遍历的方式是需要掌握的。

> 深度优先遍历是在一个方向上一头扎到底，而广度优先遍历则是在各个方向上各自走出一步。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1][]

这样的需求应该怎么实现，借助什么样的数据结构？我们都知道要使用队列，为什么栈不行呢？这些问题只有仔细思考才可以。

我们知道，要实现按层次遍历一棵二叉树，首先访问根，这个自然，因为函数会传递二叉树的根进入，然后通过根我们可以访问找到这个根节点的左右子树。即左右子节点。比如说我们此刻访问了节点B，那么怎么才能访问节点C呢？要么我们保存节点C的父亲节点，要么我们直接保存A节点。在通过栈实现深度优先遍历时，我们选择了保存节点的父节点。但在层序遍历的需求下，我们在处理同一层节点，要按照左右的顺序。B节点的孩子和C节点的孩子，B位于C的左边，因此先访问B，再访问C，同样的，也要先访问B的孩子，然后访问C的孩子。这恰恰符合FIFO的特点。因此，我们要通过一个队列来实现层序访问的功能。

# 代码实现 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2][]

## 不打印null ##

/** * 层序遍历二叉树根节点 * * @param root 二叉树根节点 */
        public static void levelOrderTraverse(Node root) { 
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                Node node = queue.poll();
                System.out.print(node.getData() + " ");
                if (node.getLeft() != null) { 
                    queue.add(node.getLeft());
                }
                if (node.getRight() != null) { 
                    queue.add(node.getRight());
                }
            }
    
        }

这样的输出结果如下所示：

List<Integer> source = Arrays.asList(3, 2, 9, null, null, 10, null, null, 8, null, 4);
            LinkedList<Integer> inputList = new LinkedList<Integer>(source);
            Node root = BinaryTree.createBinaryTree(inputList);

使用先根序列创建二叉树。参考[原创 数据结构-树与深度优先遍历][_-]

System.out.println();
            System.out.println("使用队列获取二叉树层序遍历");
            levelOrderTraverse(root);

得到的额结果如下所示：

使用队列获取二叉树层序遍历
    3 2 8 9 10 4

但这样把叶子节点的null没有打印。

## 打印null ##

打印null的理解，也比较简单，只是把null值也加入队列，统一在出队时进行对值的处理。较为简单，不再赘述。

/** * 层序遍历二叉树根节点 * * @param root 二叉树根节点 */
        public static void levelOrderTraverse(Node root) { 
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                Node node = queue.poll();
                if (node == null ) { 
                    System.out.print("null ");
                    continue;
                }
                System.out.print(node.getData() + " ");
                queue.add(node.getLeft());
                queue.add(node.getRight());
    
            }
    
        }

此时若运行，则结果如下：

3 2 8 9 10 null 4 null null null null null null

# 下载 #

[二叉树层序遍历][Link 2]

# 总结 #

关于二叉树的层序遍历，基本的内容就是这些，在工作中，应刻意练习使用这些二叉树啊、队列、栈这种结构来完成我们的工作需求，同时也加深对于这些小工具的使用。使用的越多，越熟练。这样也越好。

最近笔者在工作之余，一直在阅读张磊的《**价值**》一书，这是一本大神在20年疫情期间写的关于投资理念的书，书里面讲述了张磊的人生经历，创建高瓴资本的始末，尤其是磊哥提到的在长期主义之路上，与伟大格局观者同行，做时间的朋友，这些观念都让笔者的视野有了一些变化。\*\*真正的投资，有且只有一条标准，那就是是否在创造真正的价值，这个价值是否有益于社会的整体繁荣。\*\*真希望自己的经历能够更加丰富一点，看问题的视野和角度更开阔一些，人也更加的开放。感谢这个精彩的世界。也希望在阅读这篇博客的诸位，都能永远追求丰富而有益的人生。

[_-]: https://blog.csdn.net/lk142500/article/details/111776076
[Link 1]: https://blog.csdn.net/lk142500/article/details/113738044
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70]: /images/20221024/d98b8cc1a6404dc692598ec0952ca3a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1]: /images/20221024/f73327d4cc444761a41091cd7d41d72b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2]: /images/20221024/cfa8f42260264e4eadabafeca3be78cf.png
[Link 2]: https://download.csdn.net/download/lk142500/15118731