作业帮 > 数学 > 作业

证明:在任意一棵二叉树中,若总结点的个数为n0,度为2的结点数为n2,则n0=n2+1

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/07/08 10:40:40
证明:在任意一棵二叉树中,若总结点的个数为n0,度为2的结点数为n2,则n0=n2+1
证明:
设n1为二叉树T中度为1的结点数.
因为二叉树中所有的结点的度均小于等于2,所以其结点总数为
n=n0+n1+n2
又由于二叉树除了根节点外,其余结点都有一个分支进入,设B为分支总数,则n=B+1.
由于这些分支是由度为1或2的结点射出,所以又有B=n1+2Xn2
所以n=n0+n1+n2=n1+2Xn2+1
所以n0=n2+1