树的基础概念
定义
树是一个没有简单回路的连通的无向图
Theorem1：一个无向图是树当且仅当任意两个顶点之间都有唯一的简单路径
根树（Rooted Trees）
根树有一个特定的节点称为根，从根开始，可以定义从跟到树中其他顶点的路径。这种路径的方向性使得每一个顶点（除了根）都有一个唯一的前驱节点
树的Terminology
parent：除根外，每一个节点都有唯一的parent与之对应，parent相同的节点叫做sibling
child：除叶子节点外，每一个节点都有child节点，有孩子节点的节点称为internal vertices
ancestors:从根节点到某一节点v上的所有节点都是v的祖先（包含根节点）
descendants:如果u是v的祖先，那么v就是u的后代
subtree：以某一顶点a为根节点的子树，包含了a的所有后代
m-ary 树
每一个节点的孩子个数不超过m的树称为m-ary树，如果每一个internal vertices的孩子节点数都是m，那么这棵树就成为满m-ary树。
排序树（Ordered Rooted Trees）
排序树是一个根树，其中每一个节点的孩子节点都是从左到右有序分布的
Theorem2:n个结点的树有n-1条边
Theorem3:有i个内部节点的满m-ary树有$n=mi+1$个顶点
Theorem4：如果一个满m-ary树有n个顶点，$i=(n-1)/m$个内部顶点，叶子节点数为$l=[(m-1)n+1]/m$
平衡树（Balanced Trees）
一棵树的所有叶子结点的高度相差不超过1，那么这棵树就是一棵平衡树
Theorem5：一颗高度为h的m_ary平衡树最多有$m^h$个叶子节点
Corollary:如果一个高度为h的m-ary的树有l个叶子，那么$h\geq $
树的应用
二叉查找树：每一个节点都满足左孩子小于根节点，右孩子大于根节点
决策树（Decision trees）:二叉树可以用作决策树
example:有七枚形状大小一样的硬币，其中6枚质量一样，有一枚质量比这6枚轻，用一个天平要称几次才能找到质量轻的这一枚硬币
step1:分成两堆，每堆三枚硬币，这两堆称重情况有三种，如果一样中就找到了
step2：选上一步轻的那一堆，选两个称重，这次能直接得到答案
前缀编码（Prefix Codes）:每一个字符对应的比特串不能作为其他字母对应的比特串的开始
哈夫曼编码（Huffman Coding）：按照字符的出现频率给字符排序，每次选择两个最小的字符合并为一个大的字符，两个小字符中更小的的放在大字符的左边，同时边记作0，稍大的放在大字符右边，记作1
生成树
$G$是一个简单图，$G$的一个生成树就是$G$的一个子图，这个子图是一个包含了$G$所有顶点的树
定理：如果一个图有生成树，那么这个图一定是连通的
深度优先搜索
用深度优先搜索构建一个生成树，先随机选一个顶点作为根，然后从这个顶点开始，选择第一个相邻的顶点作为子树的根，再从子树的根出发，选择与其相邻的一个顶点（并且该顶点没有被访问过）作为根，一直重复该过程，直到找不到顶点作为子树的根，那么返回到上一个顶点，并重复该过程，如果找不到顶点作为子树的根，那么返回上一顶点……，重复该过程，到树的根的所有邻接节点访问完成，就完成了该过程
广度优先搜索
用广度优先搜索构建一个生成树，首先也是随机选取一个顶点作为根，然后我们把与这个根相邻的所有顶点入队，记作树的第一层，对队列中的每一个顶点，将其所有相邻的且不在队列中的顶点入队，并记作第二层，依次循环操作，直到所有顶点都被加入到树中
最小生成树
所有边的权重之和最小的生成树
Prim’s 算法
先选一条最小边，