设一棵非空完全二叉树T的所有叶结点均位于同一层,且每个非叶结点都有2 个子结点。若 T有 k个叶结点,则T的结点总数是()。
A. 2k-1 B. 2k C. k^2 D. 2^k-1
A
方法一:推理
因为...
用户登录可进行刷题及查看答案
因为每个非叶结点都有2个子结点,所以二叉树T只有度为0和度为2的结点,可得:
n0=k
n0=n2+1
n=n0+n2
解得 n=2k−1 。
本题选A。
方法二:画图举例
一棵非空完全二叉树T的所有叶结点均位于同一层,且每个非叶结点都有2个子结点。可得这棵二叉树为满二叉树。
直接画出一个高度为3的满二叉树。
k=4,n=7 可得 n=2k−1 。
登录后提交答案
暂无评论,来抢沙发