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

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

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

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