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