若用n个权值构造一棵最优二叉树(哈夫曼树),则该二叉树的结点总数为(59)。A.2nB.2n－1C.2n＋lD.2n＋2

Question

若用n个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的结点总数为(59)。

A．2n

B．2n-1

C．2n+l

D．2n+2

Answer 1

正确答案：B
解析：对任何一颗二叉树T，如果其终端结点数为n，度为2的结点数为m，则n=m+l。而哈夫曼树的结点度为0或2，而度为0的结点是n，所以度为2的结点数是n-l，因此总结点数为2n-1。