上一篇：初识二叉树，领悟树的概念 | 带你学《Java语言高级特性》之三十八
二叉树可以优化查找效率的关键原因在于其特殊的数据保存方式，在保存时就借助比较器提前完成数据的有序摆放。本节将结合具体案例讲解实现二叉树数据保存的方法。
【本节目标】
通过阅读本节内容，你将了解到二叉树保存数据的方式，并能够复习之前所学的比较器相关内容，借助比较器实现二叉树特殊的数据保存功能。
在实现二叉树的处理之中最为关键的问题在于数据的保存，而且数据由于牵扯到对象比较的问题，那么一定要有比较器的支持，而这个比较器首选一定是Comparable，所以本次将保存一个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 String toString() {
return "【Person类对象】姓名：" + this.name + "、年龄：" + this.age + "\n";
}
@Override
public int compareTo(Person per) {
return this.age-per.age;//升序
}
}随后如果要想进行数据的保存，首先一定要有一个节点类。节点类中由于牵扯到数据保存问题，所以必须使用Comparable（可以区分大小）；
import java.util.Arrays;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception{
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(Arrays.toString(tree.toArray()));
}
}
/**
* 实现二叉树操作
* @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 创建的新节点
* @throws IllegalArgumentException 保存的数据已存在
*/
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 toArrayNode() {
if(this.left!=null){ //有左子树
this.left.toArrayNode(); //递归调用
}
BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
if(this.right!=null){
this.right.toArrayNode();
}
}
}
//-------------------以下为二叉树的功能实现--------------
private Node root; //保存根节点
private int count; //保存数据个数
private Object[] returnData; //返回的数据
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.returnData; //返回全部的数据
}
}
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 String toString() {
return "【Person类对象】姓名：" + this.name + "、年龄：" + this.age +"\n";
}
@Override
public int compareTo(Person person) {
return this.age-person.age;//升序
}
}执行结果：
[【Person类对象】姓名：小强-30、年龄：30
, 【Person类对象】姓名：小强-50、年龄：50
, 【Person类对象】姓名：小强-60、年龄：60
, 【Person类对象】姓名：小强-80、年龄：80
, 【Person类对象】姓名：小强-90、年龄：90
]
在进行数据添加的时候只是实现了节点关系的保存，而这种关系的保存后的结果就是所有的数据都属于有序排列。
想学习更多的Java的课程吗？从小白到大神，从入门到精通，更多精彩不容错过！免费为您提供更多的学习资源。
本内容视频来源于阿里云大学
