问题
单项选择题
若用n个权值构造一棵最优二又树(哈夫曼树),则该二叉树的结点总数为______。
A.2n
B.2n-1
C.2m+1
D.2n+2
答案
参考答案:B
解析:本题考查数据结构基础知识。 二又树具有以下性质:度为2的结点(双分支结点)数比度为0(叶子结点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知,最优二叉树中只有度为2和0的结点,因此,其结点总数为2n-1。
若用n个权值构造一棵最优二又树(哈夫曼树),则该二叉树的结点总数为______。
A.2n
B.2n-1
C.2m+1
D.2n+2
参考答案:B
解析:本题考查数据结构基础知识。 二又树具有以下性质:度为2的结点(双分支结点)数比度为0(叶子结点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知,最优二叉树中只有度为2和0的结点,因此,其结点总数为2n-1。