Java实现二叉树的深度优先遍历和广度优先遍历算法示例
作者:Fantasy_Lin_ 发布时间:2021-07-16 12:37:17
本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法。分享给大家供大家参考,具体如下:
1. 分析
二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。
深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下:
先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
2. 举例说明
对下图所示的二叉排序树进行遍历,要求使用先序遍历(递归、非递归)、中序遍历(递归、非递归)、后序遍历(递归、非递归)和广度优先遍历。
① 参考代码
package BinaryTreeTraverseTest;
import java.util.LinkedList;
import java.util.Queue;
/**
* 二叉树的深度优先遍历和广度优先遍历
* @author Fantasy
* @version 1.0 2016/10/05 - 2016/10/07
*/
public class BinaryTreeTraverseTest {
public static void main(String[] args) {
BinarySortTree<Integer> tree = new BinarySortTree<Integer>();
tree.insertNode(35);
tree.insertNode(20);
tree.insertNode(15);
tree.insertNode(16);
tree.insertNode(29);
tree.insertNode(28);
tree.insertNode(30);
tree.insertNode(40);
tree.insertNode(50);
tree.insertNode(45);
tree.insertNode(55);
System.out.print("先序遍历(递归):");
tree.preOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("中序遍历(递归):");
tree.inOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("后序遍历(递归):");
tree.postOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("先序遍历(非递归):");
tree.preOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("中序遍历(非递归):");
tree.inOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("后序遍历(非递归):");
tree.postOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("广度优先遍历:");
tree.breadthFirstTraverse(tree.getRoot());
}
}
/**
* 结点
*/
class Node<E extends Comparable<E>> {
E value;
Node<E> left;
Node<E> right;
Node(E value) {
this.value = value;
left = null;
right = null;
}
}
/**
* 使用一个先序序列构建一棵二叉排序树(又称二叉查找树)
*/
class BinarySortTree<E extends Comparable<E>> {
private Node<E> root;
BinarySortTree() {
root = null;
}
public void insertNode(E value) {
if (root == null) {
root = new Node<E>(value);
return;
}
Node<E> currentNode = root;
while (true) {
if (value.compareTo(currentNode.value) > 0) {
if (currentNode.right == null) {
currentNode.right = new Node<E>(value);
break;
}
currentNode = currentNode.right;
} else {
if (currentNode.left == null) {
currentNode.left = new Node<E>(value);
break;
}
currentNode = currentNode.left;
}
}
}
public Node<E> getRoot(){
return root;
}
/**
* 先序遍历二叉树(递归)
* @param node
*/
public void preOrderTraverse(Node<E> node) {
System.out.print(node.value + " ");
if (node.left != null)
preOrderTraverse(node.left);
if (node.right != null)
preOrderTraverse(node.right);
}
/**
* 中序遍历二叉树(递归)
* @param node
*/
public void inOrderTraverse(Node<E> node) {
if (node.left != null)
inOrderTraverse(node.left);
System.out.print(node.value + " ");
if (node.right != null)
inOrderTraverse(node.right);
}
/**
* 后序遍历二叉树(递归)
* @param node
*/
public void postOrderTraverse(Node<E> node) {
if (node.left != null)
postOrderTraverse(node.left);
if (node.right != null)
postOrderTraverse(node.right);
System.out.print(node.value + " ");
}
/**
* 先序遍历二叉树(非递归)
* @param root
*/
public void preOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = null;
stack.push(root);
while (!stack.isEmpty()) {
currentNode = stack.pop();
System.out.print(currentNode.value + " ");
if (currentNode.right != null)
stack.push(currentNode.right);
if (currentNode.left != null)
stack.push(currentNode.left);
}
}
/**
* 中序遍历二叉树(非递归)
* @param root
*/
public void inOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = root;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
System.out.print(currentNode.value + " ");
currentNode = currentNode.right;
}
}
/**
* 后序遍历二叉树(非递归)
* @param root
*/
public void postOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = root;
Node<E> rightNode = null;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
// 当前结点没有右结点或上一个结点(已经输出的结点)是当前结点的右结点,则输出当前结点
while (currentNode.right == null || currentNode.right == rightNode) {
System.out.print(currentNode.value + " ");
rightNode = currentNode;
if (stack.isEmpty()) {
return; //root以输出,则遍历结束
}
currentNode = stack.pop();
}
stack.push(currentNode); //还有右结点没有遍历
currentNode = currentNode.right;
}
}
/**
* 广度优先遍历二叉树,又称层次遍历二叉树
* @param node
*/
public void breadthFirstTraverse(Node<E> root) {
Queue<Node<E>> queue = new LinkedList<Node<E>>();
Node<E> currentNode = null;
queue.offer(root);
while (!queue.isEmpty()) {
currentNode = queue.poll();
System.out.print(currentNode.value + " ");
if (currentNode.left != null)
queue.offer(currentNode.left);
if (currentNode.right != null)
queue.offer(currentNode.right);
}
}
}
② 输出结果
先序遍历(递归):35 20 15 16 29 28 30 40 50 45 55
中序遍历(递归):15 16 20 28 29 30 35 40 45 50 55
后序遍历(递归):16 15 28 30 29 20 45 55 50 40 35
先序遍历(非递归):35 20 15 16 29 28 30 40 50 45 55
中序遍历(非递归):15 16 20 28 29 30 35 40 45 50 55
后序遍历(非递归):16 15 28 30 29 20 45 55 50 40 35
广度优先遍历:35 20 40 15 29 50 16 28 30 45 55
希望本文所述对大家java程序设计有所帮助。
来源:https://blog.csdn.net/fantasy_lin_/article/details/52751559
猜你喜欢
- 本文实例讲述了C#资源释放方法。分享给大家供大家参考,具体如下:1、try{}finally{}2、using只有类型实现了IDisposa
- 一、注解注解(Annotation): 从jdk5.0开始引进,可以对程序进行解释或被其他程序读取。注解格式:"@注释名"
- 本文接上文“java反射之方法反射的基本操作方法”,利用反射了解下java集合中泛型的本质1、初始化两个集合,一个使用泛型,一个不使用Arr
- 学习过java基础,最近趁着大量课余时间想学习Android开发。百度很多资料Android studio,由Google开发的开发工具,那
- * 在JavaWeb开发中用得比较多Java Web开发中的 * (listener)就是application、session、requ
- 冒泡排序算法演示图:public static void bubbleSort(int[] array) { &
- 在开发Android应用程序中,经常会自定义View来实现各种各样炫酷的效果,在实现这吊炸天效果的同时,我们往往会定义很多attr属性,这样
- 1、@Valid与@Validated的区别1.1 基本区别@Valid:Hibernate validation校验机制@Validate
- 一、Spring-boot配置mybatis的mapper-locations解决什么问题?mapper-locations顾名思义是一个定
- 1. Spring 是什么我们通常所说的 Spring 指的是 Spring Framework(Spring 框架),它是一个开源框架,有
- 读取自定义properties注入到bean在使用springboot项目时,可使用@value的方式直接读取application.pro
- 本文实例为大家分享了java多线程之铁路售票系统的具体代码,供大家参考,具体内容如下问题:铁路售票,一共100张,通过四个窗口卖完。要求:分
- 什么是委托?委托是寻址方法的.NET版本,使用委托可以将方法作为参数进行传递。委托是一种特殊类型的对象,其特殊之处在于委托中包含的只是一个活
- WPF 实现筛选下拉多选控件框架使用.NET4 至 .NET6;Visual Studio 2022;创建 MultiSelect
- 下面展示一下FTP软件上传功能的过程,具有一定的参考价值,感兴趣的小伙伴们可以参考一下1、上传前上传前选择好要将文件或文件夹上传到远程FTP
- 这篇文章主要介绍了Java使用Collections工具类对List集合进行排序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一
- 在做项目中经常会遇到有项目需求是需要判断字符为中文的一些问题,所以搜集了判断中文字符的代码片段,特此分享供大家参考。直接贴出代码了,里面有详
- 一、默认异常处理机制默认情况下,SpringBoot 提供 /error 请求,来处理所有异常的。1.浏览器客户端,请求头里的属性是Acce
- 简介Maven为我们封装了很多构建中非常有用的操作,我们只需要执行简单的几个mvn命令即可。今天我们要讨论一下mvn命令之下的生命周期的构建
- 同线程回收对象上一小节剖析了从recycler中获取一个对象, 这一小节分析在创建和回收是同线程的前提下, recycler是如何进行回收的