java【二叉树】

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

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

下面的一个 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 技术具有卓越的通用性、高效性、平台移植性和安全性。

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

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 安装

    你若安好,便是晴天。

    131 引用 • 1184 回帖
  • CSDN

    CSDN (Chinese Software Developer Network) 创立于 1999 年,是中国的 IT 社区和服务平台,为中国的软件开发者和 IT 从业者提供知识传播、职业发展、软件开发等全生命周期服务,满足他们在职业发展中学习及共享知识和信息、建立职业发展社交圈、通过软件开发实现技术商业化等刚性需求。

    14 引用 • 155 回帖
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 563 关注
  • Webswing

    Webswing 是一个能将任何 Swing 应用通过纯 HTML5 运行在浏览器中的 Web 服务器,详细介绍请看 将 Java Swing 应用变成 Web 应用

    1 引用 • 15 回帖 • 623 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    176 引用 • 814 回帖
  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    58 引用 • 22 回帖 • 4 关注
  • Flume

    Flume 是一套分布式的、可靠的,可用于有效地收集、聚合和搬运大量日志数据的服务架构。

    9 引用 • 6 回帖 • 626 关注
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 518 关注
  • FreeMarker

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

    23 引用 • 20 回帖 • 450 关注
  • WebComponents

    Web Components 是 W3C 定义的标准,它给了前端开发者扩展浏览器标签的能力,可以方便地定制可复用组件,更好的进行模块化开发,解放了前端开发者的生产力。

    1 引用 • 1 关注
  • App

    App(应用程序,Application 的缩写)一般指手机软件。

    91 引用 • 383 回帖
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    336 引用 • 641 回帖 • 1 关注
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    5 引用 • 18 回帖 • 157 关注
  • WebClipper

    Web Clipper 是一款浏览器剪藏扩展,它可以帮助你把网页内容剪藏到本地。

    3 引用 • 9 回帖 • 1 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 708 关注
  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖 • 1 关注
  • FlowUs

    FlowUs.息流 个人及团队的新一代生产力工具。

    让复杂的信息管理更轻松、自由、充满创意。

    1 引用 • 5 关注
  • RabbitMQ

    RabbitMQ 是一个开源的 AMQP 实现,服务器端用 Erlang 语言编写,支持多种语言客户端,如:Python、Ruby、.NET、Java、C、PHP、ActionScript 等。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面表现不俗。

    49 引用 • 60 回帖 • 388 关注
  • Scala

    Scala 是一门多范式的编程语言,集成面向对象编程和函数式编程的各种特性。

    13 引用 • 11 回帖 • 115 关注
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 268 回帖 • 84 关注
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 51 关注
  • 负能量

    上帝为你关上了一扇门,然后就去睡觉了....努力不一定能成功,但不努力一定很轻松 (° ー °〃)

    88 引用 • 1234 回帖 • 429 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    124 引用 • 580 回帖 • 1 关注
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统,主要使用于便携设备。2005 年由 Google 收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。

    334 引用 • 323 回帖 • 1 关注
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖 • 1 关注
  • 尊园地产

    昆明尊园房地产经纪有限公司,即:Kunming Zunyuan Property Agency Company Limited(简称“尊园地产”)于 2007 年 6 月开始筹备,2007 年 8 月 18 日正式成立,注册资本 200 万元,公司性质为股份经纪有限公司,主营业务为:代租、代售、代办产权过户、办理银行按揭、担保、抵押、评估等。

    1 引用 • 22 回帖 • 731 关注
  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖