一,问题描述
实现二叉树的层序遍历--从根开始,依次向下,对于每一层从左向右遍历。
二,算法分析
层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列,而先、中、后序需要用到栈。
因此,先、中、后序遍历 可以 采用递归方式来实现,而层序遍历则没有递归方式。
算法步骤:
初始时,根结点入队列
然后,while循环判断队列不空时,弹出一个结点,访问它,并把它的所有孩子结点入队列。
三,代码实现
1 public void levelTraverse(BinarySearchTreetree){ 2 levelTraverse(tree.root); 3 } 4 private void levelTraverse(BinaryNode root){ 5 if(root == null) 6 return; 7 8 Queue > queue = new LinkedList<>();//层序遍历时保存结点的队列 9 queue.offer(root);//初始化10 while(!queue.isEmpty()){11 BinaryNode node = queue.poll();12 System.out.print(node.element + " ");//访问节点13 if(node.left != null)14 queue.offer(node.left);15 if(node.right != null)16 queue.offer(node.right);17 }18 }
二叉搜索树的完整实现代码参考:
或者参考: