binary-tree - 树的高度是相对于节点还是路径？

Question

在三星技术测试中，有人问这个说法是否属实：

二叉树中的最大节点数为2^(h+1)-1，其中h是树的高度。

我认为这是错误的，因为根据 Schaum 的系列 TMH 高度定义为到达叶子之前的最大节点数。

正确与否？

score 2 · Accepted Answer

陈述是正确的。一棵零高度的二叉树最多有一个节点，一棵高度为 1 的树最多有 3 个节点，以此类推。

score 1 · Accepted Answer

没错，当每个节点有两个孩子时，达到最大数量 - 所以我们有 2 的幂。只需在每个级别绘制所有叶子的树，您就会看到公式。

score 1 · Accepted Answer

定义二进制高度有两种约定
1) 从根到叶的最大节点数
2) 从根到叶的最大边数

请参考以下文章

score 1 · Accepted Answer

1

根据这篇维基百科文章，该声明是正确的

于 2013-10-02T14:21:41.770 回答

4 回答 4