3.3.3 树和森林的遍历

1. 树的先根遍历

先根遍历的定义为：
(1). 访问根结点；
(2). 按照从左到右的顺序先根遍历根结点的每一棵子树。

2. 树的后根遍历

后根遍历的定义为：
(1). 按照从左到右的顺序后根遍历根结点的每一棵子树。
(2). 访问根结点；
根据树与二叉树的转换关系以及树和二叉树的遍历定义可以推知，树的先根遍历与其转换的相应二叉树的先序遍历的结果序列相同；树的后根遍历与其转换的相应二叉树的中序遍历的结果序列相同。因此树的遍历算法是可以采用相应二叉树的遍历算法来实现的。

3. 森林前序遍历

前序遍历的定义为：
(1). 访问森林中第一棵树的根结点；
(2). 前序遍历第一棵树的根结点的子树森林；
(3). 前序遍历去掉第一棵树后的子森林。

4. 森林的中序遍历

中序遍历的定义为：
(1). 中序遍历第一棵树的根结点的子树森林；
(2). 访问森林中第一棵树的根结点；
(3). 中序遍历去掉第一棵树后的子森林。
根据森林与二叉树的转换关系以及森林和二叉树的遍历定义可以推知，森林的前序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同

3.3 树的应用

3.4.1 等价类问题

3.4.2 哈夫曼树（最优二叉树）和哈夫曼编码

最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。

设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度。

根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。哈夫曼（Haffman）依据这一特点提出了一种方法，这种方法的基本思想是：
(1). 由给定的n个权值{W1，W2，...，Wn}构造n棵只有一个叶结点的二叉
树，从而得到一个二叉树的集合F＝{T1，T2，...，Tn}；
(2). 在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造
一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
(3). 在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加
入到集合F中；
(4). 重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要
建立的哈夫曼树。