計(jì)算機(jī)二級(jí)公共基礎(chǔ)專題探究——二叉樹-wenkub
2023-04-09 07:50:29 本頁(yè)面
【正文】 已知B,DC 后’：L’R’D’ 已知DC,B 可知L’=0，即D’=B，R’= DCA可以畫出二叉樹示意圖為：BCD所以前序序列= ABCD變式訓(xùn)練22：中序序列=ABC，后序序列=CBA，求前序序列【解析】設(shè)根節(jié)點(diǎn)為D≠0，左子樹為L(zhǎng)，右子樹為R，有遍歷順序?yàn)椋呵埃篋LR 待求 中：LDR 已知ABC 后：LRD 已知通過(guò)觀察可知，L=0，DR=ABC，RD=CBA 所以前序序列=DLR= DR=ABC變式訓(xùn)練23：前序序列=ABC，中序序列=CBA，求后序序列【解析】設(shè)根節(jié)點(diǎn)為D≠0，左子樹為L(zhǎng)，右子樹為R，有遍歷順序?yàn)椋呵埃篋LR 已知A,BC 中：LDR 已知CB,A 后：LRD 待求通過(guò)觀察可知，D=A ，L={B,C}，R=0 所以后序序列=CBA (一邊偏)題型二：求二叉樹的深度 。9滿二叉樹和完全二叉樹可以按層序進(jìn)行順序存儲(chǔ)，一般的二叉樹不試用。再根據(jù)中序序列可知DC是結(jié)點(diǎn)B的左子樹。否則：①訪問(wèn)根結(jié)點(diǎn)；②前序遍歷左子樹；③前序遍歷右子樹，5中序遍歷（訪問(wèn)根結(jié)點(diǎn)在訪問(wèn)左子樹和訪問(wèn)右子樹兩者之間）6后序遍歷（訪問(wèn)根結(jié)點(diǎn)在訪問(wèn)左子樹和訪問(wèn)右子樹之后）7重點(diǎn)題型：二叉樹的遍歷例1：某二叉樹的前序序列為ABCD，中序序列為DCBA，則后序序列為（DCBA ）?！窘馕觥坑?6個(gè)度為2的結(jié)點(diǎn)可知葉子結(jié)點(diǎn)個(gè)數(shù)為17，則結(jié)點(diǎn)結(jié)點(diǎn)總數(shù)為16+17+15=48例5：某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。序號(hào)高頻考點(diǎn)1樹是簡(jiǎn)單的非線性結(jié)構(gòu)，二叉樹作為樹的一種也是一種非線性結(jié)構(gòu)。二叉樹的基本性質(zhì)：必考的題目（1）在二叉樹的第k層上，最多有2k1(k≥1)個(gè)結(jié)點(diǎn)；（2）深度為m的二叉樹最多有2m1個(gè)結(jié)點(diǎn)；（3）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)；（4）二叉樹中 n = n0 +n1 +n2滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹有2m1個(gè)結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。公共基礎(chǔ)專題探究——二叉樹
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1