
二叉树的遍历是面试经常会被考察的知识点,有些甚至要求当场手写实现过程。
遍历方式常见的分为两大类共四种:
广度优先遍历
- 层序遍历
深度优先遍历
前序遍历(先序遍历)
中序遍历
后序遍历
数据结构
在开始遍历之前,我们需要先构建一棵树,这里用 JSON 方式定义一棵树,然后用 FastJson 读取到 Java 的数据结构中:
1 | { |
Java 类:
1 |
|
初始化构建树:
1 | /** 初始化构建树 */ |
层序遍历
层序遍历是比较接近人的思维方式的一种遍历方法,将二叉树的每一层分别遍历,直到最后的叶子节点被全部遍历完。
为了简化遍历过程,我们需要引入队列(Queue),队列的特性是:先进先出,从队头出列,从队尾入列。Java 中 LinkedList 就是一种 Queue。
思路(递归方式):先出列一个节点,输出该节点,并判断该节点下有误左右子树,如果有的话,把左右子树入列,然后递归执行,直到队列为空。
代码实现
1 | public void testLevelOrder() { |
前序遍历,中序遍历,后序遍历
这三种深度优先的遍历方式用递归很方便实现。它们的区别只是对根和左右子树的遍历先后顺序不同而已。
前序遍历(NLR):先访问根节点,再访问左子树,最后访问右子树。
中序遍历(LNR):先左子树,再根节点,最后右子树。
后序遍历(LRN):先左子树,再右子树,最后根节点。
代码实现
1 | public void test() { |