二叉樹的遍歷研究及還原研究

　摘要：通過對同一棵二叉樹三種遍歷方式的分析，概括出由前序、中序或由中序、后序遍歷結果快速還原二叉樹的方法。?
　　關鍵詞：二叉樹;二叉樹的遍歷;二叉排序樹;還原? ?
　　
　　二叉樹是最為常用的數(shù)據(jù)結構，它的實際應用非常廣泛。二叉樹的遍歷方式有三種，前序遍歷、中序遍歷、后序遍歷。先序遍歷的順序為：NLR，即先根結點，然后左子樹、右子樹；中序遍歷順序為：LNR先左子樹，然后根結點、右子樹；后序遍歷順序為：LRN先左子樹、然后右子樹、根結點。由前序和中序遍歷、由中序和后序遍歷序列可以唯一確定一棵二叉樹，而由前序和后序遍歷序列不能唯一確定一棵二叉樹。?
　　二叉排序樹對二叉樹作了進一步的限定：根結點的權值大于（或小于）左子樹中所有結點的權值；根結點的權值小于（或大于）其右子樹中所有結點的權值。?
　　那么如何根據(jù)三種遍歷序列之間的關系及二叉排序樹來快速還原一棵二叉樹？下面以二叉樹的前序和中序遍歷序列為基礎，利用二叉排序樹的性質，給出快速還原二叉樹的方法。?
　　1由給定前序和中序序列或中序和后序序列還原二叉樹的方法?
　　例：前序序列：ABDECFGH 中序序列：DEBACGFH （后序序列：EDBGHFCA）?
　　（1）給中序序列中的每個結點從小到大、從左到右賦以權值，如下：?
　　D（1）E（2）B（3）A（4）C（5）G（6）F（7）H（8）?
　�。�2）還原時讀入的序列為前序序列，從左到右依次讀入序列中的各個結點值和相應的權值； ?
　　
　�。�3）由讀入的序列，根據(jù)第1）步中給定的權值按照二叉排序樹的構造規(guī)則構造二叉排序樹。第一個讀入的結點為根結點，其他結點分別為左右子樹中的結點。設根結點為TT，權值為NN，當前讀入結點為SS，權值為MM，若MM　�。�4）將SS插入到TT的左子樹或右子樹的過程中，仍然遵循3）中的規(guī)則，直至左子樹或右子樹為空時止。?
　�。�5）讀入序列結束時，二叉樹還原成功。還原后的二叉樹如下圖。?
　　
　�。�6）對于由中序序列和后序序列還原二叉樹是，讀入的序列為后序序列，從右向左讀入，構造規(guī)則同上。還原結果與上述結果完全一致。?

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

【二叉樹的遍歷研究及還原研究】相關文章：

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

審計專業(yè)判定研究：有關研究的回顧及在中國研究的機遇所在03-24

審計專業(yè)判斷研究：有關研究的回顧及在中國研究的機遇所在03-18

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

企業(yè)研究論文03-07

護理研究論文03-18

茶道的個人研究03-18

視覺文化研究12-04

負商譽研究03-21