大话数据结构-树(11) _前序遍历

前序遍历结果为，后序遍历结果为。
把此树转化为一棵二叉树，如下：
对其进行前序遍历，结果为，与森林的前序遍历结果相同；对其进行中序遍历，结果为，与森林的后序遍历结果相同。
因此有结论：
(1) 森林的前序遍历，是从第一棵树开始，使用先根遍历（根->左->右）方法遍历后，再串起来；
(2) 森林的后序遍历，是从第一棵树开始，使用后根遍历（左->右->根）方法遍历后，再串起来；
(3) 森林的前序遍历，与其转化为二叉树后的前序遍历结果相同；
(4) 森林的后序遍历，与其转化为二叉树后的中序遍历结果相同；
7.7 赫夫曼树
赫夫曼编码，是最基本的压缩编码方法。赫夫曼编码基于赫夫曼树，赫夫曼树是由赫夫曼（David ，或称哈夫曼）于1952年发明赫夫曼编码时使用的特殊的树。
7.7.1 路径长度和带权路径长度
从根结点到某结点之间的线的数量称为路径长度，所有结点的路径长度之和为树的路径长度。
如下二叉树：
以J结点为例， A结点作为根结点，要走到J结点，需要走四条线，因此J结点的路径长度为4：
各结点的路径长度为：
(1) A结点为根结点，其路径长度为0；
(2) A结点要到B结点，只有需要走一条线，因此B结点的路径长度为1；
(3) A结点要到C结点，只有需要走一条线，因此C结点的路径长度为1；
(4) A结点要到D结点，要走两条线，因此D结点的路径长度为2；
(5) A结点要到E结点，要走两条线，因此E结点的路径长度为2；
(6) A结点要到F结点，要走两条线，因此F结点的路径长度为2；
(7) A结点要到G结点，要走三条线，因此G结点的路径长度为3；
(8) A结点要到H结点，要走三条线，因此H结点的路径长度为3；
(9) A结点要到I结点，要走三条线，因此I结点的路径长度为3；
(10) A结点要到J结点，要走四条线，因此J结点的路径长度为4；
因此，此二叉树的路径长度为1+1+2+2+2+3+3+3+4=21 。
若二叉树的每一个结点都有一个权值，这棵二叉树称为带权二叉树，如下所示：
带权二叉树的结点的路径长度称为带权路径长度，带权路径长度为路径长度乘以权值，如上图中，结点J的路径长度为4 ，权值为6 ，因此结点J的带权路径长度为4*6=24 。
相应的，二叉树的带权路径长度为所有结点的带权路径长度之和，因此此二叉树的带权路径长度为：
15+11+24+25+23+36+37+39+4*6=120 。
带权路径长度也称为WPL 。
7.7.2 定义
假设有n个权值{w1、w2、w3…wn} ，构造一棵有n个结点的二叉树，每个叶子结点带权wk ，每个叶子的路径长度为lk ，则构建出的WPL ，即带权路径长度最小的二叉树，称为赫夫曼树，也称最优二叉树。
构造赫夫曼二叉树的步骤，以以上树为例，为：
(1) 把所有带权结点及其权值放到一个集合中，即FX={B-5, C-1, D-4, E-5, F-3, G-6, H-7, I-9, J-6}；
(2) 先建一个只有根结点N1的树，然后令FX中，权值最小的结点为N1的左结点，权值第二小的结点为N1的右结点，如下所示：