求解二叉树节点个数问题通常利用以下几个性质:
(1)n0 = n2 + 1
(2)度之和 = n - 1
(3)度之和 = n1 + 2n2
(4)由 (2)、(3) 得 n = n1 + 2n2 + 1
(5)对于完全二叉树:
① 当节点总数n为奇数时,n1 = 0;
② 当节点总数n为偶数时,n1 = 1。
(6)对于满二叉树,n1 = 0。
例1.具有10个叶子节点的二叉树中有____个度为2的节点。
A. 8 B. 9
C. 10 D. 11
【分析】 (1)求解二叉树节点个数问题。
(2)已经n0求n2,考虑利用性质(1)。
【解】 由性质(1),可知
n0 = n1 + 1
即 n2 = n0 -1 = 10 -1 = 9。本题答案为(B)。
例2.一棵完全二叉树上有1001个节点,其中叶子节点的个数是_____。
A. 250 B. 501
C. 254 D. 505
【分析】 (1)求解二叉树节点个数问题。
(2)完全二叉树,考虑利用性质(5)结合其它几个性质求解。
【解】 ① 由性质(1),可知
n0 = n1 + 1
② 由性质(5),1001为奇数,故 n1 = 0
③ n = n0 + n1 + n2 = n0 + n2 = 2n0 - 1 = 1001
得 n0 = 501
【注意】此题如果用总的叶子节点个数 = 最后一层的叶子节点 + 倒数第二层叶子节点个数来求解的话,将会非常繁琐。