基于遍歷求二叉樹的程序設計與探討

應沈靜 袁仁斌 陶駿 張海民

摘?要：闡述了非線性數據結構二叉樹的基本概念，介紹了二叉樹的四種遍歷方法，實現了已知前序中序序求二叉樹、已知后序中序序求二叉樹、已知特定前序求二叉樹和已知特定層次遍歷求二叉樹的程序，并對程序進行了詳細的分析。

關鍵詞：非線性;二叉樹;遍歷;前序;后序;層次

1?二叉樹

有一種非線性的邏輯結構被稱為二叉樹，它的特點是其中的每一個結點都最多會擁有兩個直接后繼，而這兩個直接后繼擁有順序關系，一個被稱為左子樹，另一個被稱為右子樹。而左右子樹本身也是二叉樹。因此由特點可以看出，二叉樹是一種遞歸的邏輯結構，具體如圖1：

二叉樹T6的左子樹T5和右子樹T4均為二叉樹，二叉樹T5的左子樹T1也是二叉樹，二叉樹T4的左子樹T2和右子樹T3也是二叉樹。

1.1?二叉樹的存儲

二叉樹的一個結點可能會有兩個直接后繼，所以二叉樹的一個結點需要記錄其左右子樹的情況，二叉樹一般采取二叉鏈表進行存儲，一個結點有三個數據項，一個是數據域，存取結點本身的信息，另外兩個是地址域，存取左右子樹的存儲地址，因為一棵二叉樹是以其根結點作為特征值的，所以這兩個地址域存取其左右子樹根結點的存儲地址，如果沒有左右子樹，這兩個地址域就用空地址（NULL）表示，圖2為圖1二叉樹的二叉鏈表存儲圖：

二叉鏈表也是一種邏輯構造的存儲結構，下表1所表示的是它所對應的真實物理存儲結構（表中的16進制地址由操作系統按照系統情況動態分配的）：

圖3?細化的二叉鏈表示意圖

1.2?二叉樹的遍歷

二叉樹遍歷就是對二叉樹按一定次序進行訪問，并且每個結點僅進行一次訪問。

因為二叉樹不是線性的，所以二叉樹訪問的順序也就會有多種，常見的二叉樹遍歷方式有先序遍歷、中序遍歷、后續遍歷和層次遍歷。

先序遍歷的步驟為：訪問根結點;訪問左子樹;訪問右子樹。在進行左子樹的訪問時，因為左子樹也是一棵二叉樹，所以對于左子樹也要執行先序遍歷，也就是先進行左子樹的根的訪問，再進行左子樹的左子樹的訪問，最后對左子樹的右子樹進行訪問，至子樹的根對應的左右子樹都為空為止。樹的遍歷可以通過遞歸實現，對應的偽代碼如下：

由上可以看出，二叉樹先序遍歷的結果序列為：A、B、D、C、E、F;而中序遍歷的步驟為：訪問左子樹;訪問根;訪問右子樹。因此，圖1的中序遍歷結果為：D、B、A、E、C、F;后序遍歷的步驟為：訪問左子樹;訪問右子樹;訪問根。因此，圖1的后序遍歷結果為：D、B、E、F、C、A;層次遍歷的步驟為：層間自上到下，層內自左到右的對每個結點進行訪問。因此，圖1的層次遍歷為：A、B、C、D、E、F。

2?已知遍歷求二叉樹

已知二叉樹的形狀，則二叉樹的遍歷結果肯定是唯一的。但二叉樹不是線性的，因此獲知二叉樹的一種遍歷結果，是確定不了二叉樹形狀的。當僅知一棵二叉樹的先序遍歷結果為AB時，A是樹根，而B可能是左子樹，也可能是右子樹，所以除了知道二叉樹的一種遍歷結果外，還需要有其他的先提條件才能唯一的確定一棵二叉樹，有四種情況可以確定一棵二叉樹。

2.1?已知前序和后序求二叉樹

設一棵二叉樹有n個結點，它的先序遍歷結果為：a1，a2，a3……an，它的中序遍歷結果為：b1，b2，b3……bn，由先序遍歷可知其第一個元素a1必定是二叉樹的樹根，因此a1是必定會出現在中序遍歷中的，因為中序遍歷也需要訪問樹根，令bk=a1（1<=k<=n），此時bk就將中序遍歷的序列分成了三個部分：樹根是bk，左子樹的中序遍歷結果序列為b1，b2……bk1，總共k1個元素，右子樹的中序遍歷結果序列為bk+1，bk+2……bn，總共nk個元素。對于先序序列來講，中序遍歷左子樹的元素個數與其相同，因此可以得出：a2，a3……ak是左子樹的前序遍歷，其余部分即ak+1，ak+2……an是右子樹的前序遍歷。此時已知左右子樹的前序和后序，這與原問題是同一個性質的，只不過問題規模縮小了，是一個遞歸的問題，利用遞歸一直進行劃分直到二叉樹為空結束再返回，其對應的java源代碼如下：

//二叉樹結點類

public?class?TreeNode?{

//數據域

public?char?data;

//左右子樹

public?TreeNode?lchild，rchild;

//構造函數

public?TreeNode（char?data）

{

this.data=data;

//左右子樹初始為空

this.lchild=null;

this.rchild=null;

}}

//已知前序和中序求二叉樹

public?TreeNode?qzorder（String?qstr，String?zstr）

{

//字符串長度為0則返回空樹

if（qstr.length（）==0||zstr.length（）==0）

return（null）;

else

{

char?c=qstr.charAt（0）;

TreeNode????????p=new

TreeNode（qstr.charAt（0））;

//樹根位置

int?x=zstr.indexOf（c）;

//遞歸求左右子樹

p.lchild=qzorder（qstr.substring（1，（zstr.substring（0，x））.length（）+1），zstr.substring（0，x））;

p.rchild=qzorder（qstr.substring（（zstr.substring（0，x））.length（）+1），zstr.substring（x+1，zstr.length（）））;

return（p）;}}

對于圖1二叉樹的執行過程如圖5所示：

2.2?已知中序和后序求二叉樹

設一棵二叉樹有n個結點，它后序遍歷結果為：a1，a2，a3……an，它中序遍歷結果為：b1，b2，b3……bn，由后序遍歷可知其最后一個元素an必定是二叉樹的樹根，因而an必然出現在中序遍歷中，因為中序遍歷也需要進行訪問樹根，那么令bk=an（1<=k<=n），此時bk把中序遍歷序列分成了三個部分：樹根是bk，左子樹中序遍歷的結果序列為b1，b2……bk1，總共k1個元素，右子樹中序遍歷的結果序列為bk+1，bk+2……bn，總共nk個元素。對于后序序列來講，中序遍歷的左子樹的元素個數與其相同，因此可以得出：a1，a3……ak1是左子樹的后序遍歷，其余部分即ak，ak+1……an1是右子樹的后序遍歷。此時已知左右子樹的中序和后序，這與原問題是同一個性質的，只不過問題規模縮小了，是一個遞歸的問題，利用遞歸一直進行劃分直到二叉樹為空結束再返回，其對應的java源代碼如下：

//已知中序和后序求二叉樹

public?TreeNode?zhorder（String?zstr，String?hstr）

{

//字符串為空返回空樹

if（hstr.length（）==0||zstr.length（）==0）

return（null）;

else

{

//確定樹根

char?c=hstr.charAt（hstr.length（）1）;

TreeNode?p=new?TreeNode（c）;

int?x=zstr.indexOf（c）;

//遞歸求左右子樹

p.lchild=zhorder（zstr.substring（0，x），hstr.substring（0，x））;

p.rchild=zhorder（zstr.substring（x+1），hstr.substring（x，x+zstr.substring（x+1）.length（）））;

return（p）;

}}

對于圖1二叉樹的執行過程如圖6所示：

如果已知后序和前序是不能求出二叉樹的形狀的，因為此時樹根在中序的位置無法確定，例如一棵二叉樹的前序是AB，后序為BA，則A是樹根，B可能是左子樹，也可能是右子樹。

2.3?已知地址域為空的結點和前序求二叉樹

僅已知前序序列是無法求得二叉樹的，但是如果知道地址域為空的結點特征就能和前序序列劃分出左右子樹，對于圖1的二叉樹，每個二叉樹結點的空地址域用#表示，則可表示成圖7：

它通過先序遍歷獲得序列為：ABD###CE##F##，已知此遍歷求二叉樹的java代碼如下：

//count為全局變量，指遍歷字符串位置

private?int?count=0;

//創建二叉樹

public?TreeNode?Dcreate（String?str）

{//取序列結點，每次進一格

char?c=str.charAt（count++）;

TreeNode?p;

if（c！='#'）

{p=new?TreeNode（c）;

//遞歸創建左右子樹

p.lchild=Dcreate（str）;

p.rchild=Dcreate（str）;}

else

//為#則為空地址域

p=null;

return（p）;}

對于圖1二叉樹的執行過程如圖8所示：

圖8?前序空地址域二叉樹生成過程

2.4?按層次遍歷求二叉樹

如果已知層次序列是無法求得二叉樹的，比如二叉樹的層次遍歷序列為ABC，C可能位于二叉樹的第二層，也可能位于二叉樹的第三層，但是如果運用滿二叉樹的形式將二叉樹進行存儲，不存在的結點和結點的空地址域都用特殊字符#表示，每一個結點的順序都與滿二叉樹的結點一一對應，此時根據層次遍歷的序列是可以求得二叉樹的，對于圖1的二叉樹，就可表示成圖9：

圖9?按照滿二叉樹補全的二叉樹

它通過層次遍歷獲得的序列為：ABCD#EF####，已知此序列求二叉樹的代碼如下：

//str為層次遍歷，i是字符位置

public?TreeNode?Lcreate（String?str，int?i）

{?char?c=str.charAt（i）;

TreeNode?p;

if（c！='#'）

{?p=new?TreeNode（c）;

//創建左右子樹

p.lchild=Lcreate（str，2*i+1）;

p.rchild=Lcreate（str，2*i+2）;}

else

//為#時返回空

p=null;

return（p）;}

當前二叉樹的層次遍歷序列按滿二叉樹的形式存儲在字符串中時，根的位置必然是0，因為java語言中字符串是從0號位置開始的。如果當前結點位置為i，若其左子樹存在，左子樹的根的位置必然是2*i+1，這運用數學歸納法就可以證明，假設k為當前結點的序號，第一，當k=0時，其左子樹的根的位置為1，這顯然成立;第二，假設k=i時，其左子樹的根的序號為2*i+1;第三，當k=i+1時，其左子樹的根的左邊是i號結點的右子樹，由假設可知i號結點的左子樹是2*i+1，則i號的右子樹必然是2*i+2，則i+1號的左子樹為2*i+2+1=2*（i+1）+1，成立。同理可證i號結點的右子樹根的序號為2*i+2。當str等于“ABCD#EF####”，圖10就表示圖1的二叉樹其執行過程：

3?結論

本文先介紹了二叉樹的基本概念，二叉樹是數據結構中一種重要的非線性結構，其有遞歸的特性，組成其的子樹和其本身特性相同。介紹了二叉樹的四種遍歷方式，前序為先根再左再右，中序為先左再根再右，后序為先左再右再根，層次指自上到下自左到右訪問二叉樹，設計了四種由遍歷求二叉樹的程序，分別是：已知前序和中序求二叉樹，已知中序和后序求二叉樹，已知特定的前序求二叉樹，已知特定的層次求二叉樹，并詳細分析了程序的實現和驗證。

這四種程序的時間復雜度都是O（N），下一步的工作是利用哈希表改良這些程序以降低這些程序的時間復雜度。

參考文獻：

[1]朱戰立.數據結構Java語言描述[M].北京：清華大學出版社，2005.

[2]趙丹丹.二叉樹的遍歷及還原[J].科技創新導報，2010（7）：225.

[3]黃霞.二叉樹的先序遍歷和中序遍歷的非遞歸算法[J].電腦開發與應用，2010，23（1）：5354，59.

[4]朱戰立.數據結構[M].西安：西安電子科技大學出版社，2003.

[5]胡元義，黑新宏，羅作民，雷西玲，費蓉.數據結構教程[M].北京：電子工業出版社，2018.

[6]鄭逢斌.計算機導論[M].北京：科學出版社，2011.

[7]郝桂芳.由二叉樹的遍歷序列返回二叉樹[J].山西礦業學院學報，1997，15（4）：372375.

[8]楊軍.題解二叉樹的構造[J].學周刊·上旬刊，2016，（3）：165.

[9]康牧，陳向奎.怎樣由遍歷序列確定二叉樹[J].洛陽師范學院學報，2003，22（2）：5658.

基金項目：安徽省教育廳高校優秀青年人才支持計劃項目（項目編號：gxyq2020107）。安徽省教育廳質量工程教學研究一般項目：面向計算機類專業新生的項目設計與實踐（項目編號：2020jyxm0829）。安徽省教育廳高校學科拔尖人才學術資助項目（項目編號：2020jxbjZD2020104）。安徽省科技廳重點研究與開發計劃項目：基于北斗的ADSB?OUT系統國產化研制及關鍵技術研究（項目編號：201904a05020093）。蕪湖市科技項目：基于北斗的ADSB網絡系統研制（項目編號：2019yf49）

作者簡介：應沈靜（2000—?），女，漢族，浙江麗水人，本科，主要研究方向為網絡安全;袁仁斌（2000—?），女，漢族，安徽滁州人，本科，主要研究方向為大數據技術;陶駿（1978—?），男，漢族，安徽蕪湖人，碩士，副教授，高級工程師，主要研究方向為網絡安全;張海民（1983—?），男，漢族，安徽安慶人，碩士，講師，主要研究方向為網絡安全。