C++二叉樹數(shù)組表示

在鏈表表示下，二叉樹的存儲單元為節(jié)點 TreeNode ，節(jié)點之間通過指針相連接。在上節(jié)中，我們學習了在鏈表表示下的二叉樹的各項基本操作。

那么，我們能否用數(shù)組來表示二叉樹呢？答案是肯定的。

表示完美二叉樹

先分析一個簡單案例。給定一個完美二叉樹，我們將所有節(jié)點按照層序遍歷的順序存儲在一個數(shù)組中，則每個節(jié)點都對應唯一的數(shù)組索引。

根據層序遍歷的特性，我們可以推導出父節(jié)點索引與子節(jié)點索引之間的“映射公式”：若節(jié)點的索引為 i ，則該節(jié)點的左子節(jié)點索引為 2i+1 ，右子節(jié)點索引為 2i+2 。圖 7-12 展示了各個節(jié)點索引之間的映射關系。

圖 7-12   完美二叉樹的數(shù)組表示

映射公式的角色相當于鏈表中的指針。給定數(shù)組中的任意一個節(jié)點，我們都可以通過映射公式來訪問它的左（右）子節(jié)點。

7.3.2   表示任意二叉樹

完美二叉樹是一個特例，在二叉樹的中間層通常存在許多 None 。由于層序遍歷序列并不包含這些 None ，因此我們無法僅憑該序列來推測 None 的數(shù)量和分布位置。這意味著存在多種二叉樹結構都符合該層序遍歷序列。

如圖 7-13 所示，給定一個非完美二叉樹，上述的數(shù)組表示方法已經失效。

圖 7-13   層序遍歷序列對應多種二叉樹可能性

為了解決此問題，我們可以考慮在層序遍歷序列中顯式地寫出所有 None 。如圖 7-14 所示，這樣處理后，層序遍歷序列就可以唯一表示二叉樹了。