平衡因子

平衡因子

某結點的左子樹與右子樹的高度(深度)差即為該結點的平衡因子(BF,Balance Factor)。

平衡二叉樹上所有結點的平衡因子只可能是 -1,0 或 1。

目錄

正文


舉例
平衡因子
平衡因子
結合右側圖示:
(a)平衡二叉樹
此節點往下 左子樹深度 - 右子樹深度=平衡因子
5的結點平衡因子就是 3 - 2 = 1;
2的結點平衡因子就是 1 - 2 = -1;
4的結點平衡因子就是 1 - 0 = 1;
6的結點平衡因子就是 0 - 1 = -1;
葉子結點都是為 0;
(b)不平衡二叉樹
此節點往下 左子樹深度- 右子樹深度=平衡因子
3 的結點平衡因子就是 2 - 4 = -2;
1 的結點平衡因子就是 0 - 1 = -1;
4 的結點平衡因子就是 0 - 3 = -3;
5 的結點平衡因子就是 0 - 2 = -2;
6 的結點平衡因子就是 0 - 1 = -1;
葉子結點都是為 0;