使用Java实现的二叉树排序列表
- 二叉树实现类
package binarytree.create;
/**
* 二叉树的实现类
* @param <T>
*/
public class BinaryTree<T extends Comparable<T>> {
private class Node {
private Comparable<T> data;
private Node parent; // 父节点
private Node left; // 左子树
private Node right; // 右子树
Node(Comparable<T> data){
this.data = data;
}
/**
* 添加节点
* @param node
*/
public void addNode(Node node) {
if (node.data.compareTo((T) this.data) <= 0) { // 要加入当前节点的节点,比当前节点要小
if (this.left == null) {
this.left = node; // 当前节点的左节点不存在,加入左节点
node.parent = this; // 保存父节点
} else {
this.left.addNode(node); // 当前节点的左节点已经存在,继续向下做判断
}
} else { // 要加入当前节点的节点,比当前节点大
if (this.right == null) {
this.right = node; // 加入当前节点的右节点
node.parent = this; // 保存父节点
} else {
this.right.addNode(node); // 当前节点的右节点已存在,继续向下做判断
}
}
}
/**
* 实现所有数据的获取处理,按照中序遍历的处理(按照二叉树的分布,左子树<根节点<右子树,由小到大的排序获取)
*/
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 int foot;
// 返回数据
private Object[] returnData;
/**
* @NullPointerException 当传入的数据对象为null时抛出空指针异常
* @param data
*/
public void add(Comparable<T> data) {
if (data == null) {
throw new NullPointerException("添加的数据为空");
} else {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
} else { // 加入一个合适的节点
root.addNode(newNode);
}
}
this.count++;
}
/**
* 获取返回值
* 如果当前的二叉树长度为0,直接返回null
* @return
*/
public Object[] returnArrayData(){
if (this.count == 0) {
return null;
}
returnData = new Object[this.count]; // 有多少个节点就创建多少个长度的对象
this.root.toArrayNode(); // 直接通过Node类负责
this.foot = 0; // 脚标清0
return this.returnData;
}
}
- 实体类
package binarytree.create.entity;
public class Person implements Comparable<Person> {
private String name;
private Integer age;
public Person(String name, Integer age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public int compareTo(Person o) {
return this.age - o.age; // 当前对象大于比较对象时为1,当前对象小于比较对象为负数,相等为0(正序排序)
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
- 测试类
package binarytree.create;
import binarytree.create.entity.Person;
import java.util.Arrays;
public class BinaryTreeTest{
public static void main(String[] args) {
BinaryTree<Person> tree = new BinaryTree<Person>();
tree.add(new Person("张三",20));
tree.add(new Person("李四",10));
tree.add(new Person("王五",50));
tree.add(new Person("赵六",30));
System.out.println(Arrays.toString(tree.returnArrayData()));
}
}
- 输出结果
[Person{name='李四', age=10}, Person{name='张三', age=20}, Person{name='小赵', age=30}, Person{name='王五', age=50}]
网友评论