问题 单项选择题

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

A.2n

B.2n-1

C.2m+1

D.2n+2

答案

参考答案:B

解析:本题考查数据结构基础知识。 二又树具有以下性质:度为2的结点(双分支结点)数比度为0(叶子结点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知,最优二叉树中只有度为2和0的结点,因此,其结点总数为2n-1。

单项选择题
单项选择题