树
树由根节点(root)和若干子树(T1,T2, … Tm-1)构成的具有层次关系的数据结构。
相关术语
节点的度 : 该节点子树个数，度为0的节点为叶子节点，度不为0的节点为分支节点
树的度 : 树中的节点的度最大值为树的度
节点的层次 : 根为第一层，往下依次递增
树的深度 : 节点层次最大值为树的深度
森林 : n棵不相交的树的集合为森林
二叉树
常用于实现二叉查找树、二叉堆
每个节点至多有两颗子树（树的度<=2）,子树分左右
第i层至多有2i-1个节点，深度为k的二叉树，最多节点数2^k-1个节点（具有最多节点的称作满二叉树），其中每个节点都与深度k满二叉树中1-n节点对应，则为完全二叉树
二叉排序树
- 左子树所有节点值小于根节点，右子树所有节点值大于根节点值
- 左右子树都是二叉排序树
二叉平衡树 AVL
- 左右子树深度差不超过1
- 左右子树都是二叉平衡树
哈夫曼树
最优二叉树
哈夫曼编码
解决报文编码的问题，将字符串转换为唯一的二进制码，且二进制码的长度最小
每个字符在字符串中出现频率为W，其编码长度为L，编码字符n个，则编码后二进制码的总长度为W1L1+W2L2+…+WnLn，利用哈夫曼树特性求总长最小编码
B树
平衡的多路查找树
B树的阶：所有孩子节点树的最大值（m叉树：每个节点最多m棵子树）
分支节点最少有两颗子树
分支节点包含信息（n，A0，K1，A1，K2，A2，…，Kn，An），其中，n为结点中的关键字树，A为指向子树根结点的指针，K为关键字，且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn；
所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空
B+树
B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶B+树和m阶的B-树的差异在于
有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点；
所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
红黑树
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。树中每个结点包含5个属性：color、key、left、right和p。如果一个结点没有子节点或父节点，则该结点相应的指针属性值为NIL，我们可以把这些NIL视为指向二叉搜索树的叶节点（外部结点）的指针，而把带关键字的结点视为树的内部结点。
性质
- 每个结点或是红色的，或是黑色的
- 根结点是黑色的
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的
- 如果一个结点是红色的，则它的两个子结点都是黑色的
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)
键树
如果一个关键字可以表示成字符的序号，即字符串，那么可以用键树（keyword tree），又称数字搜索树或字符树，来表示这样的字符串的集合。键树的结构受启发于一部大型字典的“书边标目”。字典中标出首字母是 A，B，C，…，Z的单词所在页，再对各部分标出第二字母为A，B，C，…，Z的单词所在的页等等。
键树是一种特殊的查找树，它是一棵度大于等于2的树，树中的每个节点不是包含一个或几个关键字，而是只含有组成关键字的符号。
比如：如果关键字是数值，则节点中只包含一个数位；如果关键字是单词，则节点中只包含一个字母字符。根结点不代表任何字符，根以下第一层的结点对应于字符串的第一个字符，第二层的结点对应于字符串的第二个字符……每个字符串可由一个特殊的字符如“$”等作为字符串的结束符，用一个叶子结点来表示该特殊字符。把从根到叶子的路径上，所有结点（除根以外）对应的字符连接起来，就得到一个字符串。因此，每个叶子结点对应一个关键字。在叶子结点还可以包含一个指针，指向该关键字所对应的元素。整个字符串集合中的字符串的数目等于叶子结点的数目。如果一个集合中的关键字都具有这样的字符串特性，那么，该关键字集合就可采用这样一棵键树来表示。
键树的存储通常有两种方式：
- 用树的孩子兄弟链来表示键树，称为双链树；每个Node有三个域：symbol域：存储关键字的一个字符；son域：存储指向第一棵子树的根的指针；brother域：存储指向右兄弟的指针。
- 用多重链表来表示键树，称为Trie树或字典树。
字典树
如果以树的多重链表来表示键树，则树的每个结点应包含d个（d为关键字符的基，如：字符集由英文大写字母构成时，则d=26）指针域，此时的键树又称为字典树。
字典树典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
Tire树的三个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符都不相同。
Tire树的应用： - 串的快速检索
给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。 - “串”排序
给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。 - 最长公共前缀
后缀树
所谓后缀树，就是包含一则字符串所有后缀的压缩了的字典树。先说说后缀的定义。给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1 <= i <= n，子串SiSi+1…Sn都是字符串S的后缀。以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8],S[2..8], … , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i..n]，我们说这项后缀起始于i。
键树只适合前缀匹配和全字匹配，并不适合后缀和子串匹配，而后缀树在这方面则非常合适。它与键树的最大不同在于，后缀树的单词集合是由指定字符串的后缀子串构成。
区间树与线段树
区间树是在红黑树基础上进行扩展得到的支持以区间为元素的动态集合的操作，其中每个节点的关键值是区间的左端点。通过建立这种特定的结构，可是使区间的元素的查找和插入都可以在O(lgn)的时间内完成。相比于基础的红黑树数据结构，增加了一个max[x]，即以x为根的子树中所有区间的端点的最大值。
线段树是一种平衡二叉查找树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。主要的处理思想是基于分治的思想。
设根节点的区间为[a,b),区间长度为L = b - a，线段树的性质：
1）线段树是一个平衡树，树的高度为log(L)；
2）线段树把区间上的任意长度为L的线段都分成不超过2log(L)线段。
败者树与胜者树
胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。在胜者树、败者树中，每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。不同的是，胜者树中的每个非终端结点均表示其左、右孩子结点中的“胜者”；而在败者树中，父结点中记下刚进行完的这场比赛中的败者，而让胜者去参加更高一层的比赛
哈夫曼树代码实现
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class HuffmanTree {
public static class Node<E> {
E data;
double weight;
Node leftChild;
Node rightChild;
public Node(E data, double weight) {
super();
this.data = data;
this.weight = weight;
}
public String toString() {
return "Node[data=" + data + ", weight=" + weight + "]";
}
}
public static void main(String[] args) {
List<Node> nodes = new ArrayList<Node>();
nodes.add(new Node("A", 40.0));
nodes.add(new Node("B", 8.0));
nodes.add(new Node("C", 10.0));
nodes.add(new Node("D", 30.0));
nodes.add(new Node("E", 10.0));
nodes.add(new Node("F", 2.0));
Node root = HuffmanTree.createTree(nodes);
System.out.println(breadthFirst(root));
}
/**
构造哈夫曼树
@param nodes
节点集合
@return 构造出来的哈夫曼树的根节点
*/
private static Node createTree(List<Node> nodes) {
// 只要nodes数组中还有2个以上的节点
while (nodes.size() > 1) {
quickSort(nodes);
//获取权值最小的两个节点
Node left = nodes.get(nodes.size()-1);
Node right = nodes.get(nodes.size()-2);
//生成新节点，新节点的权值为两个子节点的权值之和
Node parent = new Node(null, left.weight + right.weight);
//让新节点作为两个权值最小节点的父节点
parent.leftChild = left;
parent.rightChild = right;
//删除权值最小的两个节点
nodes.remove(nodes.size()-1);
nodes.remove(nodes.size()-1);
//将新节点加入到集合中
nodes.add(parent);
}
return nodes.get(0);
}
/**
- 将指定集合中的i和j索引处的元素交换
- @param nodes
- @param i
- @param j
*/
private static void swap(List<Node> nodes, int i, int j) {
Node tmp;
tmp = nodes.get(i);
nodes.set(i, nodes.get(j));
nodes.set(j, tmp);
}
/**
- 实现快速排序算法，用于对节点进行排序
- @param nodes
- @param start
- @param end
*/
private static void subSort(List<Node> nodes, int start, int end) {
if (start < end) {
// 以第一个元素作为分界值
Node base = nodes.get(start);
// i从左边搜索，搜索大于分界值的元素的索引
int i = start;
// j从右边开始搜索，搜索小于分界值的元素的索引
int j = end + 1;
while (true) {
// 找到大于分界值的元素的索引，或者i已经到了end处
while (i < end && nodes.get(++i).weight >= base.weight)
;
// 找到小于分界值的元素的索引，或者j已经到了start处
while (j > start && nodes.get(–j).weight <= base.weight)
;
if (i < j) {
swap(nodes, i, j);
} else {
break;
}
}
swap(nodes, start, j);
//递归左边子序列
subSort(nodes, start, j - 1);
//递归右边子序列
subSort(nodes, j + 1, end);
}
}
public static void quickSort(List<Node> nodes){
subSort(nodes, 0, nodes.size()-1);
}
//广度优先遍历
public static List<Node> breadthFirst(Node root){
Queue<Node> queue = new ArrayDeque<Node>();
List<Node> list = new ArrayList<Node>();
if(root!=null){
//将根元素加入“队列”
queue.offer(root);
}
while(!queue.isEmpty()){
//将该队列的“队尾”元素加入到list中
list.add(queue.peek());
Node p = queue.poll();
//如果左子节点不为null，将它加入到队列
if(p.leftChild != null){
queue.offer(p.leftChild);
}
//如果右子节点不为null，将它加入到队列
if(p.rightChild != null){
queue.offer(p.rightChild);
}
}
return list;
}
}