设一颗二叉树中,度为2的结点数为9,则该二叉树的叶子节点的数目是?
展开全部
n0=n2+1
证明：设二叉树T中度为1得结点数为n1，结点总数为n。由于T中所有结点度数均不大于2，因此，T中结点总数n=n0+n1+n2 (1)
再考虑树T的分支数。除了根结点外，其余每个结点都有一条向上的分支与双亲结点相连，因此总共有n-1(即总节点-根节点)条向上的分支。从另一个角度看，每个结点有其“度数”条向下的分支与孩子结点相连，因此总共有n1+2n2条向下的分支。因此有：n-1=n1+2n2 (2)
由(1)和(2)->n0=n2+1
因此答案为10
证明：设二叉树T中度为1得结点数为n1，结点总数为n。由于T中所有结点度数均不大于2，因此，T中结点总数n=n0+n1+n2 (1)
再考虑树T的分支数。除了根结点外，其余每个结点都有一条向上的分支与双亲结点相连，因此总共有n-1(即总节点-根节点)条向上的分支。从另一个角度看，每个结点有其“度数”条向下的分支与孩子结点相连，因此总共有n1+2n2条向下的分支。因此有：n-1=n1+2n2 (2)
由(1)和(2)->n0=n2+1
因此答案为10
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
