【VFP】关于计算二叉树叶子结点的问题有填空题如下：设一棵完全二叉树共有700个结点,则该二叉树中有______个叶子结点?我对二叉树的各种计算还是很模糊,特别是遇到这种稍微变通复杂的题
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/17 17:43:50
【VFP】关于计算二叉树叶子结点的问题有填空题如下：设一棵完全二叉树共有700个结点,则该二叉树中有______个叶子结点?我对二叉树的各种计算还是很模糊,特别是遇到这种稍微变通复杂的题
【VFP】关于计算二叉树叶子结点的问题
有填空题如下：
设一棵完全二叉树共有700个结点,则该二叉树中有______个叶子结点?
我对二叉树的各种计算还是很模糊,特别是遇到这种稍微变通复杂的题目就更不会了,希望有高手可以帮帮忙,不甚感激!
【VFP】关于计算二叉树叶子结点的问题有填空题如下：设一棵完全二叉树共有700个结点,则该二叉树中有______个叶子结点?我对二叉树的各种计算还是很模糊,特别是遇到这种稍微变通复杂的题
假设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 ,就可根据完全二叉树的结点总数计算出叶子结点数.
或者
根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则no=n2+1.
根据完全二叉树的定义可得:在完全二叉树中度为1的结点n1只能取两种情况,要么为0,要么为1.
所以:n0+n1+n2=700
n0=n2+1;
2n0=701-n1;
因为结点数为整数,所以n1=1,no=350
或者
完全二叉树的定义：若设二叉树的高度为h,除第 h 层外,其它各层 (1～h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树.
可以算出,这棵二叉树共十层,1-9层的节点个数为2^9-1=511个,所以最后一层的节点个数为700-511=189个,189div2=95,那么倒数第二层的叶结点个数即是2^(9-1)-95=161个
所以所有的叶结点个数即为:189+161=350个