Question

为什么度为0的结点总是比度为2的结点多一个..快来解救我吧。。

Answer 1

证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。

因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：

n=n0+n1+n2 （1）

再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。

又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。

将此式代入上式，得：

n=n1+2n2+1 （2）

用（1）式减去（2）式，并经过调整后得到：n0=n2+1。

扩展资料： 

二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过

, i>=1；

(2) 深度为h的二叉树最多有

 个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

 （注：[ ]表示向下取整）

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I>1，则其父结点的编号为I/2；

如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；

如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。

(6)给定N个结点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i。

参考资料来源：百度百科-二叉树    

Answer 2

假设度为2的节点数为M,度为1的节点为N,度为0的节点为L,总节点数=M+N+L;
另一个关系，每个度为2的节点产生两个节点，度为1的节点产生一个节点，还有一个
不是由节点产生的根节点，总结点数=2*M+N+1；
联立两式得： L=M+1，即度为0的结点总是比度为2的结点多一个。。。明白？

Answer 3

在二叉树中有以下节点：度为0的结点，度为1的结点，度为2的结点

总度数=所有节点-1=度为0的结点+度为1的结点+度为2的结点-1
总度数又=度为1的结点+2*度为2的结点

由上两式可得 ： 度为2的结点=度为0的结点-1