计算二叉树节点数

Question

是否可以计算有多少个节点有任意的二叉树？每叶的叶数和深度是已知的（实际上它是霍夫曼树）。

我需要它以便能够在实际构建树之前为树分配所需的内存并避免以后的内存重新分配。

Answer 1

霍夫曼树是full binary tree，即树中的每个节点都有0或2个孩子。在这种情况下，你需要k个叶子的k - 1个内节点。所以节点的总数是2k - 1。