文档章节

Java版二叉树的三种遍历方法

孟飞阳
 孟飞阳
发布于 2017/02/13 14:52
字数 1520
阅读 30
收藏 1
点赞 0
评论 0

基础概念

二叉树(binary tree)是一棵树,其中每个结点都不能有多于两个儿子。

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

数据结构(Java描述)之二叉树

 

二叉树的遍历

二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。二叉树的遍历方式有很多,主要有前序遍历,中序遍历,后序遍历。

前序遍历

前序遍历的规则是:若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,再前序遍历右子树

数据结构(Java描述)之二叉树

中序遍历

中序遍历的规则是:若树为空,则空操作返回;否则从根节点开始(注意并不是先访问根节点),中序遍历根节点的左子树,然后是访问根节点,最后中序遍历右子树。可以看到,如果是二叉排序树,中序遍历的结果就是个有序序列。

数据结构(Java描述)之二叉树

后序遍历

后序遍历的规则是:若树为空,则空操作返回;然后先遍历左子树,再遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。

数据结构(Java描述)之二叉树

 

删除结点

对于二叉排序树的其他操作,比如插入,遍历等,比较容易理解;而删除操作相对复杂。对于要删除的结点,有以下三种情况:

1.叶子结点;

2.仅有左子树或右子树的结点

3.左右子树都有结点

对于1(要删除结点为叶子结点)直接删除,即直接解除父节点的引用即可,对于第2种情况(要删除的结点仅有一个儿子),只需用子结点替换掉父节点即可;而对于要删除的结点有两个儿子的情况,比较常用处理逻辑为,在其子树中找寻一个结点来替换,而这个结点我们成为中序后继结点。

数据结构(Java描述)之二叉树

可以看到,我们找到的这个用来替换的结点,可以是删除结点的右子树的最小结点(6),也可以是其左子树的最大结点(4),这样可以保证替换后树的整体结构不用发生变化。为什么称为中序后继结点呢?我们来看下这棵树的中序遍历结果 1-2-3-4-5-6-7-8-9。可以很清晰的看到,其实要找的这个结点,可以是结点5的前驱或者后继。

 

代码实现

package demo3;
 public class BinaryTree { 
	 //根节点
	 private Node root; 
	 /** 树的结点 */ 
	  private static class Node{ 
		  //数据域 
		  private long data; 
		  //左子结点 
		  private Node leftChild; 
		  //右子结点 
		  private Node rightChild; 
		  Node(long data){ 
			  this.data = data; 
			  } 
		  } 
	 	public void insert(long data){ 
	 		Node newNode = new Node(data); 
	 		Node currNode = root; 
	 		Node parentNode; 
	 		//如果是空树 
	 		if(root == null){ 
	 		 root = newNode; 
	 		 return; 
	 		 } 
	 		while(true){ 
	 		 parentNode = currNode; 
	 			 //向右搜寻 
	 			 if(data > currNode.data){ 
	 				 currNode = currNode.rightChild; 
	 				 if(currNode == null){ 
	 				 parentNode.rightChild = newNode; 
	 				 return; 
	 				 } 
	 				 }else{ 
	 					 //向左搜寻 
	 					 currNode = currNode.leftChild; 
	 					 if(currNode == null){ 
	 					 parentNode.leftChild = newNode; 
	 					 return; 
	 					 } 
	 					 } 
	 			 } 
	 		 
	 		 } 
	 	 
	 	 /** 
	 	 * 前序遍历 
	 	 * @param currNode 
	 	 */ 
	 	 public void preOrder(Node currNode){ 
	 		 if(currNode == null){ 
	 		 return; 
	 		 } 
	 		 System.out.print(currNode.data+" "); 
	 		 preOrder(currNode.leftChild); 
	 		 preOrder(currNode.rightChild); 
	 		 } 
	 	 
	 	 
	 	/* 
	 	 * 中序遍历
	 	 */ 
	 	 public void inOrder(Node currNode){ 
	 		 if(currNode == null){ 
	 			return; 
	 		 } 
	 		 inOrder(currNode.leftChild); 
	 		 System.out.print(currNode.data+" "); 
	 		 inOrder(currNode.rightChild); 
	 		}

	 	/**查找结点*/
	 	public Node find(long data){
	 		Node currNode = root;
	 		while(currNode!=null){
	 		 if(data>currNode.data){
	 			 currNode = currNode.rightChild;
	 			 }else if(data<currNode.data){
	 				 currNode = currNode.leftChild;
	 				 }else{
	 					 return currNode;
	 					 }
	 		 }
	 		 return null;
	 		 }
	 	/**
	 	 *  后序遍历 
         * @param currNode
         */
	 	public void postOrder(Node currNode){
	 		if(currNode == null){
	 			return;
	 			
	 			}
	 		 postOrder(currNode.leftChild);
	 		 postOrder(currNode.rightChild);
	 		 System.out.print(currNode.data+" ");
	 		 }
	 	  /** 删除结点
	 	   *  分为3种情况 
	 	   *  1.叶子结点 
	 	   *  2.该节点有一个子节点 
	 	   *  3.该节点有二个子节点 
	 	   *  @param data 
	 	   *  
	 	   */
	 	 public boolean delete(long data) throws Exception {
	 		 Node curr = root;
	 		
	 		 //保持一个父节点的引用
	 		 Node parent = curr;
	 		 //删除为左结点还是右界定啊
	 		 boolean isLeft = true;
	 		 while(curr != null && curr.data!=data){
	 		 parent = curr;
	 		 if(data > curr.data){
	 		 curr = curr.rightChild;
	 		 isLeft = false;
	 		 }else{
	 			 curr = curr.leftChild;
	 			 isLeft = true;
	 			 }
	 		 }
	 		 if(curr==null){
	 		 throw new Exception("要删除的结点不存在");
	 		 }
	 		 //第一种情况,要删除的结点为叶子结点
	 		 if(curr.leftChild == null && curr.rightChild == null){
	 			 if(curr == root){
	 			 root = null;
	 			 return true;
	 			 }
	 			 if(isLeft){ 
	 			 parent.leftChild = null;
	 			 }else{
	 			 parent.rightChild = null;
	 			 }
	 			 }else if(curr.leftChild == null){
	 				 //第二种情况,要删除的结点有一个子节点且是右子结点
	 				 if(curr == root){
	 				 root = curr.rightChild;
	 				 return true;
	 				 }
	 				 if(isLeft){
	 				 parent.leftChild = curr.rightChild;
	 				 }else{
	 				 parent.rightChild = curr.rightChild;
	 				 }
	 				 }else if(curr.rightChild == null){
	 					 //第二种情况,要删除的结点有一个子节点且是左子结点
	 					 if(curr == root){
	 					 root = curr.leftChild;
	 					 return true;
	 					 }
	 					 if(isLeft){
	 					 parent.leftChild = curr.leftChild;
	 					 }else{
	 						 parent.rightChild = curr.leftChild;
	 						 }
	 					 }else{
	 						 //第三种情况,也是最复杂的一种情况,要删除的结点有两个子节点,需要找寻中序后继结点
	 						 Node succeeder = getSucceeder(curr);
	 						 if(curr == root){
	 						 root = succeeder;
	 						 return true;
	 						 }
	 						 if(isLeft){
	 						 parent.leftChild = succeeder;
	 						 }else{ parent.rightChild = succeeder;
	 						 }
	 						 //当后继结点为删除结点的右子结点
	 						 succeeder.leftChild = curr.leftChild;
	 						
	 						 }
	 		 return true;
	 		 }
	 	 public Node getSucceeder(Node delNode){
	 		 Node succeeder = delNode;
	 		 Node parent = delNode;
	 		 Node currNode = delNode.rightChild;
	 		 //寻找后继结点
	 		 while(currNode != null){
	 		 parent = succeeder;
	 		 succeeder = currNode;
	 		 currNode = currNode.leftChild;
	 		 }
	 		 //如果后继结点不是要删除结点的右子结点
	 		 if(succeeder != delNode.rightChild){
	 		 parent.leftChild = succeeder.rightChild;
	 		 //将后继结点的左右子结点分别指向要删除结点的左右子节点
	 		 succeeder.leftChild = delNode.leftChild;
	 		 succeeder.rightChild = delNode.rightChild;
	 		 }
	 		 return succeeder;
	 		 
	 		}
	 	 public static void main(String []args) throws Exception {
	 		 BinaryTree binaryTree = new BinaryTree(); 
	 		 //插入操作 217 binaryTree.insert(5);
	 		 binaryTree.insert(2);
	 		 binaryTree.insert(8);
	 		 binaryTree.insert(1);
	 		 binaryTree.insert(3);
	 		 binaryTree.insert(6);
	 		 binaryTree.insert(10);	 		
	 		 //前序遍历
	 		 System.out.println("前序遍历:");
	 		 binaryTree.preOrder(binaryTree.root);
	 		 System.out.println();
	 		 //中序遍历
	 		 System.out.println("中序遍历:");
	 		 binaryTree.inOrder(binaryTree.root);
	 		 System.out.println();
	 		 //后序遍历
	 		 System.out.println("后序遍历:");
	 		 binaryTree.postOrder(binaryTree.root);
	 		 System.out.println();
	 		 //查找结点
	 		 Node node = binaryTree.find(10);
	 		 System.out.println("找到结点,其值为:"+node.data);
	 		 //删除结点
	 		 binaryTree.delete(8);
	 		 System.out.print("删除结点8,中序遍历:");
	 		 binaryTree.preOrder(binaryTree.root);
	 		 }
 }

执行结果

前序遍历: 5 2 1 3 8 6 10 
中序遍历: 1 2 3 5 6 8 10
后序遍历: 1 3 2 6 10 8 5 
找到结点,其值为:10 
删除结点8,中序遍历:5 2 1 3 10 6

© 著作权归作者所有

共有 人打赏支持
孟飞阳
粉丝 202
博文 922
码字总数 537449
作品 5
朝阳
个人站长
Java学习资料-Java常用算法-二叉树算法

二叉树算法的数据结构: 二叉树结点Node实现与c中的区别是,c中采用的是结构体,而java中是用类来实现,而在c++的教材中,类是一种自定义数据结构。 二叉树的leftchild和rightchild在c中是利...

晓阳
2015/01/28
0
0
数据结构笔记--二叉查找树概述以及java代码实现

一些概念:   二叉查找树的重要性质:对于树中的每一个节点X,它的左子树任一节点的值均小于X,右子树上任意节点的值均大于X.   二叉查找树是java的TreeSet和TreeMap类实现的基础.   由于树...

冬至饮雪
2016/05/14
0
0
如何理解并掌握 Java 数据结构

一说起“数据结构”可能很多同学都又交给老师了。但是实际工作中如果做得深入一些,特别是越往上发展,越大公司越离不开数据结构。本场 Chat 作者将带领大家重温《Java 数据结构》,讲解的内...

valada
04/12
0
0
Java中系统属性Properties介绍 System.getProperty()参数大全

在JDK文档中System类中有这样的方法getProperties()在此方法的详细介绍中有下面的参数可供使用: java.version Java 运行时环境版本 java.vendor Java 运行时环境供应商 java.vendor.url Ja...

星痕2018
2012/05/29
0
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0
模仿Go语言的Benchmark测试框架写了JAVA版的简化测试工具

为了更方便的进行JAVA和Go的性能对比,于是有了搞个和Go类似的Benchmark测试框架的念头。看了两天Go的Benchmark.go源代码,写了个JAVA版的简化Benchmark测试工具。目前仅仅支持测试指定的单个...

qinhui99
2012/06/15
0
0
【二叉搜索树】Java版本,完美版本二叉搜索树,功能齐全

正文之前 经过几天下午四点到现在的功夫,然后结合算法导论和自己的一些小尝试,总算把Java版本的二叉树给做的完美了~ emm 不信的话大家伙尽管测试。。。终于!!!树形结构!用Java实现出来...

HustWolf
07/14
0
0
热修复与插件化基础——Java与Android虚拟机

一、Java虚拟机(JVM) 1、JVM整体结构 使用javac将java文件编译成class文件。 类加载器(ClassLoader)将class字节码加载进JVM对应的内存中。 JVM将内存分配给方法区、堆区、栈区、本地方式...

CSDN_LQR
05/13
0
0
二叉树算法笔记:二叉排序树(二叉搜索树) in java

本内容仅贴出三链二叉树的操作(在二叉树的两篇文章里已经有了如下代码,完全相同,只是这里把二叉排序树的代码提取出来而已)。 二叉树算法笔记:二叉树基础操作(三链二叉树) in java http:...

CheN_exe
2014/01/26
0
0
LeetCode:Binary Tree Paths - 获取一棵树从顶点到每个叶节点的路径

1、题目名称 Binary Tree Paths(获取一棵树从顶点到每个叶节点的路径) 2、题目地址 https://leetcode.com/problems/binary-tree-paths/ 3、题目内容 英文:Given a binary tree, return a...

北风其凉
2015/11/11
0
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

rabbitmq学习记录(六)交换机Exchange-direct

实现功能:一条消息发送给多个消费者 交换机模式:direct 相比于之前的fanout模式,可以进一步的筛选获取消息的消费者。 fanout模式下,只要消费者监听的队列,已经与接收生产者消息的交换机...

人觉非常君
14分钟前
0
0
Java 之 枚举

Java 中声明的枚举类,均是 java.lang.Enum 类的子类,Enun 类中的常用方法有: name() 返回枚举对象名称 ordinal() 返回枚举对象下标 valueOf(Class enumType, String name) 转换枚举对象 ...

绝世武神
22分钟前
0
0
使用爬虫实现代理IP池之放弃篇

啥叫代理IP以及代理IP池 概念上的东西网上搜索一下就好了,这里简单科普一下(大部分会读这篇文章的人,基本是不需要我来科普的),白话说就是能联网并提供代理访问互联网的服务器,它提供的...

一别丶经年
38分钟前
0
0
sqoop导入数据到Base并同步hive与impala

使用Sqoop从MySQL导入数据到Hive和HBase 及近期感悟 基础环境 Sqool和Hive、HBase简介 Sqoop Hive HBase 测试Sqoop 使用Sqoop从MySQL导入数据到Hive 使用复杂SQL 调整Hive数据类型 不断更新 ...

hblt-j
今天
0
0
Dart 服务端开发 文件上传

clent端使用angular组件 upload_component.html form id="myForm" method="POST" enctype="multipart/form-data"> <input type="file" name="fileData"> <!-- file field --></form>......

scooplol
今天
0
0
apache和tomcat同时开启,乱码问题

tomcat和apache同时开启,会走apache的转发,执行的是AJP/1.3协议。所以在tomcat的配置文件server中, <Connector port="8009" protocol="AJP/1.3" redirectPort="8443" useBodyEncodingForU......

Kefy
今天
0
0
使用ssh-keygen和ssh-copy-id三步实现SSH无密码登录 和ssh常用命令

ssh-keygen 产生公钥与私钥对. ssh-copy-id 将本机的公钥复制到远程机器的authorized_keys文件中,ssh-copy-id也能让你有到远程机器的home, ~./ssh , 和 ~/.ssh/authorized_keys的权利 第一步...

xtof
今天
0
0
orcale 查询表结构

SELECT t.table_name, t.colUMN_NAME, t.DATA_TYPE || '(' || t.DATA_LENGTH || ')', t1.COMMENTS FROM User_Tab_Cols t, User_Col_Comments t1WHERE t.table_name......

wertwang
今天
0
0
华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大

华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大!华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大! 在华为最新发布的nova 3手机上,抖音通过华为himedia SDK集成了60fps、超级...

华为终端开放实验室
今天
0
0
多 SSH Key 实现同一台服务器部署多 Git 仓库

本文以以下需求为背景,介绍详细的做法: 需在同一台服务器同时部署两个不同的 Github 仓库(对 Bitbucket 等 git 服务同样适用) root 用户可在远程登录 SSH 后附上预期的 SSH Key 进行 gi...

yeahlife
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部