填空题
公共基础知识
题号 #494203
拥有奇数个结点的完全二叉树中有4个内部结点(非叶子结点),请问它的叶子结点数是________。
参考答案
暂无
答案解析
5【分析】由于完全二叉树是自上而下、自左而右的从l开始连续编码的,因此完全二又树要么不存在-度结点(当结点个数为奇数个时),要么存在一个-度结点,而且唯-的一个-度结点就是最后编号为n(n为偶数)的叶子结点的父结点。而在二叉树中零度结点个数总比二度结点个数多l,因此拥有4个二度结点的二叉树的叶子结点的个数是4+1=5。
总结,设n为完全二叉树的结点数,n0为叶子结点数,nl为度为1的结点数,n2为度2的结点数,则n=n0+nl+n2,n0=n2+1。若n为奇数,则nI=0;若n为偶数,则nl=l(注意-定要是完全二又树)。
总结,设n为完全二叉树的结点数,n0为叶子结点数,nl为度为1的结点数,n2为度2的结点数,则n=n0+nl+n2,n0=n2+1。若n为奇数,则nI=0;若n为偶数,则nl=l(注意-定要是完全二又树)。