00
前言前面对树已经介绍了不少相关内容，从一棵普通的多叉树到二叉树，再到二叉搜索树，最后到上一篇推文的平衡二叉搜索树(AVL树)，而本文打算就之前了解过的内容进行一些知识上的补充，主要按照大学数据结构课程考试要求的内容进行补充，对这部分内容感兴趣的读者可以了解下。
本文只介绍一些知识点，内容不多，本文无任何代码部分。主要内容为
补充森林这一概念
二叉树表示森林与树
森林与树的遍历
Huffman树
01
森林这里补充一个森林的概念
m(m≥0)棵互不相交的树的集合
直接放示意图，看图就能理解了，图中四棵树组成森林。
02
二叉树表示森林与树树→二叉树用二叉树表示一棵树的方法，也称孩子兄弟表示法
一棵二叉树根结点的左子结点是它的第一个子结点，右子结点是它的下一个兄弟结点。
我们知道二叉树的每一棵子树也都是二叉树，所以它的每一棵子树也都遵循上述规定。
由这一规定我们可以知道，从整体来看，这棵二叉树必定没有右半支，即根结点没有右子结点，理由也很简单，根结点没有兄弟结点。
直接用示意图举例，转换过程按照规定进行，不难。
森林→二叉树刚才介绍的树到二叉树的转换，转换结果是没有右半支的，而森林转换为二叉树，如果森林中不止一棵树，那么转换结果是有右半支的。
先将森林中的每一棵树单独转换成二叉树，第一棵树的右子结点为第二棵树的根结点，第二棵树的右子结点为第三棵树的根结点，依此类推。
也很简单，不多解释，直接看示意图。图中用颜色对两棵树进行了区分。
二叉树→树、森林由二叉树恢复为树或森林，步骤与上述步骤正好相反，读者可用上面提供的两个示意图进行练习，这里不再过多解释。
03
森林与树的遍历我们先回顾下二叉树的三种遍历方式。详细解释查看推文《Python数据结构——树(二)》
先序遍历：根、左、右
中序遍历：左、根、右
后序遍历：左、右、根
树的遍历仿照这三个遍历，我们可以写出树的遍历如下。
先序遍历：先遍历根结点，再遍历所有子结点。
中序遍历
后序遍历：先遍历所有子结点，后遍历根结点。
这里我们说的树是普通的树，也就是多叉树，关于多叉树的中序遍历，由于子结点之间不分左右子结点，无法确定在访问完哪一个子结点后对根结点进行访问，然后再访问剩下的子结点，所以没有中序遍历。
补充内容如下
树的先序遍历结果，与树转换成二叉树后的先序遍历结果相同。
树的后序遍历结果，与树转换成二叉树后的中序遍历结果相同。
森林的遍历森林的遍历总结如下
先序遍历：与森林转换成的二叉树的先序遍历结果相同。
中序遍历：与森林转换成的二叉树的中序遍历结果相同。
后序遍历：森林无后序遍历。
补充一棵二叉树的先序遍历与中序遍历可以唯一确定这棵二叉树。
一棵二叉树的后序遍历与中序遍历可以唯一确定这棵二叉树。
上面两句话在前一篇推文有提到过，当时是用于验证最终生成的二叉树是否为AVL树。只需要把先序遍历与中序遍历结果输出，还原成一棵二叉树，再与我们手动构造的结果进行比对即可。
那么问题来了，为什么知道先序遍历与中序遍历，或后序遍历与中序遍历就可以唯一确定一棵二叉树呢？就算能够唯一确定一棵二叉树，又该如何由这两个遍历结果还原成二叉树呢？
先解决第一个问题，证明方法是数学归纳法，设二叉树有n个结点。证明步骤如下：
已知后序序列与中序序列，可以唯一确定一棵二叉树，证明步骤与上述步骤类似，不再证明。
接下来解决第二个问题，已知先序序列与中序序列如何还原成一棵二叉树。
还原过程其实与上述证明过程类似。
找出中序序列中与先序序列第一个元素相同的元素，作为根结点。
中序序列中位于根结点左侧的是左子树，位于根结点右侧的是右子树。
若左子树有k个结点，在先序序列中除根结点外的前k个结点构成左子树，其余结点构成右子树。
对每一棵子树重复执行上述步骤，直至还原出一棵完整的二叉树。
还原过程示意图如下。
另外，只知道先序序列和后序序列是无法唯一确定二叉树的。
04
Huffman树Huffman树又称最优二叉树。
先介绍几个概念。
结点路径：从树中一个结点到另一个结点，之间的分支构成这两个结点之间的路径。
路径长度：结点路径上的分支数目。
树的路径长度：从树根到每一个结点的路径长度之和。
结点的带权路径长度：从该结点到树的根结点之间的路径长度乘以结点的权值。
树的带权路径之和：树中所有叶子结点的带权路径长度之和。
接下来介绍Huffman树的定义
具有n个叶子结点(每个结点的权值为wi)的二叉树不止一棵，但在所有的二叉树中，必定存在一棵带权路径长度最小的树，称这棵树为Huffman树(或最优树)
构建Huffman树过程。
将n个带权叶子结点{w1,w2,...,wn}作为树{T1,T2,...,Tn}
选取两棵权值最小的树作为左右子树，构建一棵新的二叉树，新二叉树的权值为左右子树权值之和
集合中移除这两棵子树，将新生成的二叉树添加进集合
重复步骤2、步骤3，直至集合中只剩下一棵树。
由于每次构造新二叉树时，两棵子树并没有规定哪一棵作为左子树，哪一棵作为右子树，所以最终会出现构造结果不唯一的情况。
在这里我们可以自己按照一定的规则构造，下面这条规则可以不遵守，仅是为结果更加规范。
以权值小的为左子树，权值相等时以深度小的为左子树。
构造过程示意图如下：
Huffman编码则是以字符集作为叶子结点，字符出现频度作为权值，构造生成一棵Huffman树，树的左分支代表“0”，右分支代表“1”，这样从根结点到叶子结点所经历的路径分支上的“0”和“1”组成的字符串，作为该叶子结点所代表的字符的编码。
在最后Lastbutnotleast
本文补充介绍了森林这一概念，同时介绍了如何用二叉树表示普通的树与森林，以及关于树和森林的遍历方法，在最后介绍了一种最优树——Huffman树。
文中内容以概念为主，内容并不难，难理解一点的地方也都有示意图辅助理解，有部分地方用到之前介绍过的概念，不太熟悉的读者可以点下方链接阅读往期关于树的推文。
往期精彩回顾Python数据结构——树(二)
Python数据结构——树(三)
Python数据结构——树(四)
预览时标签不可点收录于话题#个上一篇下一篇