在右路经上有r个节点的左式堆然有2^r-1个节点?
今天在看数据结构的时候 看到左式堆时 有这个定理: 在右路经上有r个节点的左式堆必然有2^r-1个节点.
首先这个右路经是什么? 比如一个堆的右子树有两个子节点, 两个子节点又分别有两个子节点,那么这个右路经的节点数就是根节点+两个子节点+四个子节点的子节点, 还是说这个右路经的节点数就是右路经的长度?
这个该怎么理解呢?我怎么都想不明白.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
右路径指的是根节+加根节点的右孩子+根节点的右孩子的右孩子。。。。
当 r==1时，只有一个根节点，符合条件
当 r==2时，根的右孩子有一个节点，根据左试堆的定义，显然根左孩子至少也因该有一个
当........
这个左式堆至少是以右路径为基准的满二叉树，而已知满二叉树的层数，即可知道节点总数