物理學(xué)論文-二叉樹的遍歷研究及還原研究.doc

物理學(xué)論文-二叉樹的遍歷研究及還原研究摘要：通過對同一棵二叉樹三種遍歷方式的分析，概括出由前序、中序或由中關(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)。由前序和中序遍歷、由中序和后序遍歷序列可以唯一確定一棵二叉樹，而由前序和后序遍歷序列不能二叉排序樹對二叉樹作了進(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)系及二叉排序樹來快速還原一棵二叉樹？下面以二叉樹的前序和中序遍歷序列為基礎(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的左子樹或右子樹的過程中，仍然遵循3）中的規(guī)則，（5（6）對于由中序序列和后序序列還原二叉樹是，讀入的序列為后序序列，2二叉樹遍歷過程中，在中序序列中，根結(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對應(yīng)的左子樹和CC對應(yīng)的右子樹，最后將三棵子樹合并成以BB為根結(jié)點(diǎn)、AA的根結(jié)點(diǎn)為BB的左子樹、CC的根結(jié)點(diǎn)為BB（5（6）在還原過程中，讀入序列的順序也遵循也先根結(jié)點(diǎn)，后子樹的規(guī)律。3在二叉樹的一些應(yīng)用中，如平衡二叉樹、紅黑樹等，常常要觀察二叉樹