设一棵完全二叉树共有500个结点,则在该二叉树中有【 】个叶子结点。

admin2009-03-15  21

问题 设一棵完全二叉树共有500个结点,则在该二叉树中有【  】个叶子结点。

选项

答案250。

解析 由于是一棵完全二叉树我们可以推算出其各层上的结点数目与总层数。设其为n层,则其n-1层为满二叉树,结点总数目为:2n-1-1<500,所以最大解n=9,并且其n-1层为满二叉树,总结点数目为2n-1-1=255,所以第n层结点数目500-255=245,并且全部为叶子结点。n-1层结点数目2n-2=128,其中有128-[(245+1)/2]=5个叶子结点。所以叶子结点为250(245+5)。
转载请注明原文地址:https://kaotiyun.com/show/NG7Z777K
0

最新回复(0)