二叉树 (Binary Tree) 三种存储结构及四种遍历：先根
Binary Tree 三种存储结构及四种遍历：先根、中根、后根、层序
一、二叉树的分类：
- 完全二叉树：一个二叉树的深度为d,除了d层外，其他各层的节点数目均达到最大值。
-
满二叉树：所有叶节点都在最底层的完全二叉树
-
平衡二叉树（ALV树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。
-
排序二叉树（又称二叉查找树、二叉搜索树，有序二叉树）
-
霍夫曼树（Huffman Coding又称哈夫曼树或最优二叉树）：带权路径最短的二叉树。霍夫曼编码使用变长编码表对源符号进行编码，典型应用图文压缩。
-
红黑树，一种自平衡二叉查找树（区分概念：自平衡二叉查找树，平衡二叉树ALV），每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。
红黑树确保没有一条路径会比其它路径长出两倍，随着元素个数的增加查找性能几乎是均匀的。应用于jdk中TreeMap和TreeSet 和jdk8的HashMap，nginx的定时器。
-
B树和B+树是一种多叉树。
二、三种表示结构
2.1 顺序存储
一个存储在数组中的完全二叉树
顺序存储的缺点在非满二叉树的情况下浪费空间，例如极端情况深度为h的二叉树每个节点都只有右孩子，该结构需要占用2^h-1的空间，实际却占用了h个节点。
String[] arrayBinaryTree = {"A", "B", "C", "D", "E", "F", "G", "#", "I"};
2.2 二叉链表存储 只包含对左右子节点的连接指针
class BinaryLinkedListBinaryTree {
private String data;
private BinaryLinkedListBinaryTree leftChild = null;
private BinaryLinkedListBinaryTree rightChild = null;
//…
}
2.3 三叉链表存储 节点包含对父节点和左右子节点的指针
改进于二叉链表，增加父节点的指引，能更好地实现节点间的访问
public class TripleLinkedListBinaryTree {
private String data;
private TripleLinkedListBinaryTree fatherNode = null;
private TripleLinkedListBinaryTree leftChild = null;
private TripleLinkedListBinaryTree rightChild = null;
//…
}
三、几种遍历(traversal)方式：前序、中序、后序、层序
针对前序遍历、中序遍历、后序遍历，先左和先右的效率是一样的，按照习惯，我们碰到左右排序的时候一般都采用先左边后右边。
3.1 前序遍历
又称先根遍历，按照 ROOT-LEFT-RIGHT 来遍历.
针对一颗顺序存储的平衡二叉树:{"A", "B", "C", "D", "E", "F", "G", "#", "I"}
其先根遍历结果是：A B D I E C F G
3.2 中序遍历
又称中根遍历，遍历顺序： LEFT-ROOT-RIGHT
对应前根遍历的二叉树，中根遍历结果是：D I B E A F C G
3.3 后续遍历
又称后根遍历，遍历顺序： LEFT-RIGHT-ROOT
对应前面的平衡二叉树，其后根遍历结果：I D E B F G C A
3.4 层序遍历
一层一层的遍历，结果是：A B C D E F G I
其他：图的搜索 深度优先 Depth-First-Search 广度优先 Breadth-First-Search
- 深度优先搜索，是一种遍历或搜索图的算法，类似于树遍历的先根遍历。
- 广度优先搜索，是一种遍历或搜索图的算法。类似于树遍历的层序遍历。（又作：宽度优先搜索，横向优先搜索）
