W3Cschool
恭喜您成為首批注冊(cè)用戶(hù)
獲得88經(jīng)驗(yàn)值獎(jiǎng)勵(lì)
在鏈表表示下,二叉樹(shù)的存儲(chǔ)單元為節(jié)點(diǎn) TreeNode ,節(jié)點(diǎn)之間通過(guò)指針相連接。在上節(jié)中,我們學(xué)習(xí)了在鏈表表示下的二叉樹(shù)的各項(xiàng)基本操作。
那么,我們能否用數(shù)組來(lái)表示二叉樹(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)。
完美二叉樹(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ù)了。
Copyright©2021 w3cschool編程獅|閩ICP備15016281號(hào)-3|閩公網(wǎng)安備35020302033924號(hào)
違法和不良信息舉報(bào)電話(huà):173-0602-2364|舉報(bào)郵箱:jubao@eeedong.com
掃描二維碼
下載編程獅App
編程獅公眾號(hào)
聯(lián)系方式:
更多建議: