java 完全二叉树的构建与四种遍历方法示例
作者:Gonjian 发布时间:2022-03-21 00:48:04
标签:java,二叉树
本来就是基础知识,不能丢的太干净,今天竟然花了那么长的时间才写出来,记一下。
有如下的一颗完全二叉树:
先序遍历结果应该为:1 2 4 5 3 6 7
中序遍历结果应该为:4 2 5 1 6 3 7
后序遍历结果应该为:4 5 2 6 7 3 1
层序遍历结果应该为:1 2 3 4 5 6 7
二叉树的先序遍历、中序遍历、后序遍历其实都是一样的,都是执行递归操作。
我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素检查是其是否有左右孩子,有则将其加入队列,由于利用队列的先进先出原理,进行层次遍历。
下面记录下完整代码(Java实现),包括几种遍历方法:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
/**
* 定义二叉树节点元素
* @author bubble
*
*/
class Node {
public Node leftchild;
public Node rightchild;
public int data;
public Node(int data) {
this.data = data;
}
}
public class TestBinTree {
/**
* 将一个arry数组构建成一个完全二叉树
* @param arr 需要构建的数组
* @return 二叉树的根节点
*/
public Node initBinTree(int[] arr) {
if(arr.length == 1) {
return new Node(arr[0]);
}
List<Node> nodeList = new ArrayList<>();
for(int i = 0; i < arr.length; i++) {
nodeList.add(new Node(arr[i]));
}
int temp = 0;
while(temp <= (arr.length - 2) / 2) { //注意这里,数组的下标是从零开始的
if(2 * temp + 1 < arr.length) {
nodeList.get(temp).leftchild = nodeList.get(2 * temp + 1);
}
if(2 * temp + 2 < arr.length) {
nodeList.get(temp).rightchild = nodeList.get(2 * temp + 2);
}
temp++;
}
return nodeList.get(0);
}
/**
* 层序遍历二叉树,,并分层打印
* @param root 二叉树根节点
*
*/
public void trivalBinTree(Node root) {
Queue<Node> nodeQueue = new ArrayDeque<>();
nodeQueue.add(root);
Node temp = null;
int currentLevel = 1; //记录当前层需要打印的节点的数量
int nextLevel = 0;//记录下一层需要打印的节点的数量
while ((temp = nodeQueue.poll()) != null) {
if (temp.leftchild != null) {
nodeQueue.add(temp.leftchild);
nextLevel++;
}
if (temp.rightchild != null) {
nodeQueue.add(temp.rightchild);
nextLevel++;
}
System.out.print(temp.data + " ");
currentLevel--;
if(currentLevel == 0) {
System.out.println();
currentLevel = nextLevel;
nextLevel = 0;
}
}
}
/**
* 先序遍历
* @param root 二叉树根节点
*/
public void preTrival(Node root) {
if(root == null) {
return;
}
System.out.print(root.data + " ");
preTrival(root.leftchild);
preTrival(root.rightchild);
}
/**
* 中序遍历
* @param root 二叉树根节点
*/
public void midTrival(Node root) {
if(root == null) {
return;
}
midTrival(root.leftchild);
System.out.print(root.data + " ");
midTrival(root.rightchild);
}
/**
* 后序遍历
* @param root 二叉树根节点
*/
public void afterTrival(Node root) {
if(root == null) {
return;
}
afterTrival(root.leftchild);
afterTrival(root.rightchild);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
TestBinTree btree = new TestBinTree();
int[] arr = new int[] {1,2,3,4,5,6,7};
Node root = btree.initBinTree(arr);
System.out.println("层序遍历(分层打印):");
btree.trivalBinTree(root);
System.out.println("\n先序遍历:");
btree.preTrival(root);
System.out.println("\n中序遍历:");
btree.midTrival(root);
System.out.println("\n后序遍历:");
btree.afterTrival(root);
}
}
遍历结果:
来源:http://www.cnblogs.com/gonjan-blog/p/6504668.html


猜你喜欢
- CamShift算法全称是“Continuously Adaptive Mean-Shift”(连续的自适应MeanShift算法),是对M
- 去公司面试,对方一口一个controller,一口一个service,dao,搞得我很紧张。其实都是很简单的东西,只是自己当时不知道罢了,接
- 前言在实际开发当中,Spring中bean的属性直接赋值用的不是太多,整理这方面的资料,做一个小结,以备后续更深入的学习。通过配置文件的方式
- springBoot yml文件的list读取问题折腾了很久,记录下。配置如下# 自定义数据上报信息xx: # 机组信息 &nb
- 当我们右键点击listview控件时,可以得到选择的项的各个文本内容。现在我们要求只获取右键点击时的单元格的文本内容。方法如下:1、定义全局
- 1. Text日常最常用的应该就是显示文字,所以有必要说一下Text控件。首先源码如下:@Composablefun Text(  
- 一、数据类型与变量的介绍在程序运行的过程中计算机需要记录大量的状态 数据(这里我们统称数据)。那这些数据都存放在哪呢?程序在运行过程中的数据
- 篇首,完全没有技术含量的帖子,高手略过,只为十几年后重新捡起的我爱好玩玩。。。起因,一个朋友说他下载了很多短视频,但只需要要其中的一小截,去
- 一、简介Android的消息机制主要是指Handler的运行机制,那么什么是Handler的运行机制那?通俗的来讲就是,使用Handler将
- xxx cannot be resolved to a type引言 eclipse新导入的项目经常可以
- 使用volley进行网络请求:需先将volley包导入androidstudio中File下的Project Structrue,点加号导包
- 前言大家在学习Java的过程中,或者工作中,始终都绕不开集合。在单线程环境下,ArrayList就可以满足要求。多线程时,我们可以使用Cop
- 本文实例讲述了C#实现带阴历显示的日期代码,分享给大家供大家参考。具体方法如下:这是一个用于酒店预定功能的带日期控件,类似去哪网酒店预定,由
- 目标:查询数据库中的字段,然后转换成 JSON 格式的数据,返回前台。环境:idea 2016.3.4, jdk 1.8, mysql 5.
- 前言最近的项目中需要用到VideoView实现视频播放,自己花了一天多时间才能出来,有点想打自己再见,在学校的时候没好好学。使用VideoV
- 由于项目没有设计返回键,一旦进入别的应用,就无法回到桌面。只能通过串口输入input keyevent 4(返回键)来返回桌面,为了方便调试
- 本文主要带大家看看Object类中一些常用方法的API文档的介绍和JDK中的源码。1.equals方法1.API中equals方法的介绍2.
- spring cloud我想做成一个系列,所以spring cloud+eureka后面会慢慢说到的,有兴趣的小伙伴可以关注后续!这一节就简
- 本篇主要讲解如何使用Ideal 搭建Spring的源码环境,想必大家都会多多少少去看过Spring的部分源码,一般我们都是直接点进某个Spr
- 先来个效果图觉得不好看可以自己调整1.绘制数据点线状图一般由数据点和连线组成在绘制连线之前,我们先标出数据点这里我选择用Image图片来绘制