树

树(Tree)：是n(n>=0)个结点的有限集，n=0，称为空树
在任意的非空树中：

1. 有且仅有一个特定的称为根节点
2. 当n>1时，其余结点可分为m个互不相交的有限集

定义树的时候

1. 根节点是唯一的，不能存在多个根节点
2. 子树的个数没有限制，但他们一定是互不相交的

• 结点：结点是数据结构中的基础，构成复杂数据结构的基本组成单位
• 结点的度：结点拥有子节点的数量称为结点的度
• 结点关系：结点子树的根节点称为该结点的孩子结点
• 树的深度：树中结点的最大层数称为树的深度或高度

二叉树

n(n>=0)个结点的有限集，n=0，称为空二叉树

特点

1. 每个结点最多只能有2个子结点，所以二叉树中不存在度大于2的结点
2. 左子树和右子树是有顺序的，次序不能任意颠倒
3. 即使树中某个结点只有一个子结点，也要区分它是左子树还是右子树

性质

1. 在二叉树中第i层上最多有2^(i-1) (i>=1)
2. 在二叉树中如果深度为k，那么最多有2^k-1个结点
3. n0=n2+1，n0表示度数为0的结点，n2表示度数为2的结点数
4. 在完全二叉树中，具有n个结点的完全二叉树的深度[log2n]+1，其中[log2n]向下取整
5. 若对含n个结点的完全二叉树从上到下且从左到右进行1至n的编号，则对完全二叉树中的任意一个编号为i的结点有 如下特征：

• • 若i=1，则该结点是二叉树的根，无父节点，否则，编号为i/2的结点为其父结点
• • 若2i>n，则该结点没有左孩子结点，否则，编号为2i的结点为其左孩子结点
• • 若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为右孩子结点

存储结构

1. 顺序存储

• • 使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。
• • 当二叉树为完全二叉树时，结点数刚好填满数组。
• • 如果二叉树不是完全二叉树，采用顺序存储，顺序存储结构中已经出现了空间浪费的情况。
• • 比如右斜树极端情况，采用顺序存储的方式是十分浪费空间。
• • 顺序存储只适用于完全二叉树。

2. 二叉链表

• • 顺序存储不能满足二叉树的存储要求，采用链式存储。
• • 二叉树的每个结点都有两个孩子
• • 可以将结点数据结构定义成一个数据和两个指针域。

二叉树的遍历

二叉树的遍历从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次，且仅被访问一次

二叉树的访问次序可以分为4种：

1. 前序遍历(根左右)
2. 中序遍历(左根右)
3. 后序遍历(左右根)
4. 层次遍历
   按照树的层次自上而下的遍历二叉树

实例代码1(递归实现前中后排序)

class TreeNode<T>{
    T data; //数据本身
    TreeNode left; //左孩子
    TreeNode right; //右孩子
    
    public TreeNode(T data) {
        this.data = data;
    }
    //前序遍历
    // 传入的参数就是根节点
    public static void preorder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.println(root.data);
        // 递归
        preorder(root.left);
        preorder(root.right);
    }
    //中序遍历
    public static void inorder(TreeNode root) {
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.println(root.data);
        inorder(root.right);
    }
    // 后序
    public static void postorder(TreeNode root){
        if(root == null){
            return;
        }
        postorder(root.left);
        postorder(root.right);
        System.out.println(root.data);
    }
}

斜树

所有的结点都只有左子树的二叉树叫做左斜树，所有的结点都只有右子树的二叉树叫做右斜树

满二叉树

在一颗二叉树中，如果所有分支结点都在存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树叫做满二叉树

特点

1. 叶子只能出现在下一层
2. 非叶子结点的度一定是2
3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

完全二叉树

对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉中编号为i的结点位置完全相同，则这棵二叉树称为完全二叉树

实例代码2(用栈实现前根排序)

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    public static void preorder(Node head){
        if(head != null){
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            while(!stack.isEmpty()){
                head = stack.pop();
                System.out.print(head.value + "、");
                if(head.right != null){
                    stack.push(head.right);
                }
                if(head.left != null){
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }
}

二叉查找树：（二叉搜索树、二叉排序树）

1. 若左子树不为空，左子树的所有的值小于它的根节点的值
2. 若右子树不为空，右子树的所有的值大于它的根节点的值
3. 左右子树也是一个二叉查找树
4. 没有键值相等的点

平衡二叉树(AVL树)

含有形同结点的二叉树的不同形态，找出一个查找平均长度最小的一颗二叉查找树

1. 要么是一颗空树，要么其根结点的左右子树的深度之差的值不超过1
2. 左右子树也是平衡二叉树
3. 二叉树结点的平衡因子定义为该结点的左子树的深度减去右子树的深度
   平衡因子 = 左子树的深度 - 右子树的深度

红黑树（HashMap重点应用）

自平衡的二叉树。又增加了一个颜色的属性。
结点的颜色只能是红色或黑色。

1. 根节点只能是黑色
2. 红黑树中，所有的叶子结点后面再接上左右两个空结点，保持算法的一致性，所有的空结点都是黑色
3. 其他的结点要么是黑色，要么是红色，红色结点的父节点和左右孩子结点都是黑色，黑红相间
4. 在任一颗子树中，从根节点向下走到空结点的路径上所经理的黑结点数相同，平衡二叉树

B-树(B树)

B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树

1. 树中每个子结点至多有m棵子树
2. 若根结点不是叶子结点，则至少有2棵子树
3. 除根结点外所有非终端结点至少有[m/2]棵子树
4. 每个结点的信息结构（A0,K1,A1,K2....Kn，An），其中n表示关键字个数
   其中K为关键字，A是指针
5. 所有的叶子结点都出现在同一层次上，且不带任何信息。

B+树

集合框架(重要)

集合：容器，存放数据的一个容器
使用集合的目的：更方便的存储和操作数据，CRUD

集合继承结构

1. Collection：存放单值的最大父接口

• • List(列表)线性表：和数组类似，list可以动态增长，查找元素效率高，插入删除元素的效率低，因为会引起其他元素位置的改变
• • Set也是线性表，查询元素效率低，插入删除元素的效率高，插入和删除不会引起元素移位

1. Map<K,V>：存放对值的最大父接口

• • Map(映射)：用于保存具有映射关系的数据，Map保存着两组数据：key和value
• • key和value都可以是任意的应用数据类型，但key不可以重复

List和Set继承自Collection，Map不是

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
    ArrayList:内部结构是一个数组
 */
public class Ch02 {
    public static void main(String[] args) {
        //创建一个ArrayList集合
        //开发中一般情况下，使用多态创建集合
        //向上转型
//        ArrayList<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        //集合的新增
        l2.add(1);
        l2.add(2);
        l2.add(3);
        l2.add(4);
        l2.add(5);
        l2.add(1,-1);
//      从后新增
        l2.addAll(l2);

//      清空集合元素，集合中没有数据size==0,集合为null
//        l2.clear();

        //直接打印集合对象  ArrayList里重写了toString方法，所有直接输出了集合对象，而不是地址
        System.out.println(l2);

        //把下标为0的值改为200
        l2.set(0,200);

        //集合和数组之间的转换   建议封装一个工具类
        //数组-->集合
        int[] arr = new int[]{1,2,3,4,5};
        List<Integer> integers = Arrays.asList(1,2,3,4,5);
        System.out.println(integers);
//        List<int[]> arr1 = List.of(arr);

//      contains方法判断元素是否存在是根据元素的equals方法进行比较，若元素中没有重写equals方法，那么contains将比较对象
        System.out.println(l2.contains(1));

        //获取指定下标值
        System.out.println(l2.get(0));

        //判断是否是为空
        System.out.println(l2.isEmpty());

        //返回输入值的下标，没有就返回-1
        System.out.println(l2.indexOf(1000));
    }
}

如果初始化集合尽量指定初始化容量，如果确定不了，默认指定为16
使用泛型，数据的类型时候，一定要使用引用数据类型
List集合中存放的数据：

1. 数据有顺序（添加的先后顺序）
2. 数据可以重复