Java 中二叉树的层序遍历

二叉树的广度优先遍历也称为Java 中的二叉树层序遍历。

对于下面的二叉树

层序遍历顺序为：18 20 30 60 34 45 65 12 50 98 82 31 59 71 41

使用递归

可以使用递归进行二叉树的层序遍历。在递归方法中，我们需要处理左子树和右子树。伪代码更详细地展示了这一点。

递归方法的伪代码

实施

让我们使用上面定义的伪代码来实现二叉树的层序遍历。

文件名： BTreeLevelOrder.java

输出

Level order traversal of binary tree is 
18 20 30 60 34 45 65 12 50 98 82 31 59 71 41

时间复杂度：程序在最坏情况下的时间复杂度为 O(n^2)，其中 n 是二叉树的总节点数。请注意，最坏情况发生在树是倾斜的情况下。

空间复杂度：程序在最坏情况下的空间复杂度为 O(n)，其中 n 是二叉树的总节点数。请注意，最坏情况发生在树是倾斜的情况下。对于倾斜树，displayCurrentLevel() 方法使用 O(n) 的空间用于调用堆栈。在我们的例子中，树是平衡的；因此，使用的空间为 O(log(n))，这是平衡树的高度。

使用队列

也可以使用队列来完成二叉树的层序遍历。使用队列，我们首先将节点的所有子节点放入队列中。左子节点先入队，然后是右子节点。由于队列遵循先进先出 (FIFO) 原则，左子节点先出队，然后是右子节点，从而实现了树的层序遍历。为了更好地理解，让我们观察伪代码，然后是它的实现。

使用队列进行遍历的伪代码

实施

让我们使用上面定义的伪代码来实现二叉树的层序遍历。

文件名： BTreeLevelOrder1.java

输出

Level order traversal of binary tree is:
18 20 30 60 34 45 65 12 50 98 82 31 59 71 41

时间复杂度：程序的时间复杂度为 O(n)，其中 n 是二叉树的总节点数。

空间复杂度：程序使用的空间复杂度也为 O(n)，其中 n 是二叉树的总节点数。

两种方法的比较

通过比较两种方法的时空复杂度，我们发现使用队列可以更快地获得结果。此外，队列程序的时空复杂度不依赖于节点的排列。这意味着，即使树是倾斜的，程序的时间和空间复杂度也不会改变，而递归方法则无法做到这一点。在递归方法中，节点的排列对结果影响很大。