《数据结构》完全二叉树的叶子数讨论
发布时间：2021-04-03 13:45:56 所属栏目：安全 来源：网络整理
导读：? ? ?完全二叉树是一种很特别的树，很多性质和特性值得我们关注。下面，就来关注一下叶子数目。 ? ? 如果一树是是完全二叉树， 结点数为n,叶子是多少呢？ 现设结点总数为n，度为2和0结点数分别为n2和n0。下面讨论叶子数目。即计算 n0值。 ? ? ?我们根据完全
|
? ? ?完全二叉树是一种很特别的树，很多性质和特性值得我们关注。下面，就来关注一下叶子数目。 ? ? 如果一树是是完全二叉树，结点数为n,叶子是多少呢？现设结点总数为n，度为2和0结点数分别为n2和n0。下面讨论叶子数目。即计算n0值。 ? ? ?我们根据完全二叉树的概念，可以知道，完全二叉树有两种可能： ? ? ? ? 1.一种是：没有度为1的结点，只有度为2和0的结点 ? 此时有： ? ? ? ? ? ? ? ? ??n=n2+n0 ?（1）? ? ? ? ? ? ? ?根据二叉对性质知：?n0=n2+1 ? ?（2) ? ? ? ? ? ? ?联立（1）和（2）得： n0=n+1/2? ? ? ?? ? ? ?2.一种是：有1个度为1的结点，其它度为2和0. ? ? ? ? ? ? ?此时有： ? ? ? ? ? ? ? ? ? ?? n= n2+ n0+1 ? （1） ? ? ? ? ? ? ?根据二叉对性质知：? n0= n2+1 ? ? （2) ? ? ? ? ? ? ? ?联立（1）和（2）得： n0=n/2 ? ? ? ? 再进一步?分析上面两种答案，我们知道，完全二叉树叶子只能出现在最后两层。也就是说，如果共 有k+1层，则前k层一定是满树，对于满树知道结点数为2的k次方减1，为奇数。 ? ? ? ? ?对于情况1，第k+1层是偶数个叶子。所以，情况1，n一定为奇数。 ? ? ? ? ?对于情况2，第k+1层是奇数个叶子，所以，情况2，n一定为偶数。 ? ? ? ?因此得出结论，对于结点数为n的完全二树，叶子数目是： ? ? ? ? ?当n为奇数时：n0=n+1/2 ? ? ? ? ?当n为偶数时：n0=n/2 （编辑：辽源站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |