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

相关文章

来自专栏尾尾部落

[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

链接:https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorde...

862
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

本题详细的分析过程均在代码注释中: import java.util.Iterator; import java.util.Stack; /** * 题目:...

2755
来自专栏WD学习记录

LeetCode Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating chara...

872
来自专栏aCloudDeveloper

算法导论第十二章 二叉搜索树

一、二叉搜索树概览   二叉搜索树(又名二叉查找树、二叉排序树)是一种可提供良好搜寻效率的树形结构,支持动态集合操作,所谓动态集合操作,就是Search、Max...

19610
来自专栏机器学习实践二三事

二叉排序树的建立和遍历(java)

也是个经典的面试题,要求建立二叉排序树同时实现树的遍历,其实不难,直接上代码吧 树节点定义: class TreeNode{ int val; ...

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

PTA 二叉树求深度和叶子数(20 分)

二叉树求深度和叶子数(20 分) 编写函数计算二叉树的深度以及叶子节点数。二叉树采用二叉链表存储结构 函数接口定义: int GetDepthOfBiTree ...

2049
来自专栏机器学习实践二三事

二叉树的建立和各种遍历(java版)

这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题 先序+中序 ->建树 假设现在有个二叉树,如下: ? 此时遍历顺序是: ...

2095
来自专栏猿人谷

树的子结构

题目:输入两棵二叉树A和B,判断B是不是A的子结构。 二叉树结点的定义如下: struct BinaryTreeNode { int ...

1918
来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

542
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

794

扫码关注云+社区