开发者学堂课程【Java 高级编程:二叉树基础实现】学习笔记,与课程紧密联系,让用户快速学习知识。
课程地址:https://developer.aliyun.com/learning/course/20/detail/364
二叉树基础实现
内容介绍:
1. person 类
2. comparable 使用范例
在实现二叉树的处理之中最为关键性的问题在于数据的保存,而且数据由于牵扯到对象比较的问题,那么一定要有比较器的支持,而这个比较器首选的一定就是Comparable,所以本次将保存一个 Person 类数据
person 类:
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 com pareTo(Person per) {
return this age-per. age;
}
//无参构造、setter、getter略
@override
public string tostring() {return“ 【Person类对象】姓名:”+this.name+“、年龄.”+this. age+“\n”;}
}
随后如果要想进行数据的保存,首先一定需要有一个节点类。节点类里面由于牵扯所以必须使用 comparable(可以区分大小);
package cn. midn. demo;
public class JavaAPIDemo {
public static void main(String[] args) {
BinaryTree<Person> tree = new BinaryTree<Person>();
tree. add(new Person(“小强-80”,80));
tree. add(new Person(“小强-30”,30));
tree. add(new Person(“小强-50”,50));
tree. add(new Person(“小强-60”,60));
tree. add(new Person("小强-90",90));
System. out. println(Arrass. to String(tree. to Array());
}
}
/**
* 实现二叉树操作
* @param<T> 要进行二叉树的实现
*
*/
class BinaryTree<T extends Comparable<T>> {
private class Node{
private Comparable<T>data;//存放Comparable.可以比较大小
private Node parent;_//保存父节点
private Node left;//保存左子树
private Node right;//保存右子树
public Node(Comparable<T> data) {(//构造方法直接负责进行数据的存储
this.data=data;
}
/**
* 实现节点数据的适当位置的存储
* @param newNode 创建的新节点
*/
public void addNode(Node newNode) {
if (newNode.data.compareTo((T)this.data) <=0) {
if (this.left == null) { //现在没有左子树
this.left = newNode; //保存左子树
newNode.parent = this;//保存父节点
} else { //需要向左边继续判断
this.left.addNode(newNode); //继续向下判断
}
} else { //比根节点的数据要大
if (this.right == null) {
this.right = newNode ;//没有右子树
newNode.parent = this ;//保存父节点}
} else {
this.right.addNode(newNode); //继续向下判断
}
}
} /*
*实现所有数据的获取处理,按照中序遍历的形式来完成
*/
public void to ArrayNode() {
if(this. Left ! = null) { //有左子树
this. left.toArrayNode();//递归调用
}
BinaryTree. this.returnData[BinaryTree. this.foot ++] = this.data
if(this. right's null){
this. right.toArrayNode();
}
}
}
//----------以下为二叉树的功能实现------------
private Node root ; //保存的是根节点
private int count;//保存数据个数
private Object [] retuenData;//返回的数据
private int foot = 0;//脚标控制
/**
* 进行数据的保存
* @param data 要保存的数据内容
* @exception NullPointerException 保存数据为空时抛出的异常
*/
public void add(Comparable<T> data ) {
if (data == null) {
throw new NullPointerException(“保存的数据不允许为空!”);
}
// 所有的数据本身不具备有节点关系的匹配,那么一定要将其包装在 Node 类之中
Node newNode = new Node(data);//
保存根节点
if(this.root == null)
{//现在没有根节点,则第一个节点作为根节点
this.root = newNode ;
} else {
//需要为其保存到一个合适的节点
This.root.addNode(newNode);//交友Node类负责处理
}
This.count++;
}
/**
*以对象数组的形式返回全部数据,如果没有数据返回null
*@return全部数据
*
*/
public Object[] toArray() {
if(this. count==0){
return null;
}
This.returnData = new Object[this.count];//保存长度为组长长度
this. foot=0;//脚标清零
this. root.toArrayNode();//直接通过Node类负责
return this.returnDataj//返回全部的数据
}
}
在进行数据添加的时候只是实现了节点关系的保存,而这种关系保存后的结果就是所有数据都属于有序排列。