有m个叶结点的霍夫曼树,其结点总数是__________。

Question

有m个叶结点的霍夫曼树，其结点总数是__________。

Answer 1

正确答案：
2m-1
霍夫曼树是一个扩充二叉树。它的外部结点数是原来结点数加上1，因此，具有m个叶结点的霍夫曼树，即外部结点数是m，它原来结点数是m-1，所以总结点数是2m-l。