在右路经上有r个节点的左式堆然有2^r-1个节点?

Question

今天在看数据结构的时候 看到左式堆时 有这个定理: 在右路经上有r个节点的左式堆必然有2^r-1个节点.
首先这个右路经是什么? 比如一个堆的右子树有两个子节点, 两个子节点又分别有两个子节点,那么这个右路经的节点数就是根节点+两个子节点+四个子节点的子节点, 还是说这个右路经的节点数就是右路经的长度?
这个该怎么理解呢?我怎么都想不明白.

Answer 1

右路径指的是根节+加根节点的右孩子+根节点的右孩子的右孩子。。。。
当 r==1时，只有一个根节点，符合条件
当 r==2时，根的右孩子有一个节点，根据左试堆的定义，显然根左孩子至少也因该有一个
当........
这个左式堆至少是以右路径为基准的满二叉树，而已知满二叉树的层数，即可知道节点总数