一棵完全二叉树，共有n个结点，那么，其叶结点数共有( )个。

admin2016-03-29 20

问题一棵完全二叉树，共有n个结点，那么，其叶结点数共有( )个。

选项 A、n／2
B、n
C、(n-1)／2
D、(n+1)／2

答案D

解析此问题可以利用二叉树及完全二叉树的性质来求解。
设i、j、k分别为度为0、1、2的结点数目，则n=i+j+k。
根据二叉树的性质有i=k+1，即k=i-1，代入上式，得n=2i+j-1，即i=(n-j+1)／2。
由于完全二叉树中最多只有一个度为1的结点，同时考虑到i为整数，
(1)当j=0时，此时n=i+k=2k+1为奇数，则i=(n+1)／2；
(2)当j=1时，此时n=i+k+1=2k+2为偶数，则i=(n+1)／2向下取整。
所以选D。

转载请注明原文地址:https://kaotiyun.com/show/t2Ri777K

本试题收录于：计算机408题库学硕统考专业分类