剑指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 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

第4章 类与面向对象编程第4章 类与面向对象编程

在前面的章节中,我们学习了Kotlin的语言基础知识、类型系统等相关的知识。在本章节以及下一章中,我们将一起来学习Kotlin对面向对象编程以及函数式编程的支持...

682
来自专栏有趣的Python

慕课网-C++远征之多态篇(下)-学习笔记

RTTI(运行时类型识别) Run-Time Type Identification typeid < - > dynamic_cast 例子: class F...

3274
来自专栏程序员互动联盟

【专业技术】hash_map使用(二)

上次说完了简单类型的hash_map使用,现在说说用户自定义类型:比如对象类型,结构体的hash_map使用。 这种情况比价复杂,我们先...

26911
来自专栏数据结构与算法

BZOJ1008: [HNOI2008]越狱(组合数)

监狱有连续编号为 1…N1…N 的 NN 个房间,每个房间关押一个犯人,有 MM 种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱...

322
来自专栏郭耀华‘s Blog

剑指offer 第十一天

46.扑克牌顺子 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自...

3039
来自专栏DOTNET

.NET MongoDB Driver 2.2使用示例

说明:mongoDBService是对各种常用操作的封装 public class MongoDBService { #region 变量 ...

29310
来自专栏非著名程序员

Java 反射基础(下)

? 投稿作者:芮成兵/csdn 原文链接: http://blog.csdn.net/My_TrueLove/article/details/51306921...

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

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

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

2216
来自专栏恰同学骚年

剑指Offer面试题:25.二叉搜索树与双向链表

  首先,我们知道:在二叉树中,每个结点都有两个指向子结点的指针。在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。

611
来自专栏恰同学骚年

数据结构基础温故-6.查找(上):基本查找与树表查找

只要你打开电脑,就会涉及到查找技术。如炒股软件中查股票信息、硬盘文件中找照片、在光盘中搜DVD,甚至玩游戏时在内存中查找攻击力、魅力值等数据修改用来作弊等,都要...

653

扫描关注云+社区