上一篇文章为大家带来了一个关于链表的结构实现，我采用是内部类实现方式，那对于链表而言的话，链表缺点就是检索数据，那当然有人会提出一些优化方法，例如我们在学习集合时候了解到，二叉树，红黑树等，在数据改变的情况，进行对数据旋转，达到一个树的左右平衡，以此达到一个最佳的数据检索到效率。
下面的一个 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); } } }
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于