十九、平衡因子

一、定义

二叉树上结点的平衡因子(Balance Factor, BF)定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

二、例题

1. 若平衡二叉树的高度为6，且所有非叶子结点的平衡因子均为1，则该平衡二叉树的结点总数为（ B ）。

  A.12   B. 20   C. 32      D. 33

解法一:

所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为n、左右子树的高度分别为n-1和n-2、所有非叶结点的平衡因子均为1的平衡二叉树，计算总结点数的公式为C_n = C_n-1 + C_n-2 + 1，C₁ = 1，C₂ = 2, C₃ = 2 + 1 + 1 = 4，可推出C₆ = 20。

解法二：

对于选项A，高度为6、结点数为12的树怎么也无法达到平衡。对于选项C，结点较多时，考虑较极端的情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点依然不影响平衡，不是最少结点的情况。同理D错误。只可能选B。