陳文
(福州職業技術學院,福州 350108)
二叉樹是《數據結構與算法》課程的重要內容,它是典型的樹型數據結構[1],二叉樹的結構及二叉樹的算法已廣泛應用各類程序設計中[2-3]。分析研究二叉樹的應用,首先要基于二叉樹已經創建的前提下進行。因此,二叉樹的創建則是一切二叉樹算法應用的基礎。然而,《數據結構與算法》的教材中,往往注重介紹二叉樹的遍歷方法及二叉樹應用等,對二叉樹的創建并未給出詳細的分析。由于二叉樹的遍歷算法是基于二叉樹已經創建的前提下,而本文所介紹的二叉樹創建方法,卻要用到二叉樹的遍歷等遞歸思想,因此,本文所介紹的二叉樹創建方法是學完二叉樹遍歷等相關理論后,反過來進一步總結與分析二叉樹的創建思想。它是對《數據結構與算法》教材的必要說明與補充。
本文著重介紹二叉樹的創建方法,闡述二叉樹創建的遞歸原理及二叉樹創建的程序框架。并結合樣例驗證其正確性。同時,對學習二叉樹的其他算法具有輔助作用。
以圖1 所示的二叉樹為例,二叉樹的創建可用遞歸法創建。方法如圖1。
圖1 二叉樹樣例圖
首先,創建根結點root,其值為a,再依次創建左子樹及右子樹。即輸入序列如圖2。
圖2
二叉樹的創建遞歸為根結點及左右子樹的創建[4]。
為了使遞歸程序順利執行,必須增加遞歸的出口條件。不妨以“#”字符表示為空結點作為出口條件,則二叉樹可形象表示為圖3。
圖3 補充空結點后的二叉樹
輸入序列為圖4。
圖4
進一步轉化為圖5。
圖5
完整的輸入序列為:abd##eg##h##c#f##。
本文利用C 語言程序設計描述結點的結構與程序框架,通過以上的分析可知:
結點結構:
二叉樹創建的程序框架為:
為驗證所創建的二叉樹正確性,可將其前序、中序、后序輸出。二叉樹前序、中序及后序的遍歷方法有眾多資料分析討論[5],常用的遞歸算法如下:
前序算法:
中序算法:
后序算法:
主程序:
運行結算如圖6 所示。
圖6 運行結果圖
二叉樹與前序遍歷結果存在多對一的關系。如二叉樹1。
圖7 二叉樹1
與二叉樹2。
圖8 二叉樹2
前序遍歷結果均為:abdeghcf。
由此可見,單從二叉樹的前序遍歷無法構建二叉樹。
同樣,單從二叉樹的中序遍歷或后序遍歷也無法構建二叉樹。
由前序及中序遍歷結果可唯一確定二叉樹。以圖1 的二叉樹為例,分析如下:
前序遍歷abdeghcf。
中序遍歷dbgehacf。
由前序遍歷可知:a 為根結點。
再由中序遍歷可知:左子樹序列為dbgeh,右子樹為序列為cf。
于是二叉樹遞歸為圖9。
圖9 遞歸分析圖
遞歸的出口條件為前序或中序序列為空時,該二叉樹為空樹。
形參說明:
predata[]、indata[]:前序及中序數組
pre1、in1:前序序列及中序序列起始位置
len:序列的長度
程序分析:
根結點字符為ch=predate[pre1]
ch 在中序中的位置loc=lookfor(indata,ch)
則:左子樹序列長度llen=loc-in1
右子樹序列長度rlen=len-llen-1
于是:前序序列predata 各位置元素如圖10。
圖10
中序序列indata 各位置元素如圖11。程序框架:
圖11
其中,函數lookfor(char*data,char ch)表示從數組data[]中查找字符ch,具體實現方法如下:
程序運行結果如上例中的圖6 所示。
程序的基本思想與“利用前序與中序的遍歷結果,構造二叉樹”相似。不再贅述。
二叉樹算法中普遍使用遞歸方法,本文提出二叉樹的創建也是基于遞歸思想,因此,二叉樹創建的研究探討,有助于理解遞歸原理。將二叉樹創建與二叉樹其他算法相結合,有助于加深對二叉樹的理解。同時,對提高二叉樹的應用能力無疑具有積極意義。