设一棵完全二叉树共有699个节点，则在该二叉树中叶子节点数为？

这种体改怎么算啊？有什么公式吗？谢谢！

屈伟军 · 2018-4-30 02:06:47

一楼的答案是对的，但解释严重有问题。“完全二叉数中，没有度为1的结点。”这句话是错误的。

完全二叉树定义：
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。

完全二叉树叶子结点的算法：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2 ，就可根据完全二叉树的结点总数计算出叶子结点数。

因此叶子结点数是(699+1)/2=350

bbxxsslrf · 2018-4-30 02:06:48

350个
699＝N＋（N－1）

二叉树中的结点分为三种：
度为2，度为1，度为0。即这个结点有两个孩子结点，有一个孩子结点，没有孩子结点（叶结点）。
结点总数＝度为2的结点＋度为1的结点＋度为0的结点
在任意二叉树中，度为2的结点的数目比度为0的结点(叶结点)数目少一个。
例如，只有三个结点的二叉树，其度为2的结点数目为1（根结点），度为0的结点（叶结点）有两个。
      0
      ／ \
            0 0
完全二叉数中，没有度为1的结点。所以
结点总数＝度为2的结点＋度为0的结点
699＝N＋（N－1）

设一棵完全二叉树共有699个节点，则在该二叉树中叶子节点数为？

2 个回复

浏览过的版块