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

在鏈表表示下，二叉樹(shù)的存儲(chǔ)單元為節(jié)點(diǎn) TreeNode ，節(jié)點(diǎn)之間通過(guò)指針相連接。在上節(jié)中，我們學(xué)習(xí)了在鏈表表示下的二叉樹(shù)的各項(xiàng)基本操作。

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

表示完美二叉樹(shù)

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

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

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

映射公式的角色相當(dāng)于鏈表中的指針。給定數(shù)組中的任意一個(gè)節(jié)點(diǎn)，我們都可以通過(guò)映射公式來(lái)訪(fǎng)問(wèn)它的左（右）子節(jié)點(diǎn)。

7.3.2   表示任意二叉樹(shù)

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

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

圖 7-13   層序遍歷序列對(duì)應(yīng)多種二叉樹(shù)可能性

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