——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。
树和森林与二叉树的转换
左孩子右兄弟表示法
二叉树和树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。任何一棵和树对应的二叉树，其右子树必为空。所以具有n个结点的不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同（因为具有n个结点的无右子树的二叉树的形态数与其具有n-1个结点的左子树的形态数相同）。若将森林中第二棵树的根结点看成第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。
森林必须转换为对应的二叉树使用二叉链表存储；
树可以（也可以不）转换为对应的二叉树使用二叉链表存储。
树和森林的遍历
树的两种遍历方法：
1）先序（根）遍历
a)访问树的根结点（在开始访问）；
b)依次先根遍历（递归定义）根的每棵子树。
2）后序（根）遍历
a)依次后根遍历（递归定义）根的每棵子树；
b)访问树的根结点（在最后访问）。
（树无中序遍历，因为树的根的子树数可以任意多）
树的先序遍历和后序遍历即为对应的二叉树的先序遍历和中序遍历。（二叉树的先序遍历是先访问根结点（当前结点），再遍历该根节点的左子树，即先访问该二叉树的对应树的根结点（当前结点），再遍历该根结点的所有子树，即树的先序遍历。二叉树的中序遍历是先遍历根结点（当前结点）的左子树，再访问该根结点，即先遍历该二叉树的对应树的根结点（当前结点）的所有子树，再访问该根结点，即树的后序遍历。）
森林的两种遍历方法：
1）先序遍历
a)访问森林中第一棵树的根结点（在开始访问）；
b)先序遍历（递归定义）第一棵树中根结点的子树森林；
c)先序遍历（递归定义）除去第一棵树之后剩余的树构成的森林。
2）中序遍历
a)中序遍历（递归定义）森林中第一棵树的根结点的子树森林；
b)访问第一棵树的根结点（在中间访问）；
c)中序遍历（递归定义）除去第一棵树之后剩余的树构成的森林。
（森林无后序遍历，因为若后续遍历则每个根均在其孩子子树森林和兄弟森林全访问完后才能访问，这样一棵树在访问它的根和孩子森林之间被插入了另一棵树）
森林的先序遍历和中序遍历即为其对应的二叉树的先序遍历和中序遍历。
赫夫曼树（最优二叉树）
路径：从树中一个结点到另一结点之间的分支构成这两个结点之间的路径。
路径长度：路径上分支的数目称为路径的长度。
结点的路径长度：从该结点到树根之间的路径长度。
树的路径长度：从树根到每一结点的路径长度之和。
完全二叉树是树的路径长度最短（但不是唯一）的二叉树。（因为结点数相同时完全二叉树具有最小高度。）
结点的带权路径长度：从该结点到树根之间的路径长度与该结点上的权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和。
严格（或正则）m叉树：只含有度为0和m的结点的m叉树（由n=n0+ nm且n-1=m nm得n0=1+(m-1)nm，即结点总数为
，严格（或正则）二叉树的结点总数为
）。
赫夫曼树：又称最优树，是一类带权路径长度最小的树。
度为m的赫夫曼树：又称最优m叉树，只含有度为0和m的结点的赫夫曼树（为严格m叉树）。（一般所说的赫夫曼树指度为2的赫夫曼树，即最优二叉树。）
赫夫曼算法（即最优二叉树构造算法）
1）根据给定的n个权值{w1, w2,…, wn}构成n棵二叉树的集合F={ T1, T2,…, Tn }，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。
2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3）在F中删除这两棵树，同时将新得到的二叉树加入F中。
4）重复2）和3），直至F只含一棵树为止。这棵树便是赫夫曼树。
赫夫曼树为严格二叉树，即二叉树中无度为1的结点，因而具有n个叶子结点的赫夫曼树共有2n-1（n0+n1+ n2= n0+n2=2n0-1=2n-1）个结点。
（构造n个权值的度为m的赫夫曼树时，由于度为m的赫夫曼树需满足n0=1+(m-1)nm，即n-1=nm (m-1)，故在构造度为m的赫夫曼树之前需先添加(m-1)-[(n-1)%(m-1)]个权值为0的结点，然后按照构造最优二叉树的赫夫曼算法构造最优m叉树，只不过变为每次需选取m棵根结点的权值最小的树作为子树构造一棵新的m叉树。）
前缀编码：任意字符的编码都不是另一个字符的编码的前缀。
赫夫曼编码：赫夫曼编码是由以n种不同字符作为叶子结点，字符的出现频率作为该字符的权值的赫夫曼树得到的二进制前缀编码，即每个字符的赫夫曼编码为从树根到该字符对应的叶子结点的路径上的0和1的组合，其中左分支代表0，右分支代表1。（可以在构造赫夫曼树时令每次选择的最小的两个权值中的较小值为左子树，较大者为右子树。）
——可选择“【右上角···】→【在浏览器中打开】”进行横屏阅读。
