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