【单选题】设哈夫曼树中有199个结点,则该哈夫曼树中有( )个叶子结点。

设哈夫曼树中有$n$个结点，其中叶子结点有$m$个，非叶子结点有$k$个，则根据哈夫曼树的性质可得：

$$
n=m+k-1
$$

又因为哈夫曼树是一棵二叉树，所以每个非叶子结点都有两个孩子，因此有：

$$
2k=m
$$

将第二个式子代入第一个式子中，得到：

$$
n=\frac{3}{2}m-1
$$

代入$n=199$，可得：

$$
m=133
$$

因此，该哈夫曼树中有133个叶子结点。答案选项为B。

相关问题

为什么有n个叶子结点的哈夫曼树有2n-1个结点

哈夫曼树是一种带权路径长度最短的树，其中每个叶子结点都有一个权值。构建哈夫曼树的过程是，每次从权值最小的两个结点中选取一个作为左子树，另一个作为右子树，将它们合并成一个新的结点，新结点的权值为左右子树的权值之和。重复这个过程，直到最后只剩下一个根节点。

由于每次合并都会新增一个结点，所以n个叶子结点的哈夫曼树一共需要进行n-1次合并，最终得到一个根节点，因此树中的结点数为n-1+1=n。

另外，由于每个新结点的权值都是左右子树权值之和，因此可以证明，最小带权路径长度为WPL等于所有叶子结点的权值之和。因此，n个叶子结点的哈夫曼树的最小带权路径长度为WPL，而树中的所有非叶子结点都是由两个叶子结点合并得到的，所以树中共有2n-2个非叶子结点。将叶子结点和非叶子结点的数量相加，即可得到哈夫曼树的总结点数为2n-2+n=2n-1。

现有一棵哈夫曼树，其共有211个结点，则其存在多少个叶子结点?

在一棵哈夫曼树中，每个叶子结点对应一个字符或符号，因此叶子结点的个数就是字符或符号的个数。

根据哈夫曼树的性质，它是一棵最优二叉树，即具有最小带权路径长度（WPL）。每个非叶子结点都有两个子结点，而叶子结点没有子结点。

根据哈夫曼树的定义，一棵哈夫曼树共有n个叶子结点和n-1个非叶子结点。因此，如果一棵哈夫曼树共有211个结点，那么它的叶子结点个数就是211-1=210个。