问题
单项选择题
在有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。
在有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。