二叉树（Binary Tree）
树
- 根节点、父节点、兄弟节点、叶子节点
-
高度、深度、层的概念
二叉树
顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点，并不要求都要有二个节点，有的只有左节点，有的只有右节点
满二叉树
- 图中编号2的二叉树，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树
完全二叉树
- 图中编号3的二叉树，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树
如何表示（或者存储）一棵二叉树？
- 链式存储法
- 顺序存储法
- 基于数组
- 如果节点 X 存储在数组中下标为 i 的位置，
- 下标为 2 * i 的位置存储的就是左子节点，
- 下标为 2 * i + 1 的位置存储的就是右子节点。
- 反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。
- 适用于完全二叉树，如果是非完全二叉树会浪费空间；
- 堆就是完全二叉树，且常使用数组存储数据
二叉树的遍历
- 前序遍历--访问顺序：父节点--》左子节点--》右子节点
- 中序遍历--访问顺序：左子节点--》父节点--》右子节点
- 后序遍历--访问顺序：左子节点--》右子节点--》父节点
二叉查找树（Binary Search Tree）
- 概念
在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
- 能实现快速查找、插入、删除
- 查找--从根节点开始比较，小于则在左子树递归查找，大于则在右子树递归查找
- 插入--从根节点开始比较，小于则：1.左子树为空，则插入左子树；2.左子树不空，则左子树递归查找插入； 大于则：1.右子树为空，则插入右子树；2.右子树不空，则右子树递归查找插入。
- 删除--三种情况：
- 1.删除节点无子节点--父节点指向该节点指针置为null;
- 2.删除节点只有一个子节点(左或右)--父节点指向该节点指针指向该节点的子节点；
- 3.删除节点有两个子节点--需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点。如下图删除节点18
- 其他操作
快速地查找最大节点和最小节点、前驱节点和后继节点
支持重复数据的二叉查找树
- 插入时，节点值相同，则插入相同节点的右子树。
- 查找时，遇到值相同，则不停止查找，继续在右子树查找直至叶子节点。
- 删除时，先找到值相同的所有节点，然后按照二叉树节点删除方法依次删除。
复杂度分析
- 理想情况下，二叉查找树是一个完全二叉树，复杂度跟高度相关O(height)，完全二叉树的高度小于等于logn，所以插入、删除、查找时间复杂度均为O(logn)
- 最坏情况下，二叉查找树退化为链表，查找时间复杂度为O(n)
二叉查找树相对散列表的优势
- 散列表无序，二叉查找树中序遍历可在O(n)时间复杂度内输出有序数据序列。
- 散列表扩容耗时很多，遇到散列冲突时，性能不稳定；平衡二叉树性能稳定在O(logn)。
- 散列表由于散列冲突的存在，其常量级的查找时间复杂度再加上hash函数的耗时不一定比O(logn)效率高。
- 散列表构造复杂，需考虑散列函数的设计、冲突解决办法、扩容、缩容等，平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
- 为避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
二叉树高度计算
- 深度优先遍历计算 max(左右子树高度)+1