在有N个叶子节点的哈夫曼树中,其节点总数为（）?A、不确定B、2N-1C、2N+1D、2N

Question

在有N个叶子节点的哈夫曼树中,其节点总数为（）?
A、不确定
B、2N-1
C、2N+1
D、2N

Answer 1

如果这道题目里面的哈夫曼树是指二叉的话,那么答案是B,如果不确定是几叉的话,那么是A.
无论哈夫曼树是几叉,其特点是一致的（假设为m叉）,即树中只存在度为0的结点（即叶结点）和度为m的结点.不妨设度为0的结点个数为x,度为m的结点个数为y,则存在一个等式x+y=my+1,即x=(m-1)y+1,x+y是树的总结点个数.
就这道题来说,假设哈夫曼树是二叉的话,则度为0的结点个数为N,度为2的结点个数为N-1,则结点总数为2N-1.