設(shè)完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)ABCDE,畫(huà)出該二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？6. 讓ABCDE存儲(chǔ)在一個(gè)完整的二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中。二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和二叉樹(shù)的前序、中序和后序遍歷序列是必需的這種

設(shè)完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)ABCDE,畫(huà)出該二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？

6. 讓ABCDE存儲(chǔ)在一個(gè)完整的二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中。二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和二叉樹(shù)的前序、中序和后序遍歷序列是必需的

這種結(jié)構(gòu)將二叉樹(shù)的所有節(jié)點(diǎn)按一定的順序存儲(chǔ)在一個(gè)連續(xù)的存儲(chǔ)單元中。因此，必須將節(jié)點(diǎn)排列成適當(dāng)?shù)木€(xiàn)性序列，使節(jié)點(diǎn)在序列中的對(duì)應(yīng)位置能夠反映節(jié)點(diǎn)之間的邏輯關(guān)系。這種結(jié)構(gòu)特別適用于幾乎完全的二叉樹(shù)。在一個(gè)具有n個(gè)節(jié)點(diǎn)的近似完全二叉樹(shù)中，通過(guò)對(duì)所有節(jié)點(diǎn)從根開(kāi)始、從上層到下層、從左到右逐層編號(hào)，可以得到一個(gè)反映整個(gè)二叉樹(shù)結(jié)構(gòu)的線(xiàn)性序列。存儲(chǔ)結(jié)構(gòu)值為：假設(shè)節(jié)點(diǎn)在數(shù)組中的位置為I，則其左子位置為2I，右子位置為2i1。（I從1開(kāi)始）。所以您只需要?jiǎng)?chuàng)建一個(gè)數(shù)組，從鏈?zhǔn)酱鎯?chǔ)的根節(jié)點(diǎn)開(kāi)始，按中間順序遍歷樹(shù)，然后按中間順序存儲(chǔ)在數(shù)組中。這樣就可以改變順序存儲(chǔ)結(jié)構(gòu)。你可以查看相關(guān)的遍歷信息，按遍歷的順序即訪(fǎng)問(wèn)的順序是左子根右子。希望能對(duì)你有所幫助。

什么是二叉樹(shù)的順序存儲(chǔ)？

最壞的情況是二叉樹(shù)是單個(gè)分支。例如，如果有一個(gè)k層，它的節(jié)點(diǎn)號(hào)也是k，所以它需要一個(gè)長(zhǎng)度為2^k-1的數(shù)組來(lái)存儲(chǔ)，實(shí)際上它有k個(gè)節(jié)點(diǎn)。為什么？因?yàn)槎鏄?shù)的順序存儲(chǔ)是相對(duì)于完全二叉樹(shù)的。對(duì)于一般的二叉樹(shù)，如果相對(duì)于該二叉樹(shù)沒(méi)有這樣的節(jié)點(diǎn)，則應(yīng)該在數(shù)組中相應(yīng)的位置存儲(chǔ)一個(gè)ID來(lái)指示沒(méi)有這樣的節(jié)點(diǎn)。