问答题
试证明一棵二元完全树必有奇数个结点.
【正确答案】
方法一:设二元完全树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为奇数.
【答案解析】
本题可根据二元完全树的特点,树和图中边、结点的关系,经综合考虑得出结论。
提交答案
关闭