遍历分为深度优先和广度优先,对于二叉树的深度优先遍历我们已经讨论过了常规的递归遍历,迭代遍历和优化了空间复杂度的Morris遍历,这篇博客我们来讨论二叉树的广度优先遍历,也就是我们常说的层序遍历。
以下图中二叉树为例:
顾名思义二叉树的层序遍历是一层一层的顺序遍历的,上图的二叉树遍历顺序是: A B C D E F G H。
层序遍历大体的遍历方向是由浅到深,由左到右,也就是下图中箭头所示方向:
对于递归遍历和迭代遍历都是关于栈的应用,而层序遍历是关于队列的应用,代码层面的思路是,创建一个队列,根节点先入队列开始循环,每循环又一次,一个节点出队列对该节点进行相应操作,然后让该节点的左右孩子进队列(如果有的话),然后继续循环。
下面是代码实现:
public static void ergodic(TreeNode root){if(root == null){return;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);System.out.print("二叉树的层序遍历: ");while (!queue.isEmpty()){TreeNode remove = queue.remove();System.out.print((char)remove.val + " ");if (remove.left != null){queue.add(remove.left);}if (remove.right != null){queue.add(remove.right);}}}
用例子中的树测一下
public class Solution {public static TreeNode buildTree() {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;}public static void ergodic(TreeNode root){if(root == null){return;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);System.out.print("二叉树的层序遍历: ");while (!queue.isEmpty()){TreeNode remove = queue.remove();System.out.print((char)remove.val + " ");if (remove.left != null){queue.add(remove.left);}if (remove.right != null){queue.add(remove.right);}}}public static void main(String[] args) {TreeNode root = buildTree();ergodic(root);}
}
二叉树层次遍历图解、运行结果如下:
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态