树和森林

树和森林

树的存储结构：

双亲表示法

孩子表示法

利用图表示树

孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点

将树转化成二叉树：右子树一定为空

加线：在兄弟之间加一连线

抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系

旋转：以树的根结点为轴心，将整树顺时针转45°

森林转换成二叉树：

将各棵树分别转换成二叉树

将每棵树的根结点用线相连

以第一棵树根结点为二叉树的根

树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历

哈弗曼树/霍夫曼树

一些概念

路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；

路径长度：路径上的分支数目称为路径长度；

树的路径长度：从根到每个结点的路径长度之和。

结点的权：根据应用的需要可以给树的结点赋权值；

结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；

树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作  WPL=∑wi×li

哈夫曼树：假设有n个权值(w1,  w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。

前缀码的定义：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码，可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树，若有n个节点，则共有(n+1)/2个码子

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。哈夫曼树的结点个数必为奇数。

哈夫曼树不一定是完全二叉树，但一定是最优二叉树。

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。