java【二叉树】

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

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

下面的一个 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 回帖 • 1 关注
  • 二叉树
    8 引用 • 1 回帖
  • 数据结构
    88 引用 • 115 回帖 • 4 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    7489 引用 • 34059 回帖 • 198 关注
  • OnlyOffice
    4 引用 • 7 关注
  • 单点登录

    单点登录(Single Sign On)是目前比较流行的企业业务整合的解决方案之一。SSO 的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

    9 引用 • 25 回帖 • 1 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 721 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4599 回帖 • 700 关注
  • 资讯

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

    54 引用 • 85 回帖 • 4 关注
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 389 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 608 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 28 关注
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 340 关注
  • Maven

    Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。

    186 引用 • 318 回帖 • 325 关注
  • abitmean

    有点意思就行了

    34 关注
  • 创业

    你比 99% 的人都优秀么?

    83 引用 • 1398 回帖 • 1 关注
  • Swagger

    Swagger 是一款非常流行的 API 开发工具,它遵循 OpenAPI Specification(这是一种通用的、和编程语言无关的 API 描述规范)。Swagger 贯穿整个 API 生命周期,如 API 的设计、编写文档、测试和部署。

    26 引用 • 35 回帖 • 3 关注
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 1 关注
  • Shell

    Shell 脚本与 Windows/Dos 下的批处理相似,也就是用各类命令预先放入到一个文件中,方便一次性执行的一个程序文件,主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大,比用其他编程程序编辑的程序效率更高,因为它使用了 Linux/Unix 下的命令。

    122 引用 • 73 回帖
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 730 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    5 引用 • 13 回帖
  • 书籍

    宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”

    77 引用 • 390 回帖
  • NetBeans

    NetBeans 是一个始于 1997 年的 Xelfi 计划,本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE,直到 1999 年 Sun 买下此公司。Sun 于次年(2000 年)六月将 NetBeans IDE 开源,直到现在 NetBeans 的社群依然持续增长。

    78 引用 • 102 回帖 • 663 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    10 引用 • 32 回帖 • 107 关注
  • Lute

    Lute 是一款结构化的 Markdown 引擎,支持 Go 和 JavaScript。

    25 引用 • 191 回帖 • 20 关注
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖
    用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力:

    • 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
    • 自我保护:使用适当的 License 保护自己的原创作品。
    • 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
    • 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
    • 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
    • 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖
  • Notion

    Notion - The all-in-one workspace for your notes, tasks, wikis, and databases.

    5 引用 • 26 回帖
  • HBase

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

    17 引用 • 6 回帖 • 70 关注
  • 电影

    这是一个不能说的秘密。

    120 引用 • 598 回帖