当前位置：首页 >
离散数学(02324) > 正文内容
任何非空二叉树中,度为2的结点的个数比叶结点的个数少1。
任何非空二叉树中,度为2的结点的个数比叶结点的个数少1。
证明: 对任一非空二叉树T,设n0是叶结点的个数,n1是度为1的结点个数,n2是度为2的结点的个数。则T中结点总数n为n=n0+n1+n2。
树中所含的边数=n-1,度为2的结点贡献两条边,度为1的结点贡献一条边,度为0的结点不贡献边。由此得到n-1=2*n2+1*n1+0*n0 。
将上述两个等式联立,得到n0=n2+1,结论得证。 证毕
扫描二维码免费使用微信小程序搜题/刷题/查看解析。
版权声明：本文由翰林刷题小程序授权发布，如需转载请注明出处。