什么是哈夫曼树？简述哈夫曼编码过程。试证明有n个叶子的哈夫曼树共有2n-1个结点。
答哈夫曼树又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。[br][/br]哈夫曼编码过程：[br][/br]（1）根据给定的n个权值{[tex=7.357x1.286]Thc0U1FCnSWhvW69d+w7ntWrU0v8XVdYRW/QY3GLNcE=[/tex]}构成n棵二叉树的集合[tex=8.214x1.357]NKhyxXnIBeQiZ0lbj+cphfMGc3US8/JR3dWxYlq+T6w=[/tex]，[br][/br]其中每棵二叉树[tex=5.714x1.357]RNu03/H0E+jj6DU58lg8FA==[/tex]都只有一个权值为wi的根结点，其左右子树均为空。[br][/br]（2）在F中选出两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新树根结点的权值为其左、右子树根结点的权值之和。[br][/br]（3）从F中删除这两棵树，同时将新得到的二叉树加入F中。[br][/br]（4）重复第（2）步和第（3）步，直到F中只含有一棵树为止，此树便是哈夫曼树。[br][/br]证明有n个叶子结点的哈夫曼树共有2n-1个结点。[br][/br]证明：因为哈夫曼树为二叉树，设其分支结点数为n，由二叉树的性质：二叉树终端结点数等于双分支结点数加1，哈夫曼树中的分支结点都为双分支结点（此处可由哈夫曼算法得出），[br][/br]所以n=n1+1[br][/br]n1=n-1[br][/br]哈夫曼树共有[tex=9.571x1.214]j3aiAErr1m6XkLhOtjt79SeDfq2aLoCuo/p1anLMKKk=[/tex]个结点。
举一反三
内容
- 0
【填空题】设哈夫曼树中共有n个结点,则该哈夫曼树中有__ __ _个度数为1的结点。则该树中有__ 个叶子结点
- 1
用给定的n个权值构造哈夫曼树,则该哈夫曼树共有()个结点。 A: n B: 2n C: 2n-1 D: 2n+1
- 2
【填空题】设哈夫曼树中共有n个结点,则该哈夫曼树中有()个度数为1的结点
- 3
设哈夫曼树中有100个叶子结点，则该哈夫曼树中共有 个结点。
- 4
设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点