計(jì)算機(jī)二級公共基礎(chǔ)專題探究——二叉樹(參考版)
2025-03-28 07:50本頁面
【正文】 例1：【解析】先列一個(gè)表，設(shè)葉子結(jié)點(diǎn)數(shù)=nN42N33N23N10N0n有N=（42+33+23+10）+1=24，其中多加的1是根節(jié)點(diǎn)然后n=242330=16變式訓(xùn)練1：【解析】先列一個(gè)表，設(shè)葉子結(jié)點(diǎn)數(shù)=nN33N20N14N0n有N=（33+20+14）+1=14，其中多加的1是根節(jié)點(diǎn)然后n=14304=7例2：【解析】先列一個(gè)表，設(shè)葉子結(jié)點(diǎn)數(shù)=nN38N0n有N=（38）+1=25，其中多加的1是根節(jié)點(diǎn)然后n=258=17變式訓(xùn)練21：【解析】先列一個(gè)表，設(shè)度為3的結(jié)點(diǎn)數(shù)=nN3nN07有N=（3n）+1=25，其中多加的1是根節(jié)點(diǎn)，可知n=8然后7≠258=17?。?！ 故：“不存在這樣的樹”（啟示：一定要驗(yàn)算）變式訓(xùn)練22：【解析】先列一個(gè)表，設(shè)度為3的結(jié)點(diǎn)數(shù)=nN3nN23N14N015有N=（3n）+23+14）+1，其中多加的1是根節(jié)點(diǎn)然后15=N22n 聯(lián)立后無整數(shù)解 故：“不存在這樣的樹”（啟示：一定要驗(yàn)算）例3：5+1=6題型四：與按層次輸出有關(guān)的問題。 有二叉樹的性質(zhì)3，N0= N2+1 由題，N2= N01=0，有總節(jié)點(diǎn)數(shù)N= N0+ N1+ N2=12， 解得N1=11，故二叉樹的圖像為一條折線（或直線） 所以深度為12例2：已知二叉樹的前序序列=ABCDEFG，中序序列=DCBAEFG，（1）求后序序列（2）求深度。例1：已知某二叉樹共有12個(gè)節(jié)點(diǎn)，其中葉子結(jié)點(diǎn)1個(gè)，求深度。堆排序問題：題型一：三種序列的轉(zhuǎn)換。10堆可以用一維數(shù)組儲存也可以用完全二叉樹來表示堆的結(jié)構(gòu)。深度為6的滿二叉樹，結(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)，該完全二叉樹共有63個(gè)葉子結(jié)點(diǎn)，故B選項(xiàng)正確。根據(jù)前序序列可知，C是D的根結(jié)點(diǎn)，故后序序列為DCBA例2：對下列二叉樹進(jìn)行前序遍歷的結(jié)果為 ABDYECFXZ 例3：設(shè)二叉樹如下，則后序序列為 DGEBHFC
高考資料相關(guān)推薦
鄂ICP備17016276號-1