算法导论附录B B.5

编程入门行业动态更新时间:2024-10-13 18:24:33

算法<a href=https://www.elefans.com/category/jswz/34/1767094.html style= 导论附录B B.5"/>

一棵满二叉树的内路径长度是指所有内部结点深度之和。类似地，外路径长度是指所有叶结点的深度之和。考虑一个有n个内部结点的满二叉树，其内路径长度为i，外路径长度为e。证明e = i + 2n.

证明：先考虑不同深度节点的内部结点和叶结点数量，不妨设树最大深度为d，有：

不难看出每层中的内部结点与叶结点数量和与上一层的内部节点数量有关，即：

内路径长度i，外路径长度e分别为各深度结点数乘以对应深度之和，即：

不难看出（因为，，数值上均为0，变换看着可能有点别扭）：

因此

更多推荐

算法导论附录B B.5

本文发布于:2024-03-12 01:44:21，感谢您对本站的认可！

导论附录算法

评论列表（有 0 条评论）

算法导论 附录B B.5