2. 计算机
  3. 设一棵完全二叉树共有839个结点，则在该二叉树中有______个叶子结点。

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

admin2010-12-16  73
问题 设一棵完全二叉树共有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的结点。
转载请注明原文地址:https://www.kaotiyun.com/show/6mVp777K
本试题收录于： 二级C题库NCRE全国计算机二级分类
0

二级C

NCRE全国计算机二级

相关试题推荐
随机试题
最新回复(0)