4.5 树的应用★3◎3

　　4.5 树的应用★3◎3

　　1．树的计数
　　二叉树T1与T2相似是指：两者都为空树或者两者都不为空树，且它们的左右子树分别相似。
　　二叉树T1与T2等价是指：二者不仅相似，而且所有对应结点上的数据元素均相同。
　　设具有n个结点且互不相似的二叉树的数目为bn。一般情况下，一棵具有n(n≥1)个结点的二叉树可以看成由一个根结点、一棵具有i个结点的左子树和一棵具有n－i－1个结点的右子树组成，其中 0≤i≤n－1，由此可得递推公式如下：

　　对序列定义生成函数：（3-1）
　　根据之间的关系，得到方程：（3-2）
　　求解该方程，可得：（3-3）
　　对比公式（3-1）和公式（3-3）可知：

　　所以具有n个结点且互不相似的二叉树有棵。
　　由于树可以表示成无右子树的二叉树，所以具有 个结点形态不同的树的数目和具有个结点互不相似的二叉树的数目相同，为。
　　2．哈夫曼树
　　（1）基本概念
　　与哈夫曼树有关的概念如下：
　　 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
　　 路径长度：路径上分支的数目称为路径长度。
　　 树的路径长度：从树根到每一结点的路径长度之和。
　　 结点的带权路径长度：从该结点到树根之间的路径长度与该结点上权的乘积。
　　 树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记做：

　　最优二叉树或哈夫曼树：
　　假设有n个权值，构造一棵具有n个叶子结点的二叉树，每个叶子结点的权值为，则其中带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。
　　（2）哈夫曼树构造方法
　　步骤如下：
　　① 根据给定的n个权值构成n棵二叉树的集合，其中每棵二叉树中只有一个带权为的根结点，其左右子树均空。
　　②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
　　③在F中删除这两棵树，同时将新得到的二叉树加入F中。
　　④重复第②步和第③步，直到F只含有一棵树为止，这棵树便是哈夫曼树。
　　（3）哈夫曼编码
　　若要设计长短不等的编码，则必须任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。要设计总长最短的二进制编码应以n种字符出现的频率做权，设计一棵哈夫曼树，由此得到的二进制前缀编码称为哈夫曼编码。