如图所示,红色结点为度为2的结点
额,不好意思,少画了一个,只要在第四行的最后再添一个就行了,它的父亲节点是第三行第三个结点(最后一个红色结点的后面),这样此结点度为1,度为2的结点还是只有5个。
设n是完全二叉树的节点数。
n1是度为1的节点数,n2是度为2的节点数,n0是度0节点数也就是叶子数。
对二叉树有 n0 = n1 + n2 + n0; n0 = n2 + 1;这两个是基本公式。
对完全二叉树有 n1 = 0或1,分别对应n为奇数和n为偶数的情况;这是基本性质,可以自己画一下看看。
所以:
n为奇数:n = n0 + n1 + n2 = n0 + n2 = 2*n0 - 1 => n0 = (n + 1)/2
n为偶数:n = n0 + n1 + n2 = 1 + n0 + n2 = 2n0 => n0 = n/2
这样就很明显了吧,单子节点一眼也能看出,叶子数稍微算一下就出来了,度二节点自然就出来了
1
2 3
4 5 6 7
8 9 10 11 12
A叶子结点有6个,分别是7、8、9、10、11、12
B度为2的结点有5个,分别是1、2、3、4、5
C分支结点有6个,分别是1、2、3、4、5、6
D度为1的节点有1个,是6