多叉树的表示
多叉树
每个结点的分支数量不固定，可能有多个可能没有
1、父指针表示法
定义一个结构，其中包含data和parent用来表示当前结点数据和父亲结点位置然后用连续的结构体表示该树：
优点： 可用parent直接找到双亲，并且很容易找到祖先。时间复杂度O（1）
缺点：需要查找节点的孩子及其子孙时要遍历整个结构。时间复杂度O(n)
2、子女链表示法
*把每个结点的 子女结点的位置以单链表的结构存储 ，则n个结点生成了n条单链表，再将 n 条单链表头指针以顺序线性表存储 *
优点: 方便搜索孩子结点
缺点: 查找父结点需要从头遍历整个顺序表
3、双亲子女表示法
我们将父指针表示法和子女链表示法结合起来这样查找父亲和孩子结点都方便
4、子女兄弟链表示法
以二叉链表作为树的存储结构，结点的两个链域分别指向该结点的第一个孩子和右边的第一个兄弟
启示：一颗树可以转化为一个只有左子树的二叉树
树、森林、二叉树转换和遍历
转换方法
根据前面的子女兄弟链表示法我们可以进一步得出树、森林、二叉树的转换方法
树、森林–》二叉树画线更方便
二叉树—-》树、森林定义更方便
树的遍历
1.树的先根遍历（深度优先遍历）
若树不空，则先访问根结点，然后依次先序遍历各棵子树。
子女兄弟链图中的树先根遍历为:R A D E B C F G H K
树的先根遍历序列与该树对应的二叉树的先序遍历序列相同
2.树的后根遍历（深度优先遍历）
若树不空，则先依次后序遍历各棵子树，然后访问根结点。
子女兄弟链图中的树后根遍历为:D E A B G H K F C R
树的后根遍历序列与该树对应的二叉树的中序遍历序列相同
3.树的层序遍历（广度优先遍历）
若树不空，则自上而下自左至右访问树中每个结点。
森林的遍历
1.森林的先根遍历（深度优先遍历）
即依次对每一棵树进行先根遍历
森林的先根遍历序列与其对应的二叉树的先序序列一致。
2.森林的后根遍历（深度优先遍历）
即依次对每一棵树进行后根遍历
森林的后根遍历序列与其对应的二叉树的中序序列一致。
先先、后中
3.森林的广度优先遍历
从第1层起，自顶向下，同一层自左向右，依次访问森林中各棵树的结点。
Huffman树及其应用
参考文章:
Huffman树概念
路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度：路径中分支的数目称为路径长度。（线的条数）
根据路径长度定义和二叉树结构特点得到:
n 个结点的二叉树的路径长度不小于下述数列前 n 项的和，即其最小路径长度=PL
权值：在数学领域，权值指加权平均数中的每个数的频数，也称为权数或权重。
树的路径长度：树根到每个结点的路径长度之和。
树的路径长度可计算为对每一层:每层的节点数×（层数-1）的求和
结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度（Weighted Path Length, WPL）:叶子结点的带权路径长度之和。
主观上判断：权值最大的结点离根结点最近，权值最小的结点离根最远
Huffman树，又称为最优二叉树，是加权路径长度最短的二叉树。
应用:Huffman编码
详见参考文章
