数据结构 —— 已知一棵完全二叉树的节点数n,求叶节点数

时间:2024-11-11 10:24:50

题目如题,假设完全二叉树中,度为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 n1=0n0+1n1+2n2

根据 ( 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=2n1n1+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=2n1(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(20191)(2019+1)%2+1=1010