问题 填空题

设一棵完全二叉树共有839个结点,则在该二叉树中有______个叶子结点。

答案

参考答案:420

解析: 一般二叉树有一个性质;在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。
在根据完全二叉树的定义,在一棵完全二叉树中,最多有1个度为1的结点。
综合以上两点可以得到如下结论:
设一棵完全二叉树具有n个结点。如果n为偶数,则在该二叉树中有n/2个叶子结点以及n/2-1个度为2的结点,还有1个是度为1的结点;如果n为奇数,则在该二叉树中有[n/2]+1个叶子结点以及[n/2]个度为2的结点,没有度为1的结点。
在本题中,完全二叉树共有839个结点,839是奇数,因此,在该二叉树中有420个叶子结点以及419个度为2的结点,没有度为1的结点。

单项选择题
单项选择题