由于树和二叉树都可以用二叉链表作为存储结构，因此可以以二叉链表为媒介导出树与二叉树的一个对应关系，即给定一棵树，可以找到唯一一颗二叉树与之对应。从物理结构上看它们是二叉链表，只是解释不同。
「转换的规则：左孩子右兄弟」
树转化为二叉树根据树与二叉树“左孩子右兄弟”的转换规则，将森林转换为二叉树的过程如下:①将每棵树的根结点也视为兄弟关系，在兄弟结点之间加一连线。②对每个结点，只保留它与第一个子结点的连线，与其他子结点的连线全部抹掉。③以树根为轴心，顺时针旋转45°。
简单来说，就是讲每棵树的根节点也看做是兄弟关系，然后根据左孩子右兄弟规则转化。结果如下图所示。
森林转化为二叉树下图为二叉树转化为森林，转化的规则也是左孩子右兄弟。对于二叉树根节点的右孩子，转化为森林相邻的另一颗树的根节点。
二叉树转化为森林需要注意的是：
若F是一个森林，B为对应的二叉树，有以下结论：
若F有n个非终端结点，则树B中右指针域为空的结点有n+1个。（根据森林与二叉树转换规则“左孩子右兄弟”。二叉树B中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，故树B中右指针域为空的结点有n+1个。）F中叶结点的个数为，B中左孩子指针为空的节点个数（既然是叶结点，必然没有孩子，根据左孩子右兄弟，对应二叉树的左孩子指针为空的节点必为树中叶结点）此外，在树中有一个很重要的性质，即在n个结点的树中有n-1条边。由此可以得出：若森林中有25个结点、15条边，那么森林中树的个数为25-15=10棵树。
2.树、森林的遍历对于树和森林的遍历，最简单的方法就是先把树和森林转化为对应二叉树，之后就将对树和森林的遍历转化为对二叉树的遍历。
2.1树的遍历以下图为例
先根遍历（对应二叉树：先序遍历）（深度优先遍历）遍历过程：
ABCDA(BEF)(CG)(DHIJ)A(B(EK)F)(CG)(DHIJ)
代码：
//伪代码voidPreOrder(TreeNode*R){if(R!=NULL){visit(R);while(R还有下一棵树T)PreOrder(T);}}后根遍历（对应二叉树：中序遍历）（广度优先遍历）
遍历过程：
BCDA(EFB)(GC)(HIJD)A((KE)FB)(GC)(HIJD)A
代码：
//伪代码voidPostOrder(TreeNode*R){if(R!=NULL){while(R还有下一棵子树T)PreOrder(T);visit(R);}}
层次遍历（用队列）（广度优先遍历）（类似于二叉树的层次遍历）
①若树非空，则根节点入队②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队③重复②直到队列为空
如图：
2.2森林的遍历以下图为例：
森林先序遍历（对应二叉树：先序遍历）（等同于依次对各个子树进行先根遍历）
①访问森林中第一棵树的根结点。②先序遍历第一棵树中根结点的子树森林。③先序遍历除去第一棵树之后剩余的树构成的森林。
遍历过程：
BCD(BEF)(CG)(DHIJ)(B(EKL)F)(CG)(D(HM)IJ)
中序遍历（对应二叉树：中序遍历）（等同于依次对各个子树进行后根遍历）
中序遍历森林中第一棵树的根结点的子树森林。访问第一棵树的根结点。中序遍历除去第一棵树之后剩余的树构成的森林。
遍历过程
BCD(EFB)(GC)(HIJD)((KLE)FB)(GC)((MH)IJD)3.哈夫曼树与哈夫曼编码3.1哈夫曼树的定义
节点的权：每个节点赋予一个数值，代表节点的权值
节点的带权路径长度：从树的根节点到该节点的的路径长度（或经过的边数）乘节点的权值
树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和
哈弗曼树：在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。
例如：
上图3棵树带权路径长度（WPL）分别为：
(a)WPL=7x2+5x2+2x2+4x2=36。
(b)WPL=4x2+7x3+5x3+2x1=46。
(c)WPL=7x1+5x2+2x3+4x3=35。
其中，c的WPL最小，所以c是一颗哈夫曼树。
3.2哈夫曼树的构造哈夫曼树的构造过程如图所示：
哈夫曼树的构造过程简言之，就是每次将节点中权值最小的两个节点作为树的左右子树，并且将新结点的权值设为左、右子树上根结点的权值之和。同时将新得到的树加入节点堆中。重复这一步骤直到构成一颗树。
「哈夫曼树有以下几个结论：」
1）每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
2）哈夫曼树的结点总数为
3）哈夫曼树中不存在度为1的结点。由此可得，若一颗哈夫曼树有n个结点，则可有（n+1）/2种不同的编码
4）一棵度为m的哈夫曼树应只有度为0和m的结点，
5）哈夫曼树并不唯一，但WPL必然相同且为最优。
3.3哈夫曼编码「编码分为固定长度编码和可变长度编码」
在数据通信中,若对每个字符用相等长度的二进制位表示，称这种编码方式为「固定长度编码」。若允许对不同字符用不等长的二进制位表示，则这种编码方式称为「可变长度编码」。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
为了使编码可以被唯一翻译，通常使用「前缀编码」：没有一个编码是另一个编码的前缀，则称这样的编码为「前缀编码」。例如：
A：0B：C：
A，B，C的编码中没有一个一个编码是另一个编码的前缀，这样对于码串：
001可以对应翻译为AABCA
若将D编码设计为：00，此时0是00的前缀，就会产生歧义，无法唯一翻译：
001可以对应翻译为AABCA也可以翻译为DBCA
将字符作为叶结点，将字符出现的频次作为权值，构造哈夫曼树，即可得「哈夫曼编码」。（用于数据压缩）
哈夫曼编码的构造：
利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树从根节点开始，为到每个叶子节点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子节点的编码.（注意:0和1究竟是表示左子树还是右子没有明确规定。所以构造出的哈夫曼树并不唯一。）例如：
各字符权值为：a:45b:13c:12d:16e:9f:5
构造的哈夫曼树为：
对应编码为：a:0b:c:d:e:1f:1
这棵树的WPL为：
WPL=1x45+3x(13+12+16)+4x(5+9)=
此处的WPL可视为最终编码得到二进制编码的长度，共位。若采用3位固定长度编码，则得到的二进制编码长度为位，因此哈夫曼编码共压缩了25%的数据。
预览时标签不可点收录于话题#个上一篇下一篇