对于任意一棵二叉树BT,如果度为0的结点个数为n0,度为2的结点个数为n2,则n0=n2+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。
因为二叉树所有结点滴个数都不大于2,所以结点总数n=n0+n1+n2 (1)又因为度为1和度为2的结点分别有1个子树和2个子树,所以,二叉树中子树结点就有n(子)=n1+2n2二叉树中只有根节点不是子树结点,所以二叉树结点总数n=n(子)+1 即 n=n1+2n2+1 (2)结合(1)式和(2)式就得n0=n2+1