二叉樹的遍歷探究與應用

摘要：通過對同一棵二叉樹的前序遍歷、中序遍歷、后序遍歷及層次遍歷得到四個不同序列的分析，概括出二叉樹的前序遍歷、中序遍歷、后序遍歷及層次遍歷序列間的關系，確定對應的二叉樹。

關鍵詞：二叉樹；二叉樹的遍歷；層次遍歷

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)23-1014-02

The Research and Application of Traversing Binary Tree

SHENG Kui

(Bozhou Vocational and Technical College， Bozhou 236800， China)

Abstract: This paper summarizes the relation of the four different array though the analysis of getting four arrayfrom the same binary tree using four different algorithm: preorder traversal，inorder traversal，postorder traversal and level traversal，to determine the corresponding binary tree.

Key words: binary tree; binary tree traversal;level traversal

二叉樹是數據結構非常重要的一種非線性數據結構，是樹型結構的一種特殊形式，廣泛應用于計算機科學和信息科學。在對二叉樹的操作中，遍歷是一種重要的操作，在現在生活中有許多數據關系，可推廣為二叉樹遍歷的形式，如在二叉樹查找二叉樹中的某些結點，或者是通過對二叉樹中所有結點逐一處理而達到某些運算的目的。但許多教材中都指出二叉樹的遍歷是二叉樹其它操作的基礎，但由于篇幅方面的限制，沒有對二叉樹的遍歷作更深刻的介紹，因而學生學習這部分內容時感到十分困難，本文針對這一問題進行討論。

1 二叉樹的遍歷概念

二叉樹的遍歷是指按照一定的規則訪問二叉樹各個接結點，使每個結點都訪問且只能被訪問一次的過程。二叉樹遍歷的實質是將非線性結構的數據線性化的過程，根據訪問的規則（先左后右的順序）不同，可以分為四種先序遍歷、中序遍歷、后序遍歷及層次遍歷。

先序遍歷（Preorder Traversal亦稱(先根遍歷)）二叉樹的操作定義為：若二叉樹為空，則退出，否則，①訪問根結點；②先序遍歷左子樹；③先序遍歷右子樹。

中序遍歷（Inorder Traversal亦稱(中根遍歷)）二叉樹的操作定義為：若二叉樹為空，則退出，否則，①中序遍歷左子樹；②訪問根結點；③中序遍歷右子樹。

后序遍歷（Postorder Traversal亦稱(后根遍歷)）二叉樹的操作定義為：若二叉樹為空，則退出，否則，①后序遍歷左子樹；②后序遍歷右子樹；③訪問根結點。

層次遍歷（Level Traversal）二叉樹的操作定義為：若二叉樹為空，則退出，否則，按照樹的結構，從根開始自上而下，自左而右進行訪問每一個結點，從而實現對每個結點的訪問。

由這四種操作可以得到同一課樹的四個不同的遍歷序列，下面我們將進一步研究四種遍歷有什么聯系？

2 四種遍歷序列的聯系

性質一：已知中序遍歷序列和后序遍歷序列能唯一地確定一棵二叉樹。

證明：①如果后序遍歷序列和中序遍歷序列都是空，則該二叉樹是空樹，而空二叉樹是唯一的；

②如果后序遍歷序列和中序遍歷序列中都只有一個結點，那么該二叉樹是只有一個結點二叉樹，而只有一個結點的二叉樹也是唯一的;

③其它情況，設小于n(n≥2)）個結點的二叉樹可由后序遍歷序列和中序遍歷序列唯一確定。 則對于有n個結點的二叉樹，后序遍歷序列中的最后一個結點必然是該二叉樹的根結點.然后在中序遍歷序列中找到根結點，故根結點可以唯一確定，在中序遍歷序列中根結點后面的結點序列就是根結點右子樹的中序遍歷序列，在后序遍歷序列中根結點前面的屬于中序遍歷序列中根結點后面的那些結點組成的序列就是根結點右子樹的后序遍歷序列。 因為根結點的右子樹至少比原二叉樹少一個結點，所以根據歸納假設可知根結點的右子樹是唯一的；原中序序列中根結點前面的結點序列就是根結點左子樹的中序序列，原后序序列中去掉右子樹后序序列后剩下的結點序列就是根結點左子樹的后序序列，根結點的左子樹至少比原二叉樹少一個結點，根據歸納假設可知根結點的左子樹也是唯一的。

所以對于有 n 個結點的二叉樹也可由后序遍歷序列和中序遍歷序列唯一確定。

由①、②、③可知對于任意個結點的二叉樹都可由后遍歷序列和中序遍歷序列唯一確定。

性質二：已知先序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。

證明原理同1，下面我們用一個例子來說明此性質。

如：先序遍歷序列 ABCDEFG 中序序列CBEDAFG，問是否能確定一棵二叉樹?

分析：由先序遍歷序列ABCDEFG可知A為根結點，由中序序列CBEDAFG可知CBED和FG分別為該二叉樹的左子樹和右子樹結點。

性質三：已知先序遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹。

下面我們用一個反例來證明，已知：先序序列ABCK 后序序列BKCA，問是否能確定一棵二叉樹。

分析：由先序遍歷和后序遍歷只能確定根的結點A，而無法確定A的左子樹和右子樹，故，先序遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹。

性質四：已知一棵二叉樹的層次遍歷序列和中序遍歷序列能唯一確定一棵二叉樹。

證明： ①當n=0時，一棵空二叉樹的中序序列和層次序列都為空，可以唯一確定該二叉樹。命題成立。

②假設當0≤n≤k時命題成立(k≥0)，下面證明當n=k+1時命題也成立。

設一棵二叉樹的中序序列和層次序列分別為b1，b2，b3…bk+1，和d1，d2…dk+1，根據二叉樹的層次序列的定義，d1為根結點，d1在b1，b2，b3……bk+1中出現一次，設bi=d1(1≤i≤k+1)。根據二叉樹的中序序列的定義，i=1，則左子樹的中序序列為空，左子樹的層次序列也為空，若2≤I;≤k+1， 則 b1，b2，b3……bi-1為左子樹的中序序列，將b1，b2，b3……bi-1中的所有結點按其在d1，d2……dk+1中相對次序排列成dp1，dp2……dpi-1 (2＝p1

由①②可知已知一棵二叉樹的層次遍歷序列和中序遍歷序列能唯一確定一棵二叉樹。

推論1：已知一棵二叉樹的層次遍歷序列和先序遍歷序列不能唯一確定一棵二叉樹。

推論2：已知一棵二叉樹的層次遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹。

幾個重要結論：

①前序序列和中序序列相同的二叉樹是：空二叉樹或沒有左子樹的二叉樹(右單支樹)。

②中序序列和后序序列相同的二叉樹是：空二叉樹或沒有右子樹的二叉樹(左單支樹)。

③前序序列和后序序列相同的二叉樹是：空二叉樹或只有根結點的二叉樹。

④前序、中序、后序序列均相同的二叉樹：空樹或只有根結點的二叉樹。

3 利用二叉樹的四種遍歷序列的聯系來解決問題

1) 已知一個非空二叉樹，其按中根和后根遍歷的結果分別為中根：CGBAHEDJFI，后根：GBCHEJIFDA.試將這樣的二叉樹構造出來，若已知先根和后根的遍歷根，能否構造出這樣的二叉樹?為什么? [哈工大研究生試題]

解：有二叉樹的后根遍歷定義可知，后根遍歷序列的最后一個結點為根結點，而此根結點可將對應的中根序列分割為左子樹和右子樹兩部分，然后繼續對每一子樹重復上述的劃分過程直到樹葉結點為止，最終可將完整的二叉樹構造出來。此二叉樹的構造過程如下圖：

如果已知先根和下根的遍歷結果，由性質3可知，由這兩種遍歷序列僅可知道根結點的信息無法區別左右子樹，所以也就無法確定一棵二叉樹。

2) 假設一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列為DBGEHJACIF。請推出這樣二叉樹。（武漢大學研究生試題）

解：層次序列的第一個結點為根結點，而此根結點將對應的中序序列分割為左子樹和右子樹兩部分，然后繼續從左至右掃描層次序列的第二個結點即為子樹的根，再將其對應的中序子樹序列分割為左右子樹兩部分，反復上述操作可構造出對應的二叉樹。此二叉樹的構造過程如下圖：

利用上述方法解題相似題目還有：

1) 證明，由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。設一棵二叉樹的前序序列為ABDGECFH，中序序列為：DGBEAFHC 。試畫出該二叉樹。（浙江大學研究生試題）

2) 一棵樹的先序和后序序列分別如下，畫出該樹。先序序列：ABCDEFGHIJKLM ，后序序列：CDBEFGJKLMIHA（華南理工大學研究生試題）

3) 二叉樹已知其中序掃描序列和后序掃描序列如何確定這一棵二叉樹，并舉例說明。（山東大學研究生試題）

4) 試證明：僅僅已知一棵二叉樹的后序遍歷序列和先序遍歷序列，不能唯一地確定這棵二叉樹。（大連海事大學研究生試題）

5) 由二叉樹的前序遍歷和后序遍歷結果能否唯一確定一棵二叉樹？解釋你的論斷。（西安電子科技大學研究生試題）

4 結束語

二叉樹的遍歷在數據結構中有著重要作用，像求二叉樹的深度，二叉樹的左右子樹，統計葉子個數及波蘭式問題，都可以從二叉樹的遍歷去著手分析，所以說遍歷二叉樹的問題是非常重要，對我們研究有關問題起著很大幫助。

參考文獻：

[1] 齊景嘉.數據結構(含實訓)[M].南京:東南大學出版社，2006.

[2] 王昆侖，李紅.數據結構[M].北京:中國鐵道出版社，2007.

[3] 康牧，陳向奎.怎樣由遍歷序列確定二叉樹[J].洛陽師范學院學報，2003，22(2):56-58.

[4] 唐自立.基于遍歷序列的唯一確定樹或二叉樹的方法[J].小型微型計算機系統，2001，22(8):985-988.