import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class LevelTraverseBinaryTree {
/**
* 编程之美 分层遍历二叉树
* 之前已经用队列实现过二叉树的层次遍历,但这次要求输出换行,因此要标记什么时候要换行:
* 用inCount记录某层有多少个元素,outCount记录当前输出了多少个元素;当inCount==outCount时,就说明某层元素已经完全输出,此时应该换行(outCount清零)
* 此外,观察发现,当第K层元素全部出队(并已将各自左右孩子入队)后,队列里面刚好存放了第K+1层的所有元素,不多不少,所以有:inCount = queue.size();
*
* 书上的扩展问题也很有意思(从下往上分层输出),既然是反过来输出,第一反应是利用栈
* 但同时又要记录何时换行(每行有多少个元素),只好用ArrayList模拟一个“伪栈”:
* 1、第一步操作和“从上往下分层输出”是类似的:从root开始遍历,并将所有元素放入“队列”(ArrayList),用-1表示一层的结束
* 2、输出。不是从队头开始,而是从队尾开始,依次输出
* 分析到这里,这里面的ArrayList定义为“双向队列”更合适
*/
public static void main(String[] args) {
/*
__1__
/ \
__2__ 3__
/ \ \
4 __5__ 6
7 8
*/
int[] src = { 1, 2, 3, 4, 5, 0, 6, 0, 0, 7, 8 };
LevelTraverseBinaryTree data = new LevelTraverseBinaryTree();
Node root = data.createTree(src);
data.traverseByLevelFromTop(root);
System.out.println();
data.traverseByLevelFromBottom(root);
}
/*
从上往下分层输出
1
2 3
4 5 6
7 8
*/
public void traverseByLevelFromTop(Node node) {
if (node == null) {
return;
}
LinkedList<Node> queue = new LinkedList<Node>();
queue.addLast(node);
int inCount = 1;
int outCount = 0;
while (!queue.isEmpty()) {
Node curNode = queue.pollFirst();
System.out.print(curNode.getData() + " ");
outCount++;
if (curNode.getLeft() != null) {
queue.addLast(curNode.getLeft());
}
if (curNode.getRight() != null) {
queue.addLast(curNode.getRight());
}
if (outCount == inCount) {
System.out.println();
inCount = queue.size();
outCount = 0;
}
}
}
/*
从下往上分层输出
7 8
4 5 6
2 3
1
*/
public void traverseByLevelFromBottom(Node node) {
if (node == null) {
return;
}
List<Node> list = new ArrayList<Node>();
list.add(node);
list.add(new Node(-1)); //-1表示一层结束,打印时要换行
int i = 0;
int size = list.size();
while (i < size) {
Node curNode = list.get(i);
/*交换下面这两个操作,可实现输出:
8 7
6 5 4
3 2
1
*/
if (curNode.getRight() != null) {
list.add(curNode.getRight());
}
if (curNode.getLeft() != null) {
list.add(curNode.getLeft());
}
i++;
if (i == size) {
if (curNode.getData() != -1 && curNode.getLeft() == null && curNode.getRight() == null) { //已经遍历到最底层的最后一个元素,结束循环
break;
}
size = list.size();
list.add(new Node(-1));
}
}
//从后往前遍历,相当于“栈”
for (size = list.size(), i = size - 1; i >=0; i--) {
int val = list.get(i).getData();
if (val == -1) {
System.out.println();
} else {
System.out.print(val + " ");
}
}
}
public Node createTree(int[] data){
List<Node> nodeList=new ArrayList<Node>();
for(int each:data){
Node n=new Node(each);
nodeList.add(n);
}
int lastRootIndex=data.length/2-1;
for(int i=0;i<=lastRootIndex;i++){
Node root=nodeList.get(i);
Node left=nodeList.get(i*2+1);
if(left.getData()!=0){
root.setLeft(left);
}else{
root.setLeft(null);
}
if(i*2+2<data.length){
Node right=nodeList.get(i*2+2);
if(right.getData()!=0){
root.setRight(right);
}else{
root.setRight(null);
}
}
}
Node root=nodeList.get(0);
return root;
}
}
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
分享到:
相关推荐
算法6.1-6.3遍历二叉树.rar
1 已知二叉树以二叉链表作为存储结构,写一个算法按层序遍历它,通过程序在终端屏幕上打印出它的层序序列。 2 先建立二叉树的二叉链表存储结构,再遍历它。 3 利用队列完成算法。
/*选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等) 【实验内容】 必做内容 程序的菜单功能项如下: 1----...
中序遍历二叉树的简单实现
完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全二叉树的层序遍历-labview完全...
分层遍历二叉树
数据结构非递归先序、中序、后序遍历二叉树,数据结构非递归先序、中序、后序遍历二叉树
二叉树遍历问题-二叉树遍历问题
软件技术基础大作业--二叉树遍历,包含流程图,源代码,和文字说明
【源码】【数据结构几个实例】【约瑟夫环问题--停车场管理--二叉树的建立与遍历--图遍历--哈希表设计】
1---建立二叉树 2---前序遍历(递归) 3---前序遍历(非递归) 4---中序遍历(递归) 5---中序遍历(非递归) 6---后序遍历(递归) 7---后序遍历(非递归) 8---求树高 9---求叶子总数 10---输出二叉树 11...
实现二叉树遍历,要求采用两种遍历方式实现,其中层次遍历为必选,另一实现可选择层次、前序、后序、中序中的任意一种;作业中应明确指出自身所采用的遍历方式。
层次遍历二叉树
遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
按层次遍历二叉树的算法 简单易懂 按层次遍历二叉树的算法 简单易懂
java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...
算法-理论基础- 二叉树- 二叉树的遍历(包含源程序).rar
小小学习,C语言数据结构,中序遍历二叉树非递归算法
数据结构二叉树的遍历,用到队列,是二叉树必须掌握的一种操作。