美文网首页
二叉树实现排序列表

二叉树实现排序列表

作者: P_ursuit | 来源:发表于2018-07-03 17:23 被阅读0次

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

    相关文章

      网友评论

          本文标题:二叉树实现排序列表

          本文链接:https://www.haomeiwen.com/subject/iysjuftx.html