二叉树遍历(Java)---前序遍历,中序遍历,后序遍历

2024-09-04 21:32

本文主要是介绍二叉树遍历(Java)---前序遍历,中序遍历,后序遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是遍历二叉树?

遍历二叉树指的是按某种规律依次访问二叉树的每个节点,对二叉树的遍历过程就是将非线性结构的二叉树中的节点排列成线性序列的过程

遍历二叉树有哪几种方法?

如果采用链表来保存二叉树的节点,则有以下两种遍历方式。

深度优先遍历:这种遍历算法将先访问到树中最深层次的节点。
广度优先遍历:这种遍历算法将逐层访问每层的节点,广度优先遍历又被称为按层遍历。

对于深度优先算法而言,它又可分为以下三种:

先(前)序遍历,分三步:
(1)访问根节点
(2)递归遍历左子树
(3)递归遍历右子树
中序遍历
(1)递归遍历左子树
(2)访问根节点
(3)递归遍历右子树
后序遍历
(1)递归遍历左子树
(2)递归遍历右子树
(3)访问根节点
本文主要介绍深度优先算法下的三种遍历方式

package 遍历二叉树;
import java.util.*; //导入含有集合框架的包
public class Example2 { static int SIZE=10;   //设定数组大小/** 构建createArray方法生成大小为SIZE的随机数组* Math。random()方法返回带正号的 double 值,该值大于等于 0.0 且小于 1.0。* 返回值是一个伪随机选择的数,在该范围内(近似)均匀分布。 */public static int[] createArray(){int[] shuzu=new int[10];for(int i=0;i<SIZE;i++){shuzu[i]=(int)(Math.random()*100);}return shuzu;}public static int[] array=createArray();  //将createArray方法的返回值赋给数组变量arrayprivate static List<Node> nodeList=null;   //将List实例对象初始化为空/** 构建Node类* 分别定义其左子节点leftChild,右子节点rightChild*/private static class Node{Node leftChild;Node rightChild;int data;Node(int newData){leftChild=null;rightChild=null;data=newData;}}/** 构建完全二叉树*/public void createBinTree(){nodeList=new LinkedList<Node>();System.out.println("原数组是:");for(int i=0;i<array.length;i++){System.out.print(array[i]+"  ");}for(int nodeIndex=0;nodeIndex<array.length;nodeIndex++){nodeList.add(new Node(array[nodeIndex]));}for(int parentIndex=0;parentIndex<array.length/2-1;parentIndex++){nodeList.get(parentIndex).leftChild=nodeList.get(parentIndex*2+1);nodeList.get(parentIndex).rightChild=nodeList.get(parentIndex*2+2);}int lastParentIndex=array.length/2-1;nodeList.get(lastParentIndex).leftChild=nodeList.get(lastParentIndex*2+1);if(array.length%2==1){nodeList.get(lastParentIndex).rightChild=nodeList.get(lastParentIndex*2+2);}}//前序遍历public static void preOrder(Node node){if( node==null) return;System.out.print (node.data+"  ");preOrder(node.leftChild);preOrder(node.rightChild);}//中序遍历private static void inOrder(Node node) {if(node==null)return;inOrder(node.leftChild);System.out.print(node.data+"  ");inOrder(node.rightChild);}//后序遍历private static void postOrder(Node node) {if(node==null)return;postOrder(node.leftChild);postOrder(node.rightChild);System.out.print(node.data+"  ");}public static void main(String[] args) {Example2 binTree=new Example2();binTree.createBinTree();Node root=nodeList.get(0);System.out.println();System.out.println("先序遍历是"+"   ");preOrder(root);System.out.println();System.out.println("中序遍历是"+"   ");inOrder(root);System.out.println();System.out.println("后序遍历是"+"   ");postOrder(root);System.out.println();}}

算法的核心在什么地方??

结合本程序来看,算法的精髓有两点:
第一,构建完全二叉树部分,也就是程序中的createBinTree()方法,方法中首先将原数组中的每个元素按下表顺序填入空树的各个节点中,然后遍历所有存在孩子节点的节点(也就是前SIZE/2个节点),然后为各个父节点建立与子节点的联系,最后生成一个完全二叉树。
第二,遍历二叉树部分,将构建完成的完全二叉树按照递归的方式进行逐个访问,按照访问顺序将节点中的数据打印出来。

非递归遍历二叉树

前序遍历

package 前序遍历;import java.util.Stack;public class PreOrder {public void preOrder(Node head){Stack<Node> stack=new Stack();stack.push(head);while(stack!=null){head=stack.pop();System.out.print(head+" ");if(head.right!=null){stack.push(head.right);}if(head.left!=null){stack.push(head.left);}}}}
class Node{public int info;public Node left;public Node right;public Node(int data){this.info=data;}}

中序遍历

package 中序遍历;import java.util.Stack;
/** 编程思路:首先将首节点和所有左子节点压入栈中* 然后开始出栈,第一个出栈的是最左边的叶子节点,再出就是该叶子节点的父节点* 到这里,就要找该父节点的右子节点,这样便完整出栈了一个二叉树结构* 最后,按这个思路继续进行,便得到我们想要的结果*/
public class InOrder {public void inOrder(Node head){if(head!=null){Stack<Node> stack=new Stack();while(!stack.isEmpty()||head!=null){if(head!=null){stack.push(head);head=head.left;}else{head=stack.pop();System.out.println(head.info+" ");head=head.right;}}}}
}
class Node{public int info;public Node left;public Node right;public Node(int data){this.info=data;}
}

后序遍历

package 后序遍历;import java.util.Stack;
/** s1为辅助堆栈,s2为真正的目标堆栈* 基本思路是后序遍历应该怎样输出,堆栈s2的元素就应该按后序遍历的逆序入栈* s1出栈顺序决定s2的入栈顺序,所以如何控制s1的出入栈是算法的核心*/
public class PosOrder {public void posOrder(Node head){if(head!=null){Stack<Node> s1=new Stack();Stack<Node> s2=new Stack();s1.push(head);while(s1!=null){head=s1.pop();s2.push(head);if(head.left!=null){s1.push(head.left);}if(head.right!=null){s1.push(head.right);}}while(s2!=null){System.out.print(s2.pop().info+" ");}}}
}
class Node{public int info;public Node left;public Node right;public Node(int data){this.info=data;}}

这篇关于二叉树遍历(Java)---前序遍历,中序遍历,后序遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137083

相关文章

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

将Java项目提交到云服务器的流程步骤

《将Java项目提交到云服务器的流程步骤》所谓将项目提交到云服务器即将你的项目打成一个jar包然后提交到云服务器即可,因此我们需要准备服务器环境为:Linux+JDK+MariDB(MySQL)+Gi... 目录1. 安装 jdk1.1 查看 jdk 版本1.2 下载 jdk2. 安装 mariadb(my

SpringBoot中配置Redis连接池的完整指南

《SpringBoot中配置Redis连接池的完整指南》这篇文章主要为大家详细介绍了SpringBoot中配置Redis连接池的完整指南,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以... 目录一、添加依赖二、配置 Redis 连接池三、测试 Redis 操作四、完整示例代码(一)pom.

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Java使用ANTLR4对Lua脚本语法校验详解

《Java使用ANTLR4对Lua脚本语法校验详解》ANTLR是一个强大的解析器生成器,用于读取、处理、执行或翻译结构化文本或二进制文件,下面就跟随小编一起看看Java如何使用ANTLR4对Lua脚本... 目录什么是ANTLR?第一个例子ANTLR4 的工作流程Lua脚本语法校验准备一个Lua Gramm

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Java Optional的使用技巧与最佳实践

《JavaOptional的使用技巧与最佳实践》在Java中,Optional是用于优雅处理null的容器类,其核心目标是显式提醒开发者处理空值场景,避免NullPointerExce... 目录一、Optional 的核心用途二、使用技巧与最佳实践三、常见误区与反模式四、替代方案与扩展五、总结在 Java

基于Java实现回调监听工具类

《基于Java实现回调监听工具类》这篇文章主要为大家详细介绍了如何基于Java实现一个回调监听工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录监听接口类 Listenable实际用法打印结果首先,会用到 函数式接口 Consumer, 通过这个可以解耦回调方法,下面先写一个

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析