二叉树实现排序列表

使用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}]