一棵完全二叉树，结点总数为1001，求它的叶子结点总数，度为2的结点总数，有多少个结点只有非空左子树，有多少个结点只有非空右子树？_一棵完全二叉树有1001个结点,其中叶子结点的个数为

作者：cp456 | 2024-01-31 12:46:09

踩

一棵完全二叉树有1001个结点,其中叶子结点的个数为

总结以下两种理解方式：
1.完全二叉树的最后一个结点的编号是n，则它的父结点的编号为[n/2]，则叶子结点个数为n-[n/2]。
结点数为奇数,所以度为1的结点有0个;所以非空左子树为0;非空右子树为0;

完全二叉树的最后一个结点的编号一定是1001，则它的父结点的编号为1001/2=500，则叶子结点个数为1001-500=501.非空左子树为0;非空右子树为0;

2.结点数为奇数,所以度为1的结点有0个,度为2的节点数=度为0的节点数-1,所以2*度为0的节点数-1 = 1001,所以度为0的节点数为501

n0 = n2 + 1，代入n0 + n1 + n2 = 1001得到2n2 + 1+ n1 = 1001,
n1只能是0或者1，为满足2n2 + 1 + n1 = 1001，必须n1 =0，因此n2 = 500,所以n0 = 501，即叶子个数是501个

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50372