题目如题,假设完全二叉树中,度为0的节点(即叶节点)数目为n0,度为1的节点数为n1,度为2的数目为n2,总数为n
首先,我们得知道两个公式
(1)结点总数满足:
n
=
n
0
+
n
1
+
n
2
n = n_0 + n_1 + n_2
n=n0+n1+n2
(2)出度、入度,即分支数满足:
n
−
1
=
0
⋅
n
0
+
1
⋅
n
1
+
2
⋅
n
2
n - 1 = 0·n_0 + 1·n_1 + 2·n_2
n−1=0⋅n0+1⋅n1+2⋅n2
根据 ( 1 ) , ( 2 ) (1),(2) (1),(2)可得 n 0 = n 2 + 1 = n − 1 − n 1 2 + 1 n_0 = n_2 + 1 = \frac{n-1 - n_1}{2} + 1 n0=n2+1=2n−1−n1+1,但我们还是不能求出叶子节点数,我们还少了条件:
- 如果节点总数是偶数,则 n 1 = 1 n_1 = 1 n1=1
- 如果节点总数是奇数,则 n 1 = 0 n_1 = 0 n1=0
由此则有: n 0 = n − 1 − ( n + 1 ) % 2 2 + 1 n_0 = \frac{n-1 - (n+1) \% 2}{2} + 1 n0=2n−1−(n+1)%2+1,若我们假设 n = 2019 n = 2019 n=2019,则有 n 0 = ( 2019 − 1 ) − ( 2019 + 1 ) % 2 2 + 1 = 1010 n_0 = \frac{(2019-1) - (2019+1)\%2}{2} + 1= 1010 n0=2(2019−1)−(2019+1)%2+1=1010