


全文預(yù)覽已結(jié)束
下載本文檔
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
物理學(xué)論文-二叉樹的遍歷研究及還原研究摘要:通過(guò)對(duì)同一棵二叉樹三種遍歷方式的分析,概括出由前序、中序或由中關(guān)鍵詞:二叉樹;二叉樹的遍歷;二叉排序樹;二叉樹是最為常用的數(shù)據(jù)結(jié)構(gòu),它的實(shí)際應(yīng)用非常廣泛。二叉樹的遍歷方式有三種,前序遍歷、中序遍歷、后序遍歷。先序遍歷的順序?yàn)椋篘LR,即先根結(jié)點(diǎn),然后左子樹、右子樹;中序遍歷順序?yàn)椋篖NR先左子樹,然后根結(jié)點(diǎn)、右子樹;后序遍歷順序?yàn)椋篖RN先左子樹、然后右子樹、根結(jié)點(diǎn)。由前序和中序遍歷、由中序和后序遍歷序列可以唯一確定一棵二叉樹,而由前序和后序遍歷序列不能二叉排序樹對(duì)二叉樹作了進(jìn)一步的限定:根結(jié)點(diǎn)的權(quán)值大于(或小于)左子樹中所有結(jié)點(diǎn)的權(quán)值;根結(jié)點(diǎn)的權(quán)值小于(或大于)其右子樹中所有結(jié)點(diǎn)的權(quán)值。那么如何根據(jù)三種遍歷序列之間的關(guān)系及二叉排序樹來(lái)快速還原一棵二叉樹?下面以二叉樹的前序和中序遍歷序列為基礎(chǔ),利用二叉排序樹的性質(zhì),給出1例:前序序列:ABDECFGH中序序列:DEBACGFH(后序序列:EDBGHFCA(1D(1)E(2)B(3)A(4)C(5)G(6)F(7)H(8(2)還原時(shí)讀入的序列為前序序列,從左到右依次讀入序列中的各個(gè)結(jié)點(diǎn)值和相應(yīng)的權(quán)值;(3)由讀入的序列,根據(jù)第1)步中給定的權(quán)值按照二叉排序樹的構(gòu)造規(guī)則構(gòu)造二叉排序樹。第一個(gè)讀入的結(jié)點(diǎn)為根結(jié)點(diǎn),其他結(jié)點(diǎn)分別為左右子樹中的結(jié)點(diǎn)。設(shè)根結(jié)點(diǎn)為TT,權(quán)值為NN,當(dāng)前讀入結(jié)點(diǎn)為SS,權(quán)值為MM,若MM(4)將SS插入到TT的左子樹或右子樹的過(guò)程中,仍然遵循3)中的規(guī)則,(5(6)對(duì)于由中序序列和后序序列還原二叉樹是,讀入的序列為后序序列,2二叉樹遍歷過(guò)程中,在中序序列中,根結(jié)點(diǎn)的左子樹中的所有結(jié)點(diǎn)都在根結(jié)點(diǎn)的左側(cè),根結(jié)點(diǎn)的右子樹中的所有結(jié)點(diǎn)都在根結(jié)點(diǎn)的右側(cè),這個(gè)特點(diǎn)恰好與二叉排序樹具有相同的性質(zhì);在讀入序列時(shí),前序序列則從左向右讀,這恰好與遍歷二叉樹的順序相同;后序序列從右向左讀,則按照根結(jié)點(diǎn)、右子樹、左子樹的(1)設(shè)二叉樹共有N個(gè)結(jié)點(diǎn)(N為大于1的正整數(shù)),我們按照還原方法給中序序列中的這N個(gè)結(jié)點(diǎn)分別賦予權(quán)值1,2N,設(shè)根結(jié)點(diǎn)的權(quán)值為M(1M(2)由二叉樹的遍歷規(guī)則可知,權(quán)值為1,2M-1的結(jié)點(diǎn)為根結(jié)點(diǎn)的左子樹中的結(jié)點(diǎn),而權(quán)值為M+1,N(3)將這N個(gè)結(jié)點(diǎn)劃分成3個(gè)子集AA(1,2M-1)BB(M)CC(M+1,N),由于前序序列第一個(gè)讀入的結(jié)點(diǎn)必定為二叉根的根結(jié)點(diǎn),所以BB為根結(jié)點(diǎn),AA集為左子樹,CC(4)同理不斷讀入前序序列中的結(jié)點(diǎn),依次遞歸還原BB對(duì)應(yīng)的左子樹和CC對(duì)應(yīng)的右子樹,最后將三棵子樹合并成以BB為根結(jié)點(diǎn)、AA的根結(jié)點(diǎn)為BB的左子樹、CC的根結(jié)點(diǎn)為BB(5(6)在還原過(guò)程中,讀入序列的順序也遵循也先根結(jié)點(diǎn),后子樹的規(guī)律。3在二叉樹的一些應(yīng)用中,如平衡二叉樹、紅黑樹等,常常要觀察二叉樹
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 醫(yī)院感染與質(zhì)量管理
- 肥胖生殖無(wú)能綜合征知識(shí)科普2025
- 2025屆高考物理大一輪復(fù)習(xí)課件 第九章 第43課時(shí) 電場(chǎng)能的性質(zhì)
- 小兒高熱驚厥的處置
- AI大模型SaaS平臺(tái)設(shè)計(jì)方案
- 小兒肺炎試題單選及答案
- 烯烴炔烴試題及答案
- 河南省青桐鳴2024-2025學(xué)年高二下學(xué)期5月大聯(lián)考地理試卷(含答案)
- 2025年陜西省榆林市榆陽(yáng)區(qū)中考二模歷史試題(含答案)
- 配電箱跨接導(dǎo)線銹蝕排查
- 國(guó)開2024年《測(cè)量學(xué)》形考任務(wù)1234答案全析
- 非營(yíng)利組織項(xiàng)目申請(qǐng)書范文
- 2025年軍隊(duì)文職人員(司機(jī)崗)歷年考試真題庫(kù)及答案(重點(diǎn)300題)
- 2025-2030CAPP軟件行業(yè)市場(chǎng)深度調(diào)研及發(fā)展現(xiàn)狀趨勢(shì)與投資前景研究報(bào)告
- Windows 故障轉(zhuǎn)移群集功能實(shí)現(xiàn)高可用的文件服務(wù)器
- 水庫(kù)清淤工程安全措施
- 2024年全球及中國(guó)5G工業(yè)網(wǎng)關(guān)CPE行業(yè)頭部企業(yè)市場(chǎng)占有率及排名調(diào)研報(bào)告
- 商業(yè)模式創(chuàng)新試題及答案
- 旅行跟拍合同及服務(wù)條款
- 手術(shù)患者深靜脈血栓預(yù)防措施
- 2.2自然保護(hù)區(qū)與生態(tài)安全課件高二地理下學(xué)期魯教版(2019)選擇性必修三
評(píng)論
0/150
提交評(píng)論