Java比较器(三) 利用二叉树链表进行对象数组排序

Java比较器(三) 利用二叉树链表进行对象数组排序

二叉树：一个节点有左右两个子节点，左节点比中节点小，右节点比中节点大

和单链表结构大同小异，无非就是将单链表中的next节点换成了left、right两个节点。

单链表结构

创建一个简单的二叉树链表模型：

//实现二叉树模型
public class BinaryTree {
    private class Note {
        private Note left;//左节点数据
        private Note right;//右节点数据
        //实现二叉树排序的主要过程是利用Comparable子类对象中的compareTo方法进行排序，故存储的所有对象都应该是Comparable子类对象
        private Comparable data;

        public Note(Comparable com) {
            this.data = com;
        }

        public void addNote(Comparable com) {
            if (this.data.compareTo(com) > 0)//利用compareTo()判断新增的对象和当前对象的大小顺序，如果比当前对象小则插入left，反之插入right
            {
                //插入left节点
                if (this.left == null) {
                    this.left = new Note(com);
                } else {
                    this.left.addNote(com);
                }
            } else {
                //插入right节点
                if (this.right == null) {
                    this.right = new Note(com);
                } else {
                    this.right.addNote(com);
                }
            }
        }

        public void toArray()
        {
            if(this.left!=null)
            {
                this.left.toArray();
            }
            BinaryTree.this.array[BinaryTree.this.foot++]=this.data;
            if(this.right!=null)
            {
                this.right.toArray();
            }
        }
    }

    //----------------------以上为内部类----------------------------------
    private Note root;
    private int count;
    private Comparable[] array;
    private int foot;//定义角标

    public void add(Comparable com) {
        if (com == null) {
            return;
        }
        if (root == null) {
            root = new Note(com);
        } else {
            this.root.addNote(com);
        }
        this.count++;
    }

    public int size() {
        return this.count;
    }

    //获取数组对象
    public Comparable[] toArray() {
        if (this.count == 0) {
            return null;
        }
        this.array=new Comparable[this.count];
        this.foot=0;
        this.root.toArray();
        return this.array;
    }
}

因为要进行比较，所以链表中只能接收Comoarable接口的子类。利用子类覆写的comparTo(）方法进行比较。判断对象存储的节点位置。

测试Book类，实现Comparable接口，并覆写compareTo()方法

class Book implements Comparable {
    private String title;
    private double price;

    public void setPrice(int price) {
        this.price = price;
    }

    public double getPrice() {
        return price;
    }

    public void setTitle(String title) {
        this.title = title;
    }

    public String getTitle() {
        return title;
    }

    public Book(String title, double price) {
        this.title = title;
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book{" +
                "title='" + title + ''' +
                ", price=" + price +
                '}';
    }

    @Override
    public int compareTo(Book o) {
        if (this.price > o.price) {
            return 1;
        } else if (this.price < o.price) {
            return -1;
        } else {
            return 0;
        }
    }
}

测试实例：

public class Test {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.add(new Book("Java开发",566.2));
        bt.add(new Book("Jav开发",56.2));
        bt.add(new Book("Ja开发",166.2));
        bt.add(new Book("J开发",2336.2));
        System.out.println(bt.size());
        System.out.println(Arrays.toString(bt.toArray()));

    }
}

运行结果：

[Book{title='Jav开发', price=56.2},

Book{title='Ja开发', price=166.2},

Book{title='Java开发', price=566.2},

Book{title='J开发', price=2336.2}]