使用Java實(shí)現(xiàn)的二叉樹排序列表
- 二叉樹實(shí)現(xiàn)類
package binarytree.create;
/**
* 二叉樹的實(shí)現(xiàn)類
* @param <T>
*/
public class BinaryTree<T extends Comparable<T>> {
private class Node {
private Comparable<T> data;
private Node parent; // 父節(jié)點(diǎn)
private Node left; // 左子樹
private Node right; // 右子樹
Node(Comparable<T> data){
this.data = data;
}
/**
* 添加節(jié)點(diǎn)
* @param node
*/
public void addNode(Node node) {
if (node.data.compareTo((T) this.data) <= 0) { // 要加入當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)，比當(dāng)前節(jié)點(diǎn)要小
if (this.left == null) {
this.left = node; // 當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)不存在，加入左節(jié)點(diǎn)
node.parent = this; // 保存父節(jié)點(diǎn)
} else {
this.left.addNode(node); // 當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)已經(jīng)存在缺亮，繼續(xù)向下做判斷
}
} else { // 要加入當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)，比當(dāng)前節(jié)點(diǎn)大
if (this.right == null) {
this.right = node; // 加入當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
node.parent = this; // 保存父節(jié)點(diǎn)
} else {
this.right.addNode(node); // 當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)已存在劫侧，繼續(xù)向下做判斷
}
}
}
/**
* 實(shí)現(xiàn)所有數(shù)據(jù)的獲取處理，按照中序遍歷的處理(按照二叉樹的分布烧栋，左子樹<根節(jié)點(diǎn)<右子樹写妥，由小到大的排序獲取)
*/
public void toArrayNode() {
if (this.left != null) {
this.left.toArrayNode(); // 遞歸調(diào)用獲取值
}
BinaryTree.this.returnData[BinaryTree.this.foot++] = this.data;
if (this.right != null) {
this.right.toArrayNode();
}
}
}
// ----------------------- 以下為二叉樹的實(shí)現(xiàn) -----------------------
// 根節(jié)點(diǎn)
private Node root;
// 統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)
private int count;
// 腳標(biāo)
private int foot;
// 返回?cái)?shù)據(jù)
private Object[] returnData;
/**
* @NullPointerException 當(dāng)傳入的數(shù)據(jù)對(duì)象為null時(shí)拋出空指針異常
* @param data
*/
public void add(Comparable<T> data) {
if (data == null) {
throw new NullPointerException("添加的數(shù)據(jù)為空");
} else {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
} else { // 加入一個(gè)合適的節(jié)點(diǎn)
root.addNode(newNode);
}
}
this.count++;
}
/**
* 獲取返回值
* 如果當(dāng)前的二叉樹長度為0珍特，直接返回null
* @return
*/
public Object[] returnArrayData(){
if (this.count == 0) {
return null;
}
returnData = new Object[this.count]; // 有多少個(gè)節(jié)點(diǎn)就創(chuàng)建多少個(gè)長度的對(duì)象
this.root.toArrayNode(); // 直接通過Node類負(fù)責(zé)
this.foot = 0; // 腳標(biāo)清0
return this.returnData;
}
}
- 實(shí)體類
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; // 當(dāng)前對(duì)象大于比較對(duì)象時(shí)為1邑跪，當(dāng)前對(duì)象小于比較對(duì)象為負(fù)數(shù)，相等為0(正序排序)
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
- 測(cè)試類
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()));
}
}
- 輸出結(jié)果
[Person{name='李四', age=10}, Person{name='張三', age=20}, Person{name='小趙', age=30}, Person{name='王五', age=50}]
