问题 单项选择题

在有n个子叶节点的哈夫曼树中,其节点总数为 (39)

A.不确定

B.2n-1

C.2n+1

D.2n

答案

参考答案:B

解析: 哈夫曼树是最优二叉树,它是一类带权路径长度(WPL)最短的树。二叉树结点总数为:M= N0+N1+N2(N0、N1、N2分别表示度为0、1、2的结点)。哈夫曼树在构建过程中,没有度为1的结点且有 N0=N2+1,故M=2N0-1,这里N0=n。

名词解释
单项选择题