java【二叉树】

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

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

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

    3203 引用 • 8217 回帖
  • 二叉树
    8 引用 • 1 回帖
  • 数据结构
    87 引用 • 115 回帖 • 4 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1340 回帖
  • 电影

    这是一个不能说的秘密。

    123 引用 • 608 回帖
  • OkHttp

    OkHttp 是一款 HTTP & HTTP/2 客户端库,专为 Android 和 Java 应用打造。

    16 引用 • 6 回帖 • 94 关注
  • Redis

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

    284 引用 • 248 回帖
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    117 引用 • 99 回帖 • 203 关注
  • CodeMirror
    2 引用 • 17 回帖 • 176 关注
  • Excel
    31 引用 • 28 回帖
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 12 关注
  • Love2D

    Love2D 是一个开源的, 跨平台的 2D 游戏引擎。使用纯 Lua 脚本来进行游戏开发。目前支持的平台有 Windows, Mac OS X, Linux, Android 和 iOS。

    14 引用 • 53 回帖 • 563 关注
  • Bug

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

    76 引用 • 1742 回帖
  • Follow
    4 引用 • 12 回帖 • 10 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    6 引用 • 143 回帖 • 1 关注
  • RYMCU

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

    4 引用 • 6 回帖 • 64 关注
  • GraphQL

    GraphQL 是一个用于 API 的查询语言,是一个使用基于类型系统来执行查询的服务端运行时(类型系统由你的数据定义)。GraphQL 并没有和任何特定数据库或者存储引擎绑定,而是依靠你现有的代码和数据支撑。

    4 引用 • 3 回帖 • 5 关注
  • 互联网

    互联网(Internet),又称网际网络,或音译因特网、英特网。互联网始于 1969 年美国的阿帕网,是网络与网络之间所串连成的庞大网络,这些网络以一组通用的协议相连,形成逻辑上的单一巨大国际网络。

    98 引用 • 367 回帖
  • 浅吟主题

    Jeffrey Chen 制作的思源笔记主题,项目仓库:https://github.com/TCOTC/Whisper

    2 引用 • 32 回帖
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1708 回帖 • 1 关注
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    91 引用 • 59 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 184 关注
  • Postman

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

    4 引用 • 3 回帖 • 3 关注
  • 书籍

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

    84 引用 • 414 回帖
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 612 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 33 关注
  • GitLab

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

    46 引用 • 72 回帖 • 2 关注
  • 设计模式

    设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    201 引用 • 120 回帖
  • SQLServer

    SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。

    21 引用 • 31 回帖 • 1 关注
  • Kubernetes

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

    118 引用 • 54 回帖 • 11 关注