神马品牌网爱尚电动车代理:请教两道计算机二级的公共基础题
来源：百度文库 编辑：神马品牌网 时间：2024/05/09 03:46:19
1 设树t的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。
则t中的叶子结点个数为？
2 设一棵完全二叉树共700个结点，则该二叉树中共有多少个叶子结点？
请写出分析过程,谢谢
则t中的叶子结点个数为？
2 设一棵完全二叉树共700个结点，则该二叉树中共有多少个叶子结点？
请写出分析过程,谢谢
第一题中，直接按照题的要求，画出一棵那样的树，数一下叶子的个数就行了。一个根结点分出四个分支（度为四的节点有一个），每个分支上有一个节点，继续在这四个节点上任选一个，分出三支（度为三的节点有一个），再选取当前的任意两个叶子节点分别画出两只（度为2的节点有两个），同样再选取当前的任意四个叶子节点分别画出一支（度为一的节点有4个），画完数一下有几个叶子节点就行了，应该是8个。
第二题，N层完全二叉树有2的N次幂－1个节点，而2的10次幂是1024，2的9次幂是512，所以700个节点的完全二叉树应该是一棵9层多而不满10层的二叉树，前八层没有叶子节点，第九层有部分叶节点，第十层都是叶节点。
先算出第9层共有多少个节点：2的（N-1）次幂，＝256。
在算出第十层有多少个节点：700－（2的9次幂－1）＝189
这189个节点，要占用第九层中的55个节点（189/2的取整+1）。也就是第九层只有256－55＝201个是没有被第十层中节点占用，是叶子节点，所以最后共有叶子节点201＋189＝390个叶子节点。
第二题 应该是350
你可以归纳
从简单的2、4、6……个结点的情况 得出一般的结论
第二题 350个