計(jì)算機(jī)二級(jí)公共基礎(chǔ)專題探究——二叉樹(shù)(編輯修改稿)
2025-04-21 07:50 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 結(jié)點(diǎn)個(gè)數(shù)為2^61=63，則第7層共有12563=62個(gè)葉子結(jié)點(diǎn)，分別掛在第6層的左邊62個(gè)結(jié)點(diǎn)上，加上第6層的最后1個(gè)葉子結(jié)點(diǎn)，該完全二叉樹(shù)共有63個(gè)葉子結(jié)點(diǎn)，故B選項(xiàng)正確。9滿二叉樹(shù)和完全二叉樹(shù)可以按層序進(jìn)行順序存儲(chǔ)，一般的二叉樹(shù)不試用。10堆可以用一維數(shù)組儲(chǔ)存也可以用完全二叉樹(shù)來(lái)表示堆的結(jié)構(gòu)。11完全二叉樹(shù)中，若總結(jié)點(diǎn)數(shù)是偶數(shù)，則N1=1，若為奇數(shù)，則N1=012深度為i的滿二叉樹(shù)中，N2=2i1 1排序二叉樹(shù)中有序的是中序序列。堆排序問(wèn)題：題型一：三種序列的轉(zhuǎn)換。（文字?jǐn)⑹鲂停├?：已知前序序列與中序序列均為ABCDEFGH，求后序序列【解析】設(shè)根節(jié)點(diǎn)為D≠0，左子樹(shù)為L(zhǎng)，右子樹(shù)為R，有遍歷順序?yàn)椋呵埃篋LR 已知ABCDEFGH 中：LDR 已知ABCDEFGH 后：LRD 待求 由此可知，L=0，DR= ABCDEFGH 故RD=HGFEDCBA，即后序序列= HGFEDCBA變式訓(xùn)練1：已知后序序列與中序序列均為ABCDEFGH，求前序序列答案：HGFEDCBA，（這次R=0）結(jié)論：若前序序列與中序序列均為某序列，則后序序列為該序列的倒序，且為折線；同樣地，若后序序列與中序序列均為某序列，則前序序列為該序列的倒序，且為折線例2：已知前序序列=ABCD，中序序列=DCBA，求后序序列【解析】設(shè)根節(jié)點(diǎn)為D≠0，左子樹(shù)為L(zhǎng)，右子樹(shù)為R，有遍歷順序?yàn)椋呵埃篋LR 已知ABCD 中：LDR 已知DCBA 后：LRD 待求因?yàn)锳BCD與DCBA正好相反，由此可知，R=0所以DL=ABCD，即LD=DCBA所以后序序列= DCBA變式訓(xùn)練21：中序序列=BDCA，后序序列=DCBA，求前序序列【解析】設(shè)根節(jié)點(diǎn)為D≠0，左子樹(shù)為L(zhǎng)，右子樹(shù)為R，有遍歷順序?yàn)椋呵埃篋LR 待求 中：LDR 已知BDC,A 后：LRD 已知DCB,A 通過(guò)觀察可知，R=0，L={B,D,C}，D=A中、后變換時(shí)，{B,D,C}發(fā)生了變化，說(shuō)明左子樹(shù)結(jié)構(gòu)特殊，進(jìn)一步令 中’：L’D’R’ 已知B,DC 后
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1