树

结点是数据结构的基础，是构建复杂数据结构的基本组成单位。
树是n（n>=0）个结点的有限集，n=0被称为空树

在任意非空树中

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

定义树的时候需要注意的

1. 根节点是唯一的，不能存在多个根结点
2. 子树的个数没有限制，但是他们一定是互不相交的
3. 树的定义中使用了递归的方式，递归在树的学习过程中起着重要的作用

结点的度：结点拥有子节点的数量称为这个结点的度
结点关系：结点子树的根节点称为该结点的双亲结点，相应该结点称为孩子结点的父结点（双亲结点）
树的深度（结点层次）：树中结点的最大层数称为树的高度或深度

二叉树

二叉树是n个结点的有限集合，如果n=0，那就称为空二叉树

二叉树的特点

1. 每个结点最多只有两颗子树，所以二叉树中不存在度大于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. 非叶子结点的度一定是2
3. 在同样深度的二叉树中，满二叉树的个数最多，叶子数也最多

完全二叉树

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

二叉树的存储结构

1. 顺序存储：使用一维数组存储二叉树的结点，并且结点的存储位置，就是数组的下标索引。当二叉树为完全二叉树时，结点树刚好填满数组。

   • 如果二叉树不是完全二叉树，也要采用顺序存储，顺序存储结构中已经出现了空间浪费的情况。
   • 比如右斜树极端情况，采用顺序存储的方式是十分浪费空间的，顺序存储只适用于完全二叉树。
2. 二叉链表：顺序存储不能满足二叉树的存储要求，采用链式存储。二叉树的每个结点都有两个孩子，可以讲结点数据结构定义成一个数组和两个指针。

二叉树的遍历

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

二叉树的访问次序

递归遍历，自上而下，从左到右，每个结点会走三次

1. 前序遍历，从二叉树的根结点出发，按照先向左再向右的方向访问 （根左右）
   
2. 中序遍历，从二叉树的根结点出发，先向左再向右的方向访问 (左右根）
   
3. 后序遍历，从二叉树的根结点出发，按照先向左再向右的方向访问 （左根右）
   
4. 层次遍历，按照树的层次自上而下的遍历二叉树
   

用“链表”来遍历

class TreeNode<T> { // 二叉树链表存储 泛型
    T date; // 数据
    TreeNode left; // 左孩子
    TreeNode right; // 右孩子

    public TreeNode(T data) {
        this.date = data;
    }

    // 前序遍历
    // 传入的参数就是根结点
    public static void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.date);
        preorder(root.left);
        preorder(root.right);
    }

    // 中序遍历
    public static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.println(root.date);
        inorder(root.right);
    }

    // 后序遍历
    public static void postorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        inorder(root.right);
        System.out.println(root.date);
    }
}
public class Ch01 {

    public static void main(String[] args) {

        TreeNode<Integer> root = new TreeNode<>(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // 前序遍历
        System.out.println("--------前序遍历-----------");
        TreeNode.preorder(root);
        System.out.println("--------中序遍历-----------");
        TreeNode.inorder(root);
        System.out.println("--------后序遍历-----------");
        TreeNode.postorder(root);
    }
}

用“栈”来遍历

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();
    }
}

public class Ch02 {

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        Node.preorder(root);
    }
}

其他树的分类

1. 二叉查找树（二叉搜索树，二叉排序树）

   • 若左子树不为空，左子树所有的值小于它根结点的值
   • 若右子树不为空，右子树所有的值大于它根结点的值
   • 左右子树也是一个二叉查找树
   • 没有键值相等的点

2. 平衡二叉树（AVL树）
   含有相同结点的二叉树的不同形态，找出一个查找平均长度最小的一颗二叉查找树

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

3. 红黑树（HashMap重点应用）
   它时一种自平衡的二叉树，增加了一个颜色属性。结点的颜色只能是红色或黑色。

   • 根结点只能是黑色
   • 红黑树中，所有的叶子结点再街上左右两个空结点，保持算法的一致，所有的空结点都是黑色
   • 其他的结点要么是黑色，要么是红色，红色结点的父结点和左右孩子结点都是黑色，黑红相间
   • 在任意一颗子树中，从根结点向下走到空结点的路径上所经历的黑色结点的数是相同的，保证它是一个平衡二叉树

   

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

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

5. B+树

   B-树和B+树，后序在数据库中才会重点应用

时间变得如此宝贵，坐下来休息是件不堪设想的事情。只要朝着某个方向去，或朝任何方向走，就多少会有进展，说不定就会有好结果，否则就是坐以待毙，就是缩短死神赶上他们的时间。 ——马克·吐温《汤姆·索亚历险记》