完全二叉樹

定義：
按層序遍歷（從上到下，從左到右）填充節點。
除了最后一層外，其余各層必須全滿。
最后一層的節點必須 連續靠左。
完全二叉樹不一定是滿二叉樹。
滿二叉樹 (Full Binary Tree)：每個節點都有 0 或 2 個孩子。
完全二叉樹：強調節點填充的順序，不要求“必須兩個孩子”。
我之前在做題的時候就混淆了這兩個概念。

完全二叉樹的性質

節點數量范圍
高度為 h 的完全二叉樹（根為第 1 層）
節點數最少：2^(h-1)
節點數最多：2^h - 1
節點位置編號規律（堆存儲思想）：
如果根節點編號是 1
左孩子 = 2i
右孩子 = 2i + 1
父節節點 = i/2（向下取整）
從0開始父親節點的下標是（i-1）/2
葉子節點分布
只可能出現在最后一層，或者最后兩層。
且最后一層的葉子必須集中在最左邊。
數組存儲最優
因為節點編號連續 → 可以直接用數組下標表示節點位置（堆就是這樣做的）。
節省指針存儲空間，也方便隨機訪問。
注意得到父親節點的方法

完全二叉樹的應用

堆 (Heap)
二叉堆（最大堆、最小堆）就是基于完全二叉樹的順序存儲實現的。
優先隊列就是堆的典型應用。