结构推理
试证明一棵完全二叉树必有奇数个结点.
【正确答案】
分析 本题可根据完全二叉树的特点、树、图中边、结点的关系,经综合考虑得出结论.
证明 方法一:设完全二叉树T有n个结点,m条边.依定义,T中每个分枝点都关联两条边,所以m必为偶数.
又因为T是树,有n=m+1,故n为奇数.
因此,完全二叉树必有奇数个结点.
方法二:设完全二叉树T有n个结点,L片叶子,b个分枝结点,则有
n=L+b及b=L-1,
所以n=L+b=L+L-1=2L-1.
即n为奇数.
【答案解析】
提交答案
关闭