一. Binary Search Tree(BST)
1. 概念
Root 根，树顶端的节点。一棵树只能有一个节点。
Parent 父 - Child 子
Leaf 叶子，没有孩子的节点。
Level（Height）高度。root在高度0。 空树和只有根节点的树高度为0。
full binary tree 满树，每一个节点都有零个或两个孩子。
complete tree 完全树，除了最后一层，其它层的所有节点都被填充。
例如：
1
2 3
4 5 6 完全树，但是不满。
1
2 3
4 5 满树，但不完全。
8 9平衡树：它是一棵空树，或左右两子树的高度差绝对值不超过1，且左右子树均是平衡树。（红黑、AVL等树待补充）
2. 常用方法
find(int key);
insert(int key, double value);
delete(int key);
traverse();
3. 实现
实现每种方法时都要注意先判断是不是空树。
3.1 deleted方法：需要判断四种情况：（1）not found （2）a leaf （3）node with one child （4）node with two child。需要有一个flag变量确定找到的节点是左子树还是右子树。
其中，第四种情况比较特殊，需要找到继承当前位置的节点。我们一般寻找当前节点的左子树中最大的节点，或右子树中最小的节点进行继承。另外要注意指针的移动，需要判断找到的继承节点是不是当前节点的直接孩子。
3.2 遍历二叉树：遍历二叉树分为以下方法
Depth First 深度遍历：preorder（前序），inorder（中序），postorder（后序）
Breadth First 广度遍历：level order （层序）
此处以inorder为例，用递归和非递归方法分别实现。preorder只是print的位置不同，非递归时在循环中print。后序非递归需要一个flag变量来标记右子树是否访问过。（后序遍历非递归程序待补充 可参考 http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html）
/** * 非递归，需要借助栈来实现 */ public static int inOrder() { Stack s; Node p = root; while(p != null || !s.empty()) { while(p != null) { s.push(p); p = p.left; } p = s.top(); s.pop(); System.out.println(p); p = p.rchild; } } /** * 递归 */ public static int inOrderRecursive(Node toVisit) { if (toVisit != null) { inOrderRecursive(toVisit.left); System.out.println(toVisit); inOrderRecursive(toVisit.right); } }
4.时间复杂度
对于BST来说，遍历的复杂度为O（n）。查找search的最坏情况是树形成了一条链表的形状，时间复杂度也是O（n）。
二. 哈夫曼编码Huffman Coding、哈夫曼树
fixed width code编写26个字母至少需要5位。
Huffman code利用权值最高的节点距离最短的思想缩减编码所需的位数。
建立哈夫曼树步骤如下：
（1）创建每一个节点，计算它们的权值。
（2）将权值最小的两个节点放进一个树，把它们的和作为权值建立父节点
（3）再寻找两个权值最小的节点（包括我们刚刚建立的节点），把它们的和作为权值建立新的父节点
（4）重复（3）直到所有节点被连接
（5）给所有左枝标记为0，所有右枝标记为1
三. TreeMap and TreeSet
TreeMap的实现依靠红黑树算法。红黑树是一种自平衡的排序二叉树。
补充红黑二叉树内容前。暂时需要了解如下内容。
TreeMap与HashMap的区别是，它可以实现按顺序遍历。所有存进TreeMap和TreeSet的对象必须是可排序的。
例：可以用schedule.headSet(1600).last() 来得到1600之前的相邻数据。
可以用schedule.tailSet(1600).first()来得到1600之前的相邻数据。
