非完全二叉树高度与深度的关系及CLRS堆节点公式疑问

问题1：不同深度的节点是否可以拥有相同的高度？ #

完全可以。举个具体的例子：

• 堆最底层（深度为H）的节点，因为没有子节点，高度都是0。
• 当堆不是完全二叉树时，深度为H-1的部分节点可能没有子节点（底层未填满导致这些节点没有左右孩子），它们的高度同样是0。
  这就出现了深度为H和深度为H-1的节点拥有相同高度（0）的情况。再延伸一步：如果堆高度H=3，深度为2的某个节点没有子节点，它的高度是1；而深度为1的某个节点如果子树高度为0，它的高度也是1——这同样是不同深度节点共享同一高度的场景。

问题2：堆的叶子节点数为N/2，与上述内容是否有关联？ #

二者直接紧密关联：

• 叶子节点的本质就是高度为0的节点。根据你提到的CLRS结论，高度为h的节点最大数量公式为N/2^(h+1)，当h=0时，计算结果正好是N/2（实际是⌈N/2⌉或⌊N/2⌋，和堆叶子节点数的表述一致）。
• 结合你说的非完全二叉堆场景：底层（深度H）的节点都是高度0的叶子，深度H-1中没有子节点的节点也属于高度0的叶子，这些节点的总数正好对应“叶子节点数为N/2”的结论。
• 简单来说，CLRS中关于高度h的节点数量公式，当h=0时，就是堆叶子节点数的推导依据。

内容的提问来源于stack exchange，提问作者neelanchaljain