java【二叉树】

本贴最后更新于 1284 天前,其中的信息可能已经事过景迁

上一篇文章为大家带来了一个关于链表的结构实现,我采用是内部类实现方式,那对于链表而言的话,链表缺点就是检索数据,那当然有人会提出一些优化方法,例如我们在学习集合时候了解到,二叉树,红黑树等,在数据改变的情况,进行对数据旋转,达到一个树的左右平衡,以此达到一个最佳的数据检索到效率。

下面的一个 demo 主要便于我们理解二叉树数据结构,同样我们采用也是内部类的方式,对于红黑树的话,其实是在二叉树的基本在进行进一步数据优化,但是目前我还不能用代码的形式为大家展示【很复杂 😭 】,有兴趣的可以去关于数据结构的书籍。

不说了,上代码

代码里面有注解大部分设计思路。

package ITaljavaT3;
/**
 * 实现二叉树的操作
 * @author Administrator
 * @param <T> 要进行二叉树的实现
 * <? extends Comparable<? super T>>
 * 代表任何实现了comparable接口的实例,且接口的类型是comparable<T 或其父类>。
<T extends Comparable<? super T>>
代表类型是T的实例,且这个T要实现comparable 接口,接口的类型是comparable<T 或其父类>
 */
class BinaryTree< T extends Comparable<T>>{
		//节点内部类
		private class Node{
			private Comparable<T> date;//保存数据在comparable中可以进行大小的比较,还可以进行向下强制性转换;
			private Node parent; //保存父节点
			private Node left;   //保存左节点
			private Node right;  //保存左节点
			public Node(Comparable<T> date) {
				this.date=date;//进行数据的初始化
			}
			/**
			 * 进行数据的保存处理
			 * @param date 需要进行保存的数据
			 */
			public void addarrays(Node newNode) {
				//将当前的数据和newNode类中的数据进行比较,如果大于0,向右,小于0向左
				if(newNode.date.compareTo((T)this.date)<=0) {
					if(this.left==null) {//现在没有左子树
						this.left=newNode;//进行数据的保存
						newNode.parent=this;//进行父节点的保存
					}else {//继续进行左子树的判断
						this.left.addarrays(newNode);
					}
				}else {
					if(this.right==null) {//右子树为的话
						this.right=newNode;//进行右子树保存
						newNode.parent=this;//进行父节点的保存
					}else {//继续济宁右子树的判断
						this.right.addarrays(newNode);
					}
				}
			}
			/**
			 * 采用中序遍历的方式进行数据的输出
			 */
			public void toarraysNode() {
				//左
				if(this.left!=null) {//左子树不为空话
					//继续进行数据的获取
					this.left.toarraysNode();
				}
				//进行数据的获取并且复制(数据的获取)
				BinaryTree.this.returndate[BinaryTree.this.foot++]=this.date;
				//右
				if(this.right!=null) {//右子树不为空
					//继续进行数据的获取
					this.right.toarraysNode();
				}
			}
			//进行数据的查询
			public boolean judgedate(Comparable<T> date) {
				if(date.compareTo((T)this.date)==0) {
					return true;
				}else if(date.compareTo((T)this.date)<0) {//左边有数据
					if(this.left!=null) {
						//递归调用
						return this.left.judgedate(date);
					}else {
						return false;
					}
				}else {
					if(this.right!=null) {
						//递归调用
						return this.right.judgedate(date);
					}else {
						return false;
					}
				}
			}
		
			//进行删除数据的获取
			public Node getRemoveNode(Comparable<T> date) {
				if(date.compareTo((T)this.date)==0) {
					return this;
				}else if(date.compareTo((T)this.date)<0) {//左边有数据
					if(this.left!=null) {
						//递归调用
						return this.left.getRemoveNode(date);
					}else {
						return null;
					}
				}else {
					if(this.right!=null) {
						//递归调用
						return this.right.getRemoveNode(date);
					}else {
						return null;
					}
				}
			}

	}
		//---------------以下时候BinaryTree中的操作--------------------------
		private Node root;  //二叉树的根节点
		private int count;  // 保存数据的个数
		private Object[] returndate;// 进行数据返回
		private int foot=0;//进行数据返回的角标处理
		/**
		 * 进行数据的保存操作
		 * @param date 要保存的数据内容
		 */
		public void add(Comparable<T> date) {
			if(date==null) {
				throw new NullPointerException("date数据为空");
			}
			//所有的数据是不存在数据的节点操作的,所有需要将数据存在节点中
			Node newNode=new Node(date);
			if(this.root==null) {
				this.root=newNode;//判断节点是否为空,为空的话,将数据赋值给根节点
			}else {
				this.root.addarrays(newNode);//将数据添加的操作给Node进行数据的处理
			}
			this.count++;
		}
	
		//进行数据的添加以后,就得进行数据的返回操作
		public Object[] getarray() {
			if(this.count==0) {
				return null;
			}
			//进行数据的返回操作
			this.returndate=new Object[this.count];//进行数组的长度保存
			this.foot=0;//角标清零
			this.root.toarraysNode();//将这个获取数据的操作交给Node类进行数据的获取处理
			return this.returndate;
		}
	
		//进行数据的查询(判断数据是否存在)
		public boolean seacherdate(Comparable<T> date) {
			if(date==null) {
				return false;
			}
			return this.root.judgedate(date);
		}
	
	//进行删除数据的获取,然后进行数据的删除
	public void remove(Comparable<T> date) {
		if(date==null && this.root.judgedate(date)) {
			System.out.println("数据查询不到");
		return ;
	}else {
		//进行判断删除的是否为根节点
	if(date.compareTo((T)this.root.date)==0){
		//进行根节点的删除
	Node move=this.root.right;//移动的角标对象
	while(move.left!=null) {
		move=move.left;//一直进行最最左边的数据进行获取
	}
	move.left=this.root.left;//左边进行赋值
	move.right=this.root.right;//右边赋值
	move.parent.left=null;//原始上一个节点的去除
		this.root=move;
	}else {
		Node removeNode=this.root.getRemoveNode(date);//获取到需要删除的Node类
	if(removeNode.left==null && removeNode.right==null) {
		removeNode.parent.left=null;
		removeNode.parent.right=null;
		//removeNode.parent=null;
	}else if(removeNode.left==null && removeNode.right!=null) {
		//将删除Node类的下一个类中right改成删除类的上一个的左节点,然后将其删除类的right中的父节点改成删除类的上一个当前对象
		removeNode.parent.left=removeNode.right;
		removeNode.left.parent=removeNode.parent;
	}else if(removeNode.left!=null && removeNode.right==null) {
		removeNode.parent.left=removeNode.left;
		removeNode.left.parent=removeNode.parent;
	}else {
		//两者都存在的情况(这种情况是将删除数据替换成右边最左下角的那个对象Node)
		Node moveNode=removeNode.right;
		while(moveNode.left!=null) {
			moveNode=moveNode.left;
		}
	
		//左替换
		moveNode.left=removeNode.left;
		//右替换
		moveNode.right=removeNode.right;
		//上一个节点的左节点替换
		removeNode.parent.left=moveNode;
		moveNode.parent.left=null; //原始断开左节点
			//父类替换
		moveNode.parent=removeNode.parent;
	}

	}
		this.count--;
	}
		}
	
	}
	class person implements Comparable<person>{
		private String name;
		private int age;
		public person(String name,int age) {
			this.name=name;
			this.age=age;
		}
		@Override
		public int compareTo(person per) {
			// TODO Auto-generated method stub
			if(this.age>per.age) {
				return 1;
			}else if (this.age<per.age){
				return -1;
			}
			return 0;
		
		}
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "姓名"+this.name+"年龄"+this.age+"\n";
		}
	}

public class  javaDemo01{
		public static void main(String[] args) {
			//进行数据的添加
			BinaryTree<person> bt=new BinaryTree<person>();
			bt.add(new person("小强-80",80));
			bt.add(new person("小强-50",50));
			bt.add(new person("小强-30",30));
			bt.add(new person("小强-60",60));
			bt.add(new person("小强-10",10));
			bt.add(new person("小强-55",55));
			bt.add(new person("小强-70",70));
			bt.add(new person("小强-90",90));
			bt.add(new person("小强-85",85));
			bt.add(new person("小强-95",95));
		
			//进行数据的获取
			Object[] obj=bt.getarray();
			for(Object temp:obj) {
				System.out.println(temp);
			}
			//进行数据的删除
			//bt.remove(new person("小强10",10));
			//bt.remove(new person("小强30",30));
			//bt.remove(new person("小强80",80));
			bt.remove(new person("小强50",50));
			System.out.println("删除以后进行遍历");
			Object[] obj2=bt.getarray();
			for(Object temp:obj2) {
				System.out.println(temp);
			}
		}
}

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3186 引用 • 8212 回帖
  • 二叉树
    8 引用 • 1 回帖
  • 数据结构
    88 引用 • 115 回帖 • 4 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Swift

    Swift 是苹果于 2014 年 WWDC(苹果开发者大会)发布的开发语言,可与 Objective-C 共同运行于 Mac OS 和 iOS 平台,用于搭建基于苹果平台的应用程序。

    36 引用 • 37 回帖 • 535 关注
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。

    75 引用 • 1737 回帖
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    55 引用 • 85 回帖 • 2 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • TensorFlow

    TensorFlow 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edges)则表示在节点间相互联系的多维数据数组,即张量(tensor)。

    20 引用 • 19 回帖
  • 快应用

    快应用 是基于手机硬件平台的新型应用形态;标准是由主流手机厂商组成的快应用联盟联合制定;快应用标准的诞生将在研发接口、能力接入、开发者服务等层面建设标准平台;以平台化的生态模式对个人开发者和企业开发者全品类开放。

    15 引用 • 127 回帖 • 2 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 45 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 461 关注
  • 房星科技

    房星网,我们不和没有钱的程序员谈理想,我们要让程序员又有理想又有钱。我们有雄厚的房地产行业线下资源,遍布昆明全城的 100 家门店、四千地产经纪人是我们坚实的后盾。

    6 引用 • 141 回帖 • 584 关注
  • React

    React 是 Facebook 开源的一个用于构建 UI 的 JavaScript 库。

    192 引用 • 291 回帖 • 402 关注
  • CongSec

    本标签主要用于分享网络空间安全专业的学习笔记

    1 引用 • 1 回帖 • 10 关注
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 383 关注
  • 倾城之链
    23 引用 • 66 回帖 • 138 关注
  • 安装

    你若安好,便是晴天。

    132 引用 • 1184 回帖 • 1 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    286 引用 • 248 回帖 • 74 关注
  • OpenStack

    OpenStack 是一个云操作系统,通过数据中心可控制大型的计算、存储、网络等资源池。所有的管理通过前端界面管理员就可以完成,同样也可以通过 Web 接口让最终用户部署资源。

    10 引用 • 2 关注
  • HBase

    HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。

    17 引用 • 6 回帖 • 70 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖
  • QQ

    1999 年 2 月腾讯正式推出“腾讯 QQ”,在线用户由 1999 年的 2 人(马化腾和张志东)到现在已经发展到上亿用户了,在线人数超过一亿,是目前使用最广泛的聊天软件之一。

    45 引用 • 557 回帖 • 85 关注
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。

    110 引用 • 54 回帖 • 3 关注
  • GitHub

    GitHub 于 2008 年上线,目前,除了 Git 代码仓库托管及基本的 Web 管理界面以外,还提供了订阅、讨论组、文本渲染、在线文件编辑器、协作图谱(报表)、代码片段分享(Gist)等功能。正因为这些功能所提供的便利,又经过长期的积累,GitHub 的用户活跃度很高,在开源世界里享有深远的声望,并形成了社交化编程文化(Social Coding)。

    209 引用 • 2031 回帖
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 684 关注
  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 153 关注
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 2 关注
  • 运维

    互联网运维工作,以服务为中心,以稳定、安全、高效为三个基本点,确保公司的互联网业务能够 7×24 小时为用户提供高质量的服务。

    148 引用 • 257 回帖 • 1 关注
  • 分享

    有什么新发现就分享给大家吧!

    247 引用 • 1792 回帖 • 7 关注
  • 脑图

    脑图又叫思维导图,是表达发散性思维的有效图形思维工具 ,它简单却又很有效,是一种实用性的思维工具。

    25 引用 • 83 回帖