哈夫曼树和哈夫曼编码

　　(1)路径长度：在二叉树中，从根到任意一个后裔结点的路径长度是指从根结点到该后裔结点的路径上所包括的边的数目。

　　二叉树的内路径长度：从根到其它所有分支结点的路径长度之和。

　　二叉树的外路径长度：从根到其它所有叶子结点的路径长度之和。

　　二叉树的加权路径长度：二叉树中所有叶子结点的加权路径长度之和。

　　(2)哈夫曼树和哈夫曼算法

　　最优二叉树：具有最小加权路径长度的二叉树。

　　哈夫曼算法：由哈夫曼给出、用于构造最优二叉树的算法。

　　a.用给定的一组权值{w1,w2 ,…,wn}，生成一个有n棵二叉树组成的集合 F={T1，T2，…，Tn}，其中，每棵二叉树Ti只有一个结点，即权值为wi的 根结点。

　　b.从F中选择两棵根结点权值最小的二叉树，作为新二叉树根的左、右子树， 新二叉树根的权值是左、右子树根结点的权值之和。

　　c.从F中删除这两棵二叉树，另将新二叉树加入F中。

　　d.重复(2)和(3)，直到F中只包含一棵二叉树为止。

　　哈夫曼树：用哈夫曼算法构造的最优二叉树。

　　(3)哈夫曼编码

　　哈夫曼树的每个叶结点对应一个字符。在从哈夫曼树的每个结点到其左孩子的边上标上1。将从根到每个叶子的路径上的数码连接起来，就是该叶子所代表的字符的编码。

　　第五单元 第六单元 第七单元

　　以上是小编为大家整理分享的“2022考研计算机数据结构：哈夫曼树和哈夫曼编码”相关内容，希望对大家有帮助。祝大家考上理想的院校