二叉樹創建方法

陳文

（福州職業技術學院，福州 350108）

0 引言

二叉樹是《數據結構與算法》課程的重要內容，它是典型的樹型數據結構[1]，二叉樹的結構及二叉樹的算法已廣泛應用各類程序設計中[2-3]。分析研究二叉樹的應用，首先要基于二叉樹已經創建的前提下進行。因此，二叉樹的創建則是一切二叉樹算法應用的基礎。然而，《數據結構與算法》的教材中，往往注重介紹二叉樹的遍歷方法及二叉樹應用等，對二叉樹的創建并未給出詳細的分析。由于二叉樹的遍歷算法是基于二叉樹已經創建的前提下，而本文所介紹的二叉樹創建方法，卻要用到二叉樹的遍歷等遞歸思想，因此，本文所介紹的二叉樹創建方法是學完二叉樹遍歷等相關理論后，反過來進一步總結與分析二叉樹的創建思想。它是對《數據結構與算法》教材的必要說明與補充。

本文著重介紹二叉樹的創建方法，闡述二叉樹創建的遞歸原理及二叉樹創建的程序框架。并結合樣例驗證其正確性。同時，對學習二叉樹的其他算法具有輔助作用。

1 直接遞歸創建二叉樹

1.1 二叉樹創建分析

以圖1 所示的二叉樹為例，二叉樹的創建可用遞歸法創建。方法如圖1。

圖1 二叉樹樣例圖

首先，創建根結點root，其值為a，再依次創建左子樹及右子樹。即輸入序列如圖2。

圖2

二叉樹的創建遞歸為根結點及左右子樹的創建[4]。

為了使遞歸程序順利執行，必須增加遞歸的出口條件。不妨以“#”字符表示為空結點作為出口條件，則二叉樹可形象表示為圖3。

圖3 補充空結點后的二叉樹

輸入序列為圖4。

圖4

進一步轉化為圖5。

圖5

完整的輸入序列為：abd##eg##h##c#f##。

1.2 程序框架

本文利用C 語言程序設計描述結點的結構與程序框架，通過以上的分析可知：

結點結構：

二叉樹創建的程序框架為：

1.3 程序運行結果

為驗證所創建的二叉樹正確性，可將其前序、中序、后序輸出。二叉樹前序、中序及后序的遍歷方法有眾多資料分析討論[5]，常用的遞歸算法如下：

前序算法：

中序算法：

后序算法：

主程序：

運行結算如圖6 所示。

圖6 運行結果圖

2 利用前序與中序的遍歷結果，構造二叉樹

2.1 二叉樹與前序遍歷的關系

二叉樹與前序遍歷結果存在多對一的關系。如二叉樹1。

圖7 二叉樹1

與二叉樹2。

圖8 二叉樹2

前序遍歷結果均為：abdeghcf。

由此可見，單從二叉樹的前序遍歷無法構建二叉樹。

同樣，單從二叉樹的中序遍歷或后序遍歷也無法構建二叉樹。

2.2 由前序及中序遍歷結果構建二叉樹

由前序及中序遍歷結果可唯一確定二叉樹。以圖1 的二叉樹為例，分析如下：

前序遍歷abdeghcf。

中序遍歷dbgehacf。

由前序遍歷可知：a 為根結點。

再由中序遍歷可知：左子樹序列為dbgeh，右子樹為序列為cf。

于是二叉樹遞歸為圖9。

圖9 遞歸分析圖

遞歸的出口條件為前序或中序序列為空時，該二叉樹為空樹。

2.3 由前序及中序遍歷結果構建二叉樹的程序框架

形參說明：

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 所示。

3 利用后序與中序的遍歷結果，構造二叉樹

程序的基本思想與“利用前序與中序的遍歷結果，構造二叉樹”相似。不再贅述。

4 結語

二叉樹算法中普遍使用遞歸方法，本文提出二叉樹的創建也是基于遞歸思想，因此，二叉樹創建的研究探討，有助于理解遞歸原理。將二叉樹創建與二叉樹其他算法相結合，有助于加深對二叉樹的理解。同時，對提高二叉樹的應用能力無疑具有積極意義。