一棵二叉树中共有70个叶子结点和80个度为1的结点，则这个二叉树的总结点数是多少？

求分析过程。

大大，是这样的哈，叶子结点总是比度为2的结点多一个（可以用数学退出来的额），即n0=n2+1。设总结点数目m=n0+n1+n2，用上面的公式既可以化成m=2*n0-1+n1，带入数据结果应该是m=2*70-1+80=219.应该是这样额。。。

叶子结点总是比度为2的结点多一个（可以用数学退出来的额）
咋推？

呵呵  我也只会用

设n1为二叉树T中度为1的结点数.因为二叉树中所有结点的度军小于或等于2,所以其结点总数为
n=n0+n1+n2    (1)
再看二叉树中的分支数.除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1.由于这些分支是由度为1或2的结点射出的，所以B=n1+2n2.于是得
n=n1+2n2+1    (2)
由式(1)(2)得
n0=n2+1

转载的阿

转载的好阿

转载的说的很对!这个推导过程适应于所有的树！记得课本上是这么说的！

等下哈，我推一下。。。

因总结点数n=n0+n1+n2,因为二叉树中除了根结点以外，其余的每一个结点都有唯一的一个分支进入，设二叉树中所有进入分支的总数为m，则二叉树中总的节点数为n=m+1（一）
又由于二叉树中这m个进入分支是由分别由非叶子结点射出的。其中度为1的每个结点射出一个分支，度为2的结点射出2个分支。因此二叉树中所有度为1与度为2的结点射出的分支总数为n1+n2.而在二叉树中，总的射出的分支数应该与总的进入的分支数相等，于是m=n1+n2，然后代入上式既有
m=n1+2*n2（二），将（二）代入（一）既有n=n1+2*n2+1（三），然后比较（三）和n=n0+n1+n2,既有n0+n1+n2=n1+2*n2+1，消去相等的项，既有
n0=n2+1.
这样就证完了。大大你看看哈。

[ 本帖最后由 zxd675816777 于 2012-3-5 19:51 编辑 ]

抓住不变量，证明思路就很清晰了额。。。