Question

某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数是？

我算的是（n+1）/2 我取的是完全二叉树的情况：
设二叉树深度为X （2平方X）-1=2n+1
所以 2平方（x-1）=n+1 即是叶子结点数，我这算法对么？

Answer 1

n+1

对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1.
设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

Answer 2

设二叉树有a个度为二的节点，b个度为1的节点，c个叶子节点。
则二叉树的节点个数m=a+b+c
每条边对应一个节点，只有根节点没有相应的边。
所以节点个数m= 边数n+1
一个度为2的节点对应有2条出边，
一个度为1的节点对应有条出边，
所以边数n=所有节点的度之和=2*a+1*b
m=（2*a+1*b）+1
和m=a+b+c
联立消去m和b
可以解得c=a+1
即 叶子节点个数 为 度为2的节点树+1

Answer 3

设二叉树有a个度为二的节点，b个度为1的节点，c个叶子节点。
则二叉树的节点个数m=a+b+c
每条边对应一个节点，只有根节点没有相应的边。
所以节点个数m= 边数n+1
一个度为2的节点对应有2条出边，
一个度为1的节点对应有条出边，
所以边数n=所有节点的度之和=2*a+1*b
m=（2*a+1*b）+1
和m=a+b+c
联立消去m和b
可以解得c=a+1
即 叶子节点个数 为 度为2的节点树+1

Answer 4

某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数是n+1
对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1.
设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

Answer 5

其实没有这么麻烦，根据二叉树的性质中叶子结点数n0和度为2结点个数n2的关系：n0 = n2 +1，推导过程参见《数据结构》教材，于是叶子结点数为n + 1