在任何 n 元素树中最多有天花板 (n/2^(h+1)) 个高度为 h 的节点

Question

参考来自 Intro to Algorithms, pg 157。图像有 10 个节点，树的高度为 3。

我的问题是当 h=1 时这如何成立？

天花板(n/2^(h+1))=天花板(10/2^(1+1))=天花板(10/4)=天花板(2.5)=3个节点。但是 h=1 有 4 个节点。

Answer 1

节点的高度是节点和叶子之间最长向下路径上的边数。

对于高度为 1 的二叉树，只能有根节点、左叶和右叶。那总共是3个。

在图像中，只有 2、16 和 3 是高度为 1 的节点。