二叉樹(shù)的遍歷研究及還原研究

時(shí)間：2024-08-11 02:15:03 物理畢業(yè)論文我要投稿

相關(guān)推薦

二叉樹(shù)的遍歷研究及還原研究

　摘要：通過(guò)對(duì)同一棵二叉樹(shù)三種遍歷方式的分析，概括出由前序、中序或由中序、后序遍歷結(jié)果快速還原二叉樹(shù)的方法。?
　　關(guān)鍵詞：二叉樹(shù);二叉樹(shù)的遍歷;二叉排序樹(shù);還原? ?
　　
　　二叉樹(shù)是最為常用的數(shù)據(jù)結(jié)構(gòu)，它的實(shí)際應(yīng)用非常廣泛。二叉樹(shù)的遍歷方式有三種，前序遍歷、中序遍歷、后序遍歷。先序遍歷的順序?yàn)椋篘LR，即先根結(jié)點(diǎn)，然后左子樹(shù)、右子樹(shù)；中序遍歷順序?yàn)椋篖NR先左子樹(shù)，然后根結(jié)點(diǎn)、右子樹(shù)；后序遍歷順序?yàn)椋篖RN先左子樹(shù)、然后右子樹(shù)、根結(jié)點(diǎn)。由前序和中序遍歷、由中序和后序遍歷序列可以唯一確定一棵二叉樹(shù)，而由前序和后序遍歷序列不能唯一確定一棵二叉樹(shù)。?
　　二叉排序樹(shù)對(duì)二叉樹(shù)作了進(jìn)一步的限定：根結(jié)點(diǎn)的權(quán)值大于（或小于）左子樹(shù)中所有結(jié)點(diǎn)的權(quán)值；根結(jié)點(diǎn)的權(quán)值小于（或大于）其右子樹(shù)中所有結(jié)點(diǎn)的權(quán)值。?
　　那么如何根據(jù)三種遍歷序列之間的關(guān)系及二叉排序樹(shù)來(lái)快速還原一棵二叉樹(shù)？下面以二叉樹(shù)的前序和中序遍歷序列為基礎(chǔ)，利用二叉排序樹(shù)的性質(zhì)，給出快速還原二叉樹(shù)的方法。?
　　1由給定前序和中序序列或中序和后序序列還原二叉樹(shù)的方法?
　　例：前序序列：ABDECFGH 中序序列：DEBACGFH （后序序列：EDBGHFCA）?
　　（1）給中序序列中的每個(gè)結(jié)點(diǎn)從小到大、從左到右賦以權(quán)值，如下：?
　　D（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)值按照二叉排序樹(shù)的構(gòu)造規(guī)則構(gòu)造二叉排序樹(shù)。第一個(gè)讀入的結(jié)點(diǎn)為根結(jié)點(diǎn)，其他結(jié)點(diǎn)分別為左右子樹(shù)中的結(jié)點(diǎn)。設(shè)根結(jié)點(diǎn)為T(mén)T，權(quán)值為NN，當(dāng)前讀入結(jié)點(diǎn)為SS，權(quán)值為MM，若MM　�。�4）將SS插入到TT的左子樹(shù)或右子樹(shù)的過(guò)程中，仍然遵循3）中的規(guī)則，直至左子樹(shù)或右子樹(shù)為空時(shí)止。?
　�。�5）讀入序列結(jié)束時(shí)，二叉樹(shù)還原成功。還原后的二叉樹(shù)如下圖。?
　　
　�。�6）對(duì)于由中序序列和后序序列還原二叉樹(shù)是，讀入的序列為后序序列，從右向左讀入，構(gòu)造規(guī)則同上。還原結(jié)果與上述結(jié)果完全一致。?

　　2還原方法的確定依據(jù)?
　　二叉樹(shù)遍歷過(guò)程中，在中序序列中，根結(jié)點(diǎn)的左子樹(shù)中的所有結(jié)點(diǎn)都在根結(jié)點(diǎn)的左側(cè)，根結(jié)點(diǎn)的右子樹(shù)中的所有結(jié)點(diǎn)都在根結(jié)點(diǎn)的右側(cè)，這個(gè)特點(diǎn)恰好與二叉排序樹(shù)具有相同的性質(zhì)；在讀入序列時(shí)，前序序列則從左向右讀，這恰好與遍歷二叉樹(shù)的順序相同；后序序列從右向左讀，則按照根結(jié)點(diǎn)、右子樹(shù)、左子樹(shù)的順序還原。?
　　（1）設(shè)二叉樹(shù)共有N個(gè)結(jié)點(diǎn)（N為大于1的正整數(shù)），我們按照還原方法給中序序列中的這N個(gè)結(jié)點(diǎn)分別賦予權(quán)值1,2…N，設(shè)根結(jié)點(diǎn)的權(quán)值為M（1　　（2）由二叉樹(shù)的遍歷規(guī)則可知，權(quán)值為1,2…M-1的結(jié)點(diǎn)為根結(jié)點(diǎn)的左子樹(shù)中的結(jié)點(diǎn)，而權(quán)值為M+1,…N的結(jié)點(diǎn)為根結(jié)點(diǎn)的右子樹(shù)中的結(jié)點(diǎn)。?
　�。�3）將這N個(gè)結(jié)點(diǎn)劃分成3個(gè)子集AA＝（1,2…M-1）BB＝（M）CC＝（M+1,…N），由于前序序列第一個(gè)讀入的結(jié)點(diǎn)必定為二叉根的根結(jié)點(diǎn)，所以BB為根結(jié)點(diǎn)，AA集為左子樹(shù)，CC集為右子樹(shù)。?
　�。�4）同理不斷讀入前序序列中的結(jié)點(diǎn)，依次遞歸還原BB對(duì)應(yīng)的左子樹(shù)和CC對(duì)應(yīng)的右子樹(shù)，最后將三棵子樹(shù)合并成以BB為根結(jié)點(diǎn)、AA的根結(jié)點(diǎn)為BB的左子樹(shù)、CC的根結(jié)點(diǎn)為BB的右子樹(shù)的一棵二叉排序樹(shù)。?
　�。�5）同理可以得出，由中序序列和后序序還原二叉樹(shù)的規(guī)則也成立。?
　�。�6）在還原過(guò)程中，讀入序列的順序也遵循也先根結(jié)點(diǎn)，后子樹(shù)的。?
　　3?
　　在二叉樹(shù)的一些應(yīng)用中，如平衡二叉樹(shù)、紅黑樹(shù)等，常常要觀察二叉樹(shù)的形態(tài)，對(duì)其進(jìn)行判斷并調(diào)整。根據(jù)遍歷序列和二叉排序樹(shù)的性質(zhì)快速還原出二叉樹(shù)對(duì)于研究相關(guān)的問(wèn)題有很大的幫助。?
　　?
　�。�1］?嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學(xué)出版社,1996.

【二叉樹(shù)的遍歷研究及還原研究】相關(guān)文章：

化學(xué)還原制作納米銀粉研究論文11-16

審計(jì)專(zhuān)業(yè)判定研究：有關(guān)研究的回顧及在中國(guó)研究的機(jī)遇所在03-24

審計(jì)專(zhuān)業(yè)判斷研究：有關(guān)研究的回顧及在中國(guó)研究的機(jī)遇所在03-18

淺談小學(xué)數(shù)學(xué)研究性學(xué)習(xí)研究12-10