[Java知识库]泛型、Set集合、TreeSet集合、二叉树

泛型

Set

TreeSet

01. 泛型-概述

泛型的作用?
 ? ?是JDK5中引入的新特性, 它提供了编译时对类型安全检测机制
 ? ?
泛型好处?
 ?  1. 把运行时可能出现的问题提前到了编译期间
 ?  2. 避免了强制类型转换

public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?ArrayList list = new ArrayList();
 ? ? ? ? ? ?list.add("aaa");
 ? ? ? ? ? ?list.add("bbb");
 ? ? ? ? ? ?list.add("ccc");
 ? ? ? ? ? ?list.add(123);
?
 ? ? ? ? ? ?Iterator it = list.iterator();
 ? ? ? ? ? ?while (it.hasNext()) {
 ? ? ? ? ? ? ? ?//Object next = it.next();
 ? ? ? ? ? ? ? ?//int length = next.length(); //Object类没有length方法
?
 ? ? ? ? ? ? ? ?//强转
 ? ? ? ? ? ? ? ?String next = (String) it.next();
 ? ? ? ? ? ? ? ?/*
 ? ? ? ? ? ? ? ? ? ?如果元素中除了String还有其他数据类型,就会报转换异常:
 ? ? ? ? ? ? ? ? ? ? ? ?java.lang.ClassCastException
 ? ? ? ? ? ? ? ? */
 ? ? ? ? ? ? ? ?System.out.println(next);
 ? ? ? ? ?  }
 ? ? ?  }
 ?  }

02 . 泛型类的使用

泛型可以使用的地方
 ? ?1.类后面: 泛型类
 ? ?2.方法后面: 泛型方法
 ? ?3.接口后面: 泛型接口
?
了解
 ? ?我们常见的泛型类有ArrayList
 ? ?ArrayList在JDK4之前, 没有泛型, 这样会有弊端 (强转时会有异常、为了解决弊端增加了代码量)
 ? ?为了解决这些弊端, JDK5后ArrayList被设计为泛型类
 ? ?泛型代表未知的类型, 这个类型在创建对象时可以被确定
?
注意
 ? ?如果一个类后面有<E>, 表示这是一个泛型类
 ? ?创建泛型类对象时, 必须给这个泛型确定具体的数据类型 ?

03. 泛型-自定义泛型类

泛型类的定义格式
 ? ?<类型>: 指定一种类型的格式
 ? ?尖括号中任意写, 按照变量的定义规则即可, 一般写一个大写字母
 ? ?例如<E>、<T>、<Q>、<M>
?
 ? ?<类型1,类型2>: 指定多种类型的格式
 ? ?多种类型之间用逗号隔开
 ? ?例如<E,T>、<Q,M>、<K,V>
?
?
泛型类的定义格式
 ? ?修饰符 class 类名<类型>{}?

//测试类
 ? ?class Test{
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?//创建对象,指定类型
 ? ? ? ? ? ?Box<String> box = new Box<>();
 ? ? ? ? ? ?box.setElement("给女神表白的代码");
 ? ? ? ? ? ?System.out.println(box.getElement());
?
 ? ? ? ? ? ?//创建对象,指定类型
 ? ? ? ? ? ?Box<Integer> box2 = new Box<>();
 ? ? ? ? ? ?box2.setElement(18);
 ? ? ? ? ? ?System.out.println(box2.getElement());
 ? ? ?  }
 ?  }
 ? ?//自定义泛型类
 ? ?public class Box<T> {
 ? ? ? ?//成员变量,类型为泛型
 ? ? ? ?private T element;
?
 ? ? ? ?//提供getXxx和setXxx方法
 ? ? ? ?public T getElement() {
 ? ? ? ? ? ?return element;
 ? ? ?  }
?
 ? ? ? ?public void setElement(T element) {
 ? ? ? ? ? ?this.element = element;
 ? ? ?  }
 ?  }

04. 泛型-泛型方法的使用

Java中泛型方法的使用
 ? ?查阅API我们发现ArrayList有两个方法
 ? ? ? ?1. Object oArray(); 返回集合的数组表现形式
 ? ? ? ?2. <T> T[] toArray(T[] arr); 返回集合的指定类型数组的表现形式

代码示例?

public class Demo {
 ? ?public static void main(String[] args) {
 ? ? ? ?ArrayList<String> list = new ArrayList<>();
 ? ? ? ?list.add("张三");
 ? ? ? ?list.add("李四");
 ? ? ? ?list.add("王五");
?
 ? ? ? ?//1. Object toArray(); 返回集合的数组表现形式
 ? ? ? ?Object[] objects = list.toArray();
 ? ? ? ?System.out.println(Arrays.toString(objects)); //获取的类型都是Object类型,如果要调用方法不方便
?
 ? ? ? ?//2. <T> T[] toArray(T[] arr); 返回集合的指定类型数组的表现形式
 ? ? ? ?String[] strings = list.toArray(new String[list.size()]);
 ? ? ? ?System.out.println(Arrays.toString(strings)); //此时获取的元素都是String类型
 ?  }
}

05. 泛型-自定义泛型方法

泛型方法的定义格式
 ? ?修饰符 <类型> 返回值类型 方法名(类型 变量名)
 ? ?例如public<T> void show(T t){}
?
需求:
 ? ?定义一个方法, 接收一个集合和四个元素(数据类型调用者指定)
 ? ?将元素添加到集合并返回

代码示例?

public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?//测试1: 元素为String类型
 ? ? ? ? ? ?ArrayList<String> list1 = addElement(new ArrayList<String>(), "张飞", "刘备", "关羽", "赵云");
 ? ? ? ? ? ?System.out.println(list1);
?
 ? ? ? ? ? ?//测试2: 元素为int类型
 ? ? ? ? ? ?ArrayList<Integer> list2 = addElement(new ArrayList<Integer>(), 11, 22, 33, 44);
 ? ? ? ? ? ?System.out.println(list2);
 ? ? ?  }
?
 ? ? ? ?//修饰符 <类型> 返回值类型 方法名(类型 变量名)
 ? ? ? ?public static <T> ArrayList<T> addElement(ArrayList<T> list, T t1, T t2, T t3, T t4) {
 ? ? ? ? ? ?list.add(t1);
 ? ? ? ? ? ?list.add(t2);
 ? ? ? ? ? ?list.add(t3);
 ? ? ? ? ? ?list.add(t4);
 ? ? ? ? ? ?return list;
 ? ? ?  }
 ?  }

06. 泛型-泛型接口

Java中的泛型接口举例?
    public interface List<E> extends Eollection<E>..
使用者是ArrayList, 将该泛型延续下来(方式1)
    public class ArrayList<E> extends AbstractList<E>
 ? ? ? ?implements List<E>, RandomAccess, Cloneable, java.io.Serializable..
    
泛型接口的使用方式?
    方式1. 实现类不给泛型, 将实现类也定义为泛型类, 创建实现类对象时才确定具体的数据类型
    方式2. 实现类确定具体的数据类型
    
泛型接口的定义格式?
    修饰符 interface 接口名<T>{}

代码示例??

 ? ?//测试类
 ? ?public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?//测试方式1: 创建实现类对象时要确定具体的数据类型
 ? ? ? ? ? ?InterImpl1<String> i1 = new InterImpl1<>();
 ? ? ? ? ? ?i1.method("黑马程序员");
?
 ? ? ? ? ? ?//测试方式2: 由于类型已经确定, 直接创建实现类对象即可, 不需要确定具体的数据类型
 ? ? ? ? ? ?InterImpl2 i2 = new InterImpl2();
 ? ? ? ? ? ?i2.method(100);
 ? ? ?  }
 ?  }
?
 ? ?//自定义泛型接口
 ? ?interface inter<T> {
 ? ? ? ?public abstract void method(T t);
 ?  }
?
 ? ?//方式1. 实现类不给泛型, 将实现类也定义为泛型类, 创建实现类对象时才确定具体的数据类型
 ? ?class InterImpl1<T> implements inter<T> {
 ? ? ? ?@Override
 ? ? ? ?public void method(T t) {
 ? ? ? ? ? ?System.out.println(t);
 ? ? ?  }
 ?  }
?
 ? ?//方式2. 实现类确定具体的数据类型
 ? ?class InterImpl2 implements inter<Integer>{
 ? ? ? ?@Override
 ? ? ? ?public void method(Integer integer) {
 ? ? ? ? ? ?System.out.println(integer);
 ? ? ?  }
 ?  }
 ? ?

07. 泛型-通配符

类型通配符: <?>
?
ArrayList<?>: 表示元素类型未知的ArrayList集合, 它的元素可以匹配任何类型
?
类型通配符上限: <? extends 类型>
 ? ?ArrayList<? extends Number>: 表示类型是Number或者Number的子类
 ? ?
类型通配符下限: <? super 类型>
 ? ?ArrayList<? super Number>: 表示类型是Number或者Number的父类

代码示例??

public class Demo {
 ? ?public static void main(String[] args) {
 ? ? ? ?/*
 ? ? ? ? ? ?Integer 继承自 Number 继承自 Object
 ? ? ? ? */
 ? ? ? ?//类型是任意类型
 ? ? ? ?method01(new ArrayList<Integer>());
 ? ? ? ?method01(new ArrayList<Number>());
 ? ? ? ?method01(new ArrayList<Object>());
?
 ? ? ? ?//类型是Number或者Number的子类
 ? ? ? ?method02(new ArrayList<Integer>());
 ? ? ? ?method02(new ArrayList<Number>());
 ? ? ? ?//method02(new ArrayList<Object>()); //如果传递Number的父类型,报错
?
 ? ? ? ?//类型是Number或者Number的父类
 ? ? ? ?//method03(new ArrayList<Integer>()); //如果传递Number的子类型,报错
 ? ? ? ?method03(new ArrayList<Number>());
 ? ? ? ?method03(new ArrayList<Object>());
 ?  }
?
 ? ?//类型是任意类型
 ? ?public static void method01(ArrayList<?> list) {
 ?  }
 ? ?//类型是Number或者Number的子类
 ? ?public static void method02(ArrayList<? extends Number> list) {
 ?  }
 ? ?//类型是Number或者Number的父类
 ? ?public static void method03(ArrayList<? super Number> list) {
 ?  }
}

08. Set-概述

单列集合 
Collection接口 

????????List接口(可重复) 

????????????????ArrayList实现类 LinkedList实现类 

Set接口(不可重复) ? 

????????TreeSet实现类 ? HashSet实现类

09. Set-基本使用

Set集合特点
    1. 可以去重
    2. 存取顺序不一致
    3. 没有带索引的方法, 所以不能用普通for遍历, 也不能通过索引获取/删除元素
    
Set集合练习
    存储字符串并遍历

代码示例??

 ? ?public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?Set<String> set = new TreeSet<>();
 ? ? ? ? ? ?set.add("cc");
 ? ? ? ? ? ?set.add("dd");
 ? ? ? ? ? ?set.add("aa");
 ? ? ? ? ? ?set.add("aa");
 ? ? ? ? ? ?set.add("bb");
 ? ? ? ? ? ?set.add("bb");
?
 ? ? ? ? ? ?//遍历1:普通for不行
 ? ? ? ? ? ?//for (int i = 0; i < set.size(); i++) {
 ? ? ? ? ? ? ? ?//System.out.println(set.get(i)); //没有操作索引的方法
 ? ? ? ? ? ?//}
?
 ? ? ? ? ? ?//遍历2:迭代器
 ? ? ? ? ? ?Iterator<String> it = set.iterator();
 ? ? ? ? ? ?while (it.hasNext()){
 ? ? ? ? ? ? ? ?System.out.println(it.next());
 ? ? ? ? ?  }
?
 ? ? ? ? ? ?System.out.println("-----------");
?
 ? ? ? ? ? ?//遍历3:增强for
 ? ? ? ? ? ?for (String s : set) {
 ? ? ? ? ? ? ? ?System.out.println(s);
 ? ? ? ? ?  }
 ? ? ?  }
 ?  }
 ? ?

10. TreeSet-基本使用

TreeSet集合特点
    1. 可以去重
    2. 存取顺序不一致
    3. 可以将元素按照规则进行排序 (重点关注)
 ? ?
TreeSet集合练习1
 ? ?存储Integer类型的整数并遍历 (虽然存取顺序不一致,但是有序)
TreeSet集合练习2
 ? ?存储Student对象并遍历 (报错, 原因是没有规定排序规则)

代码示例??

public class Demo {
 ? ? ? ?public static void main(String[] args) {
            
 ? ? ?  }
?
 ? ? ? ?//TreeSet集合练习2
 ? ? ? ?private static void test02() {
 ? ? ? ? ? ?//存储Student对象并遍历
 ? ? ? ? ? ?TreeSet<Student> set = new TreeSet<>();
 ? ? ? ? ? ?set.add(new Student("张飞",18));
 ? ? ? ? ? ?set.add(new Student("关羽",19));
 ? ? ? ? ? ?set.add(new Student("刘备",20));
 ? ? ? ? ? ?System.out.println(set); //报错, 原因是没有规定排序规则
 ? ? ?  }
?
 ? ? ? ?//TreeSet集合练习1
 ? ? ? ?private static void test01() {
 ? ? ? ? ? ?//存储Integer类型的整数并遍历
 ? ? ? ? ? ?TreeSet<Integer> set = new TreeSet<>();
 ? ? ? ? ? ?set.add(5);
 ? ? ? ? ? ?set.add(3);
 ? ? ? ? ? ?set.add(4);
 ? ? ? ? ? ?set.add(1);
 ? ? ? ? ? ?set.add(2);
 ? ? ? ? ? ?System.out.println(set); //[1, 2, 3, 4, 5] 虽然存取顺序不一致,但是有序
 ? ? ?  }
 ?  }
 ? ?

11. TreeSet-自然排序Comparable的使用

Comparable接口API介绍
    该接口对它每个实现类强加一个整体排序, 这个排序被称为"自然排序"
    类的compareTo方法被称为"自然排序方法"
?
自然排序Comparable的使用步骤
    1. 使用空参构造TreeSet集合
    2. 自定义类要实现Comparable接口
    3. 重写Comparable接口中的compareTo方法

代码示例??

 ? ?public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?//1. 使用空参构造TreeSet集合
 ? ? ? ? ? ?TreeSet<Student> set = new TreeSet<>();
 ? ? ? ? ? ?set.add(new Student("刘备",20));
 ? ? ? ? ? ?set.add(new Student("张飞",18));
 ? ? ? ? ? ?set.add(new Student("关羽",19));
 ? ? ? ? ? ?//遍历集合
 ? ? ? ? ? ?for (Student stu : set) {
 ? ? ? ? ? ? ? ?System.out.println(stu);
 ? ? ? ? ? ? ? ?/*
 ? ? ? ? ? ? ? ? ? ?Student{name='张飞', age=18}
 ? ? ? ? ? ? ? ? ? ?Student{name='关羽', age=19}
 ? ? ? ? ? ? ? ? ? ?Student{name='刘备', age=20}
 ? ? ? ? ? ? ? ? */
 ? ? ? ? ?  }
 ? ? ?  }
 ?  }
 ? ?//2. 自定义类要实现Comparable接口
    public class Student implements Comparable<Student> {
 ? ?//3. 重写Comparable接口中的compareTo方法
 ? ?@Override
 ? ?public int compareTo(Student o) {
 ? ? ? ?/*
 ? ? ? ? ? ?return 当前对象的年龄 - 存入对象的年龄
 ? ? ? ? ? ? ? ?如果返回值为负数: 表示存入元素为较小值, 存左边
 ? ? ? ? ? ? ? ?如果返回值为0: 表示重复, 不存
 ? ? ? ? ? ? ? ?如果返回值为正数: 表示存入元素为较大值, 存右边
 ? ? ? ?*/
 ? ? ? ?int result = this.age - o.age;
 ? ? ? ?return result;
 ?  }
 ? ?

12. 自然排序-练习

需求
    按照年龄从小到大排序, 如果年龄一样, 按照姓名首字母排序
    如果姓名和年龄都一样, 认为是同一个人, 不存

?代码示例?

 ? ?public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?//创建集合添加元素
 ? ? ? ? ? ?TreeSet<Student> set = new TreeSet<>();
 ? ? ? ? ? ?set.add(new Student("zhangsan", 24));
 ? ? ? ? ? ?set.add(new Student("lisi", 18));
 ? ? ? ? ? ?set.add(new Student("wangwu", 24));
 ? ? ? ? ? ?set.add(new Student("zhaoliu", 24));
 ? ? ? ? ? ?set.add(new Student("chenglong", 58));
?
 ? ? ? ? ? ?//遍历集合
 ? ? ? ? ? ?for (Student stu : set) {
 ? ? ? ? ? ? ? ?System.out.println(stu);
 ? ? ? ? ? ? ? ?/*
 ? ? ? ? ? ? ? ? ? ?Student{name='lisi', age=18}
 ? ? ? ? ? ? ? ? ? ?Student{name='wangwu', age=24} //w在z前面
 ? ? ? ? ? ? ? ? ? ?Student{name='zhangsan', age=24} //细节: z、h、a都一样,比较n和o,n在o前面
 ? ? ? ? ? ? ? ? ? ?Student{name='zhaoliu', age=24}
 ? ? ? ? ? ? ? ? ? ?Student{name='chenglong', age=58}
 ? ? ? ? ? ? ? ? */
 ? ? ? ? ?  }
 ? ? ?  }
 ?  }
?
 ? ?class Student implements Comparable<Student> {
 ? ? ? ?@Override
 ? ? ? ?public int compareTo(Student s) {
 ? ? ? ? ? ?/*
 ? ? ? ? ? ? ? ?年龄从小到大排序: 如果当前对象年龄 - 存入对象年龄
 ? ? ? ? ? ? ? ? ? ?负数: 表示存入元素为较小值, 存左边
 ? ? ? ? ? ? ? ? ? ?为0: 表示重复, 继续判断姓名!
 ? ? ? ? ? ? ? ? ? ?正数: 表示存入元素为较大值, 存右边
 ? ? ? ? ? ? */
 ? ? ? ? ? ?int result = this.age - s.age;
 ? ? ? ? ? ?//result为0: 表示重复, 继续判断姓名!
 ? ? ? ? ? ?return result == 0 ? this.name.compareTo(s.name) : result;
 ? ? ?  }
 ? ? ?  ...
 ?  }

13. TreeSet-比较器排序Comparator的使用

比较器排序Comparator的使用步骤
    1. 使用带参构造, 创建TreeSet集合
    2. 比较器排序, 就是让集合构造方法接收Comparator的实现类对象, 重写compare方法
    3. 重写compare方法要注意, 排序规则必须按照要求的"主要条件"和"次要条件"来写
    
需求
    自定义Teacher类, 属性为name和age
    按照年龄排序, 如果年龄一样, 按照姓名排序

?代码示例?

public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?//比较器排序, 就是让集合构造方法接收Comparator的实现类对象, 重写compareTo方法
 ? ? ? ? ? ?TreeSet<Teacher> set = new TreeSet<>(new Comparator<Teacher>() {
 ? ? ? ? ? ? ? ?@Override
 ? ? ? ? ? ? ? ?public int compare(Teacher t1, Teacher t2) {
 ? ? ? ? ? ? ? ? ? ?//重写compareTo方法要注意, 排序规则必须按照要求的"主要条件"和"次要条件"来写
 ? ? ? ? ? ? ? ? ? ?//[1]主要条件: 比年龄
 ? ? ? ? ? ? ? ? ? ?int result = t1.getAge() - t2.getAge();
 ? ? ? ? ? ? ? ? ? ?//[2]次要条件: 比姓名
 ? ? ? ? ? ? ? ? ? ?return result == 0 ? t1.getName().compareTo(t2.getName()) : result;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  });
?
 ? ? ? ? ? ?//添加元素,遍历集合
 ? ? ? ? ? ?set.add(new Teacher("zhangsan", 24));
 ? ? ? ? ? ?set.add(new Teacher("lisi", 18));
 ? ? ? ? ? ?set.add(new Teacher("wangwu", 24));
 ? ? ? ? ? ?set.add(new Teacher("zhaoliu", 24));
 ? ? ? ? ? ?set.add(new Teacher("chenglong", 58));
?
 ? ? ? ? ? ?for (Teacher tea : set) {
 ? ? ? ? ? ? ? ?System.out.println(tea);
 ? ? ? ? ? ? ? ? ? ?/*
 ? ? ? ? ? ? ? ? ? ? ? ?Student{name='lisi', age=18}
 ? ? ? ? ? ? ? ? ? ? ? ?Student{name='wangwu', age=24} //w在z前面
 ? ? ? ? ? ? ? ? ? ? ? ?Student{name='zhangsan', age=24} //细节: z、h、a都一样,比较n和o,n在o前面
 ? ? ? ? ? ? ? ? ? ? ? ?Student{name='zhaoliu', age=24}
 ? ? ? ? ? ? ? ? ? ? ? ?Student{name='chenglong', age=58}
 ? ? ? ? ? ? ? ? ? ?*/
 ? ? ? ? ?  }
 ? ? ?  }
 ?  }

14. TreeSet-两种比较方式的对比

自然排序Comparable:
    自定义类实现Comparable接口, 重写compareTo方法, 根据返回值进行排序
    
比较器排序Comparator
    将Comparator接口的实现类作为参数, 传递给TreeSet的带参构造, 重写compare方法, 根据返回值进行排序
    
默认使用自然排序, 当自然排序不满足当前需求, 使用比较器排序
?
返回值规则
    如果返回值为负数: 表示存入元素为较小值, 存左边
    如果返回值为0: 表示重复, 不存
    如果返回值为正数: 表示存入元素为较大值, 存右边
    
练习需求
    存入四个字符串, "c","ab","df","qwer"
 ? ?按照长度升序排序, 长度一样按照首字母排序

?代码示例?

public class Demo {
 ? ? ? ?public static void main(String[] args) {
 ? ? ? ? ? ?/*
 ? ? ? ? ? ? ? ?1. 查看String源码发现String已经实现自然排序接口
 ? ? ? ? ? ? ? ? ? ?public final class String
 ? ? ? ? ? ? ? ? ? ?implements java.io.Serializable, Comparable<String>, CharSequence,
 ? ? ? ? ? ? ? ? ? ? ? Constable, ConstantDesc {
 ? ? ? ? ? ? ? ?2. 但是按照首字母进行排序,不满足题目要求
 ? ? ? ? ? ? ? ?3. 所以需要使用比较器排序完成!
 ? ? ? ? ? ? */
 ? ? ? ? ? ?TreeSet<String> set = new TreeSet<>(new Comparator<String>() {
 ? ? ? ? ? ? ? ?@Override
 ? ? ? ? ? ? ? ?public int compare(String s1, String s2) {
 ? ? ? ? ? ? ? ? ? ?//[1]主要条件: 按照长度升序排列
 ? ? ? ? ? ? ? ? ? ?int result = s1.length() - s2.length();
 ? ? ? ? ? ? ? ? ? ?//[2]次要条件: 按照首字母排序
 ? ? ? ? ? ? ? ? ? ?return result == 0 ? s1.compareTo(s2) : result;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  });
 ? ? ? ? ? ?set.add("df");
 ? ? ? ? ? ?set.add("c");
 ? ? ? ? ? ?set.add("qwer");
 ? ? ? ? ? ?set.add("ab");
?
 ? ? ? ? ? ?System.out.println(set);
 ? ? ?  }
 ?  }

15.数据结构-二叉树

命名约定
    TreeSet 树结构 - Set体系的一员
    ArrayList 数组结构 - List体系的一员
    LinkedList 链表结构 - List体系的一员
    
树的分类?
 ? ?二叉树
 ? ?二叉查找树
 ? ?平衡二叉树
 ? ?红黑树 (TreeSet集合底层是红黑树)
?
树结构中每一个元素称为: 节点(对象), 包含四个部分
    1. 父节点位置
    2. 值
    3. 左子节点位置
    4. 右子节点位置
    
注意
    如果再没有父节点了, 父节点地址为null
    如果再没有子节点了, 子节点地址为null
    
在树结构中, 每一个节点的子节点数量称为: 度 (没儿子了度就是0, 有两个儿子度就是2)
 ? ?
注意
    在二叉树中, 任意一个节点的度, 必须小于等于2
?
二叉树图形中的层数称为: 树高
最顶层的称为: 根节点
?
以根节点为中心,
    左子节点展开的图形称为: 左子树 (子树也是有树高的)
    右子节点展开的图形称为: 右子树 (子树也是有树高的)
?
注意
    普通二叉树, 是没有存储规则的?

16. 数据结构-二叉查找树

二叉查找树?
 ? ?又称为"二叉排序树", 或者"二叉搜索树"
 ? ?
特点?
 ? ?1. 每一个节点上最多有两个子节点
 ? ?2. 每一个节点的左子节点, 都小于自己
 ? ?3. 每一个节点的右子节点, 都大于自己
    总结: 任意一个节点从左到右都是依次增大的?

17. 数据结构-二叉树找树添加节点

将节点按照二叉查找树的规则存入
    07 04 10 05
 ? ?
存储规则?
 ? ?小的存左边
 ? ?大的存右边
 ? ?一样的不存
 ? ?
 ? ?07 ? ? ?07 -> 没人比较, 自己就是根节点
 ?↓ ? ?↓ ? ?04 -> 和根节点比较, 小于根节点存入左边
 ?04 ? 10 ? 10 -> 和根节点比较, 大于根节点存入右边
↓ ? ?↓
     05 ? ? 05 -> 还是和根节点比较, 小于根节点存入左边, 但是左边有人了(在二叉树中, 任意一个节点的度, 必须小于等于2), 所以和04节点比较, 大于04节点, 存入右边的子节点
     
思考: 如果现在11进来了, 怎么存? ? ? ? ? ?

18. 数据结构-平衡二叉树

平衡二叉树?
 ? ?二叉树左右两个子树的高度差, 不要超过1 (不要求树高完全一致)
    任意节点的左右两个子树, 都是平衡二叉树?

19. 平衡二叉树-左旋

保证二叉树平衡的机制
    1. 左旋
    2. 右旋
?
旋转触发的机制(重点记忆)
 ? ?当添加一个节点后, 该树不再是平衡二叉树了, 就会触发旋转
 ? ?
左旋?
 ? ?将根节点的右侧往左拉, 原来的右子节点变为根节点
 ? ?并将多余(没人要)的左子节点出让, 给已经降级的根节点当右子节点?

20. 平衡二叉树-右旋

左旋?
 ? ?将根节点的左侧往右拉, 原来的左子节点变为根节点
 ? ?并将多余(没人要)的右子节点出让, 给已经降级的根节点当右左子节点?

21. 平衡二叉树-小结

二叉树 -> 没有存储规律, 查找效率低
↓
二叉查找(搜索/排序)树 -> 每个节点的度<=2, 从根节点开始判断, 左子节点小于自己, 右子节点大于自己
↓
平衡二叉树 -> 左右两个子树高度差<=1
↓
如果新节点的加入打破了平衡 -> 触发保证二叉树平衡的机制
↓
左旋/右旋 -> 主要看朝那边拉

22. 平衡二叉树-左左和左右

由于添加数据的位置不同, 旋转的四种情况
    左左: 当根节点的左子树的左子树, 有节点插入, 导致平衡二叉树不平衡
    左右: 当根节点的左子树的右子树, 有节点插入, 导致平衡二叉树不平衡
    右右: 当根节点的右子树的右子树, 有节点插入, 导致平衡二叉树不平衡
    右左: 当根节点的右子树的左子树, 有节点插入, 导致平衡二叉树不平衡
    
注意:
    旋转保证平衡二叉树平衡, 不一定仅旋转一次, 有可能旋转多次
    以每一个节点为基准, 都可以旋转?

?

23. 平衡二叉树-右右和右左