Java-比较器、二叉树

比较使用:Arrays.sort()

一、比较器

对象数组进行排序,必须有一个排序规则,要使用比较器Comparable完成。

public interface Comparable<T> {
    public int compareTo(T o);
}

根据Java文档,要排序的数组所在的类一定要实现Comparable接口,此接口返回的是int型数据,而用户覆写此方法的时候只需返回三种结果。1(>0),-1(<0),0(=0)。

package com.joeaaa.demo14;

import java.util.Arrays;

/*
* 定义Person类,实现比较器,比较对象数组的大小。
*/
class Person implements Comparable<Person>{
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}'+'\n';
    }

    @Override
    public int compareTo(Person o) { // 定义比较器
        if (this.age > o.age){ // 定义比较规则
            return 1;
        }else if (this.age < o.age){
            return -1;
        }else {
            return 0;
        }
    }
}
public class ComparableTest {
    public static void main(String[] args) {
        Person person[] = new Person[]{
                new Person("Alex",20),
                new Person("Joe",29),
                new Person("Winda",18),
                new Person("Val",21)};
        Arrays.sort(person); // 对person数组进行排序
        System.out.println(Arrays.toString(person));
    }
}
[Person{name='Winda', age=18}
 , Person{name='Alex', age=20}
 , Person{name='Val', age=21}
 , Person{name='Joe', age=29}
 ]

二、Binary Tree,二叉树

二叉树是一种排序的基本数据结构。二叉树的基本原理 :

  1. 取第一个元素作为根节点,之后每一个元素的排列按要求:
  2. 如果比根节点小的数据,放在左子树;比根节点大的数据放在右子树;
  3. 输出时采用中序遍历(左->中/根->右)
package com.joeaaa.demo14;
/*
* 使用二叉树进行排序
*/

class Student implements Comparable<Student> {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}' + '\n';
    }

    @Override
    public int compareTo(Student o) { // 定义比较器
        if (this.age > o.age){ // 定义比较规则
            return -1;
        }else if (this.age < o.age){
            return 1;
        }else {
            return 0;
        }
    }
}

class BinaryTree{
    private class Node{
        private Comparable data;
        private Node left;
        private Node right;

        public Node(Comparable data){
            this.data = data;
        }

        public void addNode(Node newNode){
            if(this.data.compareTo(newNode.data) < 0){
                if(this.left == null){ // 没有左子树
                    this.left = newNode;
                }else {
                    this.left.addNode(newNode);
                }
            }else {
                if(this.right == null){
                    this.right = newNode;
                }else {
                    this.right.addNode(newNode);
                }
            }
        }

        // 节点输出 左中右
        public void printNode(){
            if (this.left != null){
                this.left.printNode();
            }
            System.out.println(this.data);
            if (this.right != null){
                this.right.printNode();
            }
        }
    }

    private Node root; // 根节点

    public void add(Student data){
        if(data == null){
            return; // 返回调用处
        }
        Node newNode = new Node(data); // 将数据封装为节点
        if(this.root == null){
            this.root = newNode; // 没有根节点,进行设置
        }else { // 保存到合适位置
            this.root.addNode(newNode);
        }
    }

    public void print(){
        if(this.root != null){
            this.root.printNode();
        }
    }
}

public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.add(new Student("Alex",20));
        tree.add(new Student("Joe",29));
        tree.add(new Student("Winda",18));
        tree.add(new Student("Val",21));
        tree.print();
    }
}
Student{name='Winda', age=18}
Student{name='Alex', age=20}
Student{name='Val', age=21}
Student{name='Joe', age=29}

Comparable 比较逻辑优化

@Override
    public int compareTo(Student o) { // 定义比较器
        if (this.age > o.age){ // 定义比较规则
            return -1;
        }else if (this.age < o.age){
            return 1;
        }else {
            return 0;
        }
    }
@Override
    public int compareTo(Student o) { // 定义比较器
        return Integer.compare(o.age, this.age); // 定义比较规则
    }

请解释Comparable与Comparator的区别

  1. java.util.Comparator是需要单独定义一个比较的规范类,里面有两个方法:compare()、equals();
  2. java.lang.Comparable是在一个类定义时,默认实现好的接口,里面只有一个compareTo()方法/。。