Java学习路线-23：比较器Comparable、Comparator、二叉树

第13 章 ： 比较器 52 比较器问题引出

比较器：大小关系判断

示例：对象数组排序

Integer[] data = new Integer[]{1, 4, 5, 8, 6};
Arrays.sort(data);
System.out.println(Arrays.toString(data));
// [1, 4, 5, 6, 8]

53 Comparable比较器

接口：Comparable

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

大于返回正数 等于返回0 小于返回负数

示例：自定义类型数组排序

import java.util.Arrays;

class Person implements Comparable{
    private String name ;
    private int age ;

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

    @Override
    public int compareTo(Person other) {
        return this.age - other.age;
    }

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


class Demo {
    public static void main(String[] args) {
        Person[] data = {
                new Person("小王", 23),
                new Person("小刘", 27),
                new Person("小张", 25),
        };

        Arrays.sort(data);
        System.out.println(Arrays.toString(data));
        // [
        // Person{name='小王', age=23}, 
        // Person{name='小张', age=25}, 
        // Person{name='小刘', age=27}
        // ]
    }
}

54 Comparator比较器

解决没有实现Comparable接口的对象比较

@FunctionalInterface
public interface Comparator {
    int compare(T o1, T o2);
}

排序方法

import java.util.Arrays;

public static void sort(Object[] a)

public static  void sort(T[] a, Comparator c)

使用示例

import java.util.Arrays;
import java.util.Comparator;

class Person{
    private String name ;
    private int age ;

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

    public int getAge() {
        return age;
    }

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

class PersonComparator implements Comparator {
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getAge() - person2.getAge();
    }
}

class Demo {
    public static void main(String[] args) {
        Person[] data = {
                new Person("小王", 23),
                new Person("小刘", 27),
                new Person("小张", 25),
        };

        Arrays.sort(data, new PersonComparator());
        System.out.println(Arrays.toString(data));
        // [
        // Person{name='小王', age=23},
        // Person{name='小张', age=25},
        // Person{name='小刘', age=27}
        // ]
    }
}

Comparable优先使用

区别 Comparable Comparator Comparable 定义类的时候实现父接口，定义排序规则

public int compareTo(T o)

Comparator 挽救的比较器操作，需要单独设置比较规则实现排序

int compare(T o1, T o2);

可以使用匿名类

Arrays.sort(data, new Comparator() {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getAge() - o2.getAge();
    }
});

也可以使用Lambda表达式

Comparator comparator = (Person o1, Person o2)->{
    return o1.getAge() - o2.getAge();
};

Arrays.sort(data, comparator);

或者

Arrays.sort(data, (p1, p2)->{
            return p1.getAge() - p2.getAge();
        });

55 二叉树结构简介

链表的时间复杂度是O(n) 二叉树查找的时间复杂度是O(logn)

数据位置

         父节点-中  

左子树-小          右子树-大

遍历数据 1、前序遍历 根-左-右 2、中序遍历 左-根-右 3、后序遍历 左-右-根

56 二叉树基础实现

import java.util.Arrays;

class Person implements Comparable {
    private String name;
    private int age;

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

    public int getAge() {
        return age;
    }

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

    @Override
    public int compareTo(Person other) {
        return this.age - other.age;
    }
}

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

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

        public void addNode(Node node) {
            // 数据比当前节点小，添加到左子树
            if (node.data.compareTo((T) this.data)