剑指offer代码解析——面试题23从上往下打印二叉树

本题的详细分析过程均在代码注释中:

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 题目:从上到下打印二叉树的结点,同一层的结点按照从左到右的顺序打印。
 * @author 大闲人柴毛毛
 * @date 2016年3月15日
 */
public class PrintBinaryTree {
	/**
	 * 分析:学过数据结构便可知,本题实则为宽度优先遍历二叉树。
	 * 在数据结构中,深度优先遍历一棵二叉树有三种方式:先序遍历、中序遍历、后序遍历。他们均可采用递归,代码非常简洁。
	 * 而宽度优先遍历二叉树可采用迭代,并借助一个辅助的队列来存储尚未遍历的结点,下面是详细过程。
	 */
	
	/**
	 * 首先需要创建一个队列,用于存储尚未打印的结点。
	 * 首先让根结点入队,然后重复一下操作,直到对为空为止:
	 * 从队首取出一个结点,并打印该结点,若该结点有孩子,则按照先左后右的顺序将左右孩子入队。
	 * 重复上述操作,当队为空时,遍历结束。
	 */
	
	public static boolean printBinaryTree(BinaryTreeNode<Integer> root){
		//若树为空
		if(root==null){
			System.out.println("树为空!");
			return false;
		}
		
		//创建队列
		Queue<BinaryTreeNode<Integer>> queue = new LinkedBlockingQueue<BinaryTreeNode<Integer>>();
		//将根结点入队
		queue.add(root);
		//当队不为空时
		while(!queue.isEmpty()){
			//取出队首结点
			BinaryTreeNode<Integer> first_node = queue.poll();
			System.out.println(first_node.data);
			//若该结点有孩子,则按照先左后右的顺序将孩子入队
			if(first_node.left!=null)
				queue.add(first_node.left);
			if(first_node.right!=null)
				queue.add(first_node.right);
		}
		return true;
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		//构建二叉树
		BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node1 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node2 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node3 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node4 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> node5 = new BinaryTreeNode<Integer>();
		
		root.data = 1;
		node1.data = 2;
		node2.data = 3;
		node3.data = 4;
		node4.data = 5;
		node5.data = 6;
		
		root.left = node1;
		root.right = node2;
		
		node1.left = node3;
		node1.right = node4;

		node2.right = node5;
		
		printBinaryTree(root);
	}
}




/**
 * 二叉树的结点
 */
class BinaryTreeNode<T>{
	T data;//结点的数据域
	BinaryTreeNode<T> left;//左子树
	BinaryTreeNode<T> right;//右子树
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

二叉树转链表

给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外开辟存储空间) LeetCode 114. ...

502
来自专栏用户2442861的专栏

轻松搞定面试中的二叉树题目

版权所有,转载请注明出处,谢谢! http://blog.csdn.net/walkinginthewind/article/details/7518888...

1032
来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

34411
来自专栏猿人谷

二叉树的非递归遍历(递归和非递归)

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义,...

17410
来自专栏恰同学骚年

数据结构基础温故-4.树与二叉树(上)

前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形...

793
来自专栏拭心的安卓进阶之路

重温数据结构:二叉排序树的查找、插入、删除

我们知道,二分查找可以缩短查找的时间,但是有个要求就是 查找的数据必须是有序的。每次查找、操作时都要维护一个有序的数据集,于是有了二叉排序树这个概念。 上篇文章...

2426
来自专栏C/C++基础

二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

二叉树是一类简单而又重要的树形结构,在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构,简单的逻辑,广泛的应用和大量的指针操作,在面试过程屡见不鲜,快...

711
来自专栏desperate633

LintCode Binary Tree Maximum Node二叉树的最大节点分析代码

Find the maximum node in a binary tree, return the node.

652
来自专栏拭心的安卓进阶之路

重温数据结构:二叉树的常见方法及三种遍历方式 Java 实现

树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二叉树。 ? 什么是二叉树 Binary Tree 先来个定义: 二叉树是有限个节点的集合,这个集合...

2096
来自专栏Java 源码分析

二叉树

1.二叉树的性质 1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点 2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点 3.度...

2574

扫码关注云+社区