一棵完全二叉树有500个结点 请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度
结点,叶子,正确答案
已帮助 人
一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。【东南大学2004一、1(5分)】
请帮忙给出正确答案和分析，谢谢！
-
正确答案：二叉树度为2的结点n2和度为0的结点n0间有关系式n2=n0-1且完全二叉树中度为1的结点n1至多为1由上述关系得知完全二叉树结点间的公式n=2n0+n1-1。故当n=500时n0=250n1=1n2=249;n=501时n0=251n1=0n2=250。
二叉树度为2的结点n2和度为0的结点n0间有关系式n2=n0-1,且完全二叉树中度为1的结点n1至多为1,由上述关系得知完全二叉树结点间的公式n=2n0+n1-1。故当n=500时,n0=250,n1=1,n2=249;n=501时,n0=251,n1=0,n2=250。