企源知识库

任何非空二叉树中,度为2的结点的个数比叶结点的个数少1。
【正确答案】：证明: 对任一非空二叉树T,设n₀是叶结点的个数,n₁是度为1的结点个数,n₂是度为2的结点的个数。则T中结点总数n为n=n₀+n₁+n₂。
 树中所含的边数=n-1,度为2的结点贡献两条边,度为1的结点贡献一条边,度为0的结点不贡献边。由此得到n-1=2*n₂+1*n₁+0*n₀ 。
 将上述两个等式联立,得到n₀=n₂+1,结论得证。  证毕