树
非线性表结构：树，二叉树，二叉查找树，平衡二叉查找树、红黑树, 递归树
树的高度，深度，层
- 高度：从下往上， 从最底层开始计数，并且计数的起点是0
- 深度：从上往下， 从根节点开始度量，并且计数的起点是0
- 层： 跟深度计算类似，但是计数起点是1
二叉树
满二叉树 ： 叶子节点全都在最底层，除了叶子节点外，每个节点都有左右两个子节点
完全二叉树： 叶子节点都在最底的两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都是满的
二叉树的存储
链式存储法： 每个节点有三个字段，一个存储数据，另外两个指向左右子节点的指针
顺序存储法： 根节点存储在下标i=1的位置，左子节点存储在下标2 i = 2 的位置，右子节点存储在下标2 i + 1的位置， 以此类推。
如果是完全二叉树，那用数组存储无疑是最省内存的一种方式
二叉树的遍历
遍历的时间复杂度是O(n)
- 前序遍历：对树种任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印右子树
- 前序非递归的遍历： 采用栈。
- 1:初始化堆栈
- 2:把根节点指针入栈
- 3:当堆栈非空时，循环执行下列步骤(while)
- 出栈取得栈顶节点，访问该节点，打印
- 若该节点右孩子节点非空，将该节点右孩子指针入栈
- 若该节点左孩子节点非空，将该节点左孩子指针入栈
中序遍历：对树种任意节点来说，先打印它的左子树，然后打印它本身，最后打印右字数
后序遍历：对树种任意节点来说，先打印它的左子树，然后打印右子树， 最后打印这个点本身
层序遍历：每一层进行打印
- 采用队列进行遍历
- 1：初始化队列
- 2：把根节点指针入队列
- 3：当队列非空时，循环执行下列步骤(while)
- 出队列，获取头节点，访问该节点，打印
- 若该节点左孩子节点非空，则将该节点左孩子节点入队列
- 若该节点右孩子节点非空，则将该节点右孩子节点入队列
二叉查找树(二叉搜索树)
二叉查找树： 在树种任意一个节点，其左子树中每个节点的值，都要小于这个节点的值，其右子树每个节点的值都要大于该节点的值。
中序遍历二叉查找树可以输出有序的数据序列，时间复杂度O(n)
二叉查找树，如果根节点的左右子树极度不平衡，就已经退化成链表了，所以查找的时间复杂度变成O(n). 但是这不是我们想要的
- 二叉查找树中两个极端情况的时间复杂度O(n), O(logn)分别对应退化成链表的情况和完全二叉树。
平衡二叉查找树： 不管是删除还是插入数据，都能较好的保持左右子树较为平衡
- 平衡二叉查找树的高度接近logn,所以插入，删除，查找的时间复杂度比较稳定是O(logn)
红黑树(平衡二叉查找树)
其实有很多平衡二叉查找树，为什么在工程中大家喜欢用红黑树？
Treap, Splay Tree 绝大部分情况下操作效率很高，但无法避免极端情况下时间复杂度的退化
AVL树是一种高度平衡的二叉树，查找效率很高，但每次插入删除都有做调整，对于频繁的插入删除操作，使用AVL树代价就很高
红黑树只是近似平衡，在维护平衡的成本上比AVL树要低。此外插入，删除，查找等各种操作性能都比较稳定。工业中更倾向于这种稳定的平衡二叉查找树。