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

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

admin2016-03-29  56
问题 一棵完全二叉树，共有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题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)