返回主页
已有17条笔记
[数据结构 P1501] 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2 个子结点。若 T有 k个叶结点
未通过
设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2 个子结点。若 T有 k个叶结点，则T的结点总数是（）。
A. 2k-1 B. 2k C. k^2 D. 2^k-1
上面问题的答案是：
加入错题本
个人笔记
A
方法一：推理
因为...
用户登录可进行刷题及查看答案
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 。
本题选A。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发