二叉树理论基础
二叉树的总类
在算法题中，二叉树主要有两种：满二叉树和完全二叉树
满二叉树
如果一颗二叉树只有度为零和贰的结点，并且度为零的结点在同一层上，则这颗二叉树被称为满二叉树
这颗二叉树为满二叉树。
也可以称为深度为k，有2^k-1个结点的二叉树
完全二叉树
定义：
在完全二叉树中，除了最底层结点可能没填满外，其余每层结点数都达到最大值，并且最下面一层的结点都集中在该层最左边的若干位置。
若最底层为第h层，则该层包含1~2^h-1个结点
优先级队列其实是一个堆，堆是一棵完全二叉树，同时保证父子结点的顺序关系
二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值；
- 它的左、右子树分别为是二叉排序树
下面这两棵树都是二叉搜索树
平衡二叉搜索树
平衡二叉搜索树：简称AVL树（Adelson-Velaky and Landis）。它是一棵空树或者它的左右两个子树的高度差的绝对值不超过壹，并且左右两个子树都是一棵平衡二叉树
如图：
最后一棵不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了壹。
C++中map、multimap、multiset的底层实现都是平衡二叉搜索树
二叉树的储存方式
二叉树可以链式储存，也可以顺序储存。
链式储存用指针
顺序储存用数组
顾名思义就是顺序储存的元素在内存是连续分布的，而链式储存则是通过指针把分布在散落在各个地址的结点串联一起