陳文

（福州職業(yè)技術(shù)學(xué)院，福州 350108）

0 引言

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

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

1 直接遞歸創(chuàng)建二叉樹

1.1 二叉樹創(chuàng)建分析

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

圖1 二叉樹樣例圖

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

圖2

二叉樹的創(chuàng)建遞歸為根結(jié)點及左右子樹的創(chuàng)建[4]。

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

圖3 補充空結(jié)點后的二叉樹

輸入序列為圖4。

圖4

進一步轉(zhuǎn)化為圖5。

圖5

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

1.2 程序框架

本文利用C 語言程序設(shè)計描述結(jié)點的結(jié)構(gòu)與程序框架，通過以上的分析可知：

結(jié)點結(jié)構(gòu)：

二叉樹創(chuàng)建的程序框架為：

1.3 程序運行結(jié)果

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

前序算法：

中序算法：

后序算法：

主程序：

運行結(jié)算如圖6 所示。

圖6 運行結(jié)果圖

2 利用前序與中序的遍歷結(jié)果，構(gòu)造二叉樹

2.1 二叉樹與前序遍歷的關(guān)系

二叉樹與前序遍歷結(jié)果存在多對一的關(guān)系。如二叉樹1。

圖7 二叉樹1

與二叉樹2。

圖8 二叉樹2

前序遍歷結(jié)果均為：abdeghcf。

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

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

2.2 由前序及中序遍歷結(jié)果構(gòu)建二叉樹

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

前序遍歷abdeghcf。

中序遍歷dbgehacf。

由前序遍歷可知：a 為根結(jié)點。

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

于是二叉樹遞歸為圖9。

圖9 遞歸分析圖

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

2.3 由前序及中序遍歷結(jié)果構(gòu)建二叉樹的程序框架

形參說明：

predata[]、indata[]：前序及中序數(shù)組

pre1、in1：前序序列及中序序列起始位置

len：序列的長度

程序分析：

根結(jié)點字符為ch=predate[pre1]

ch 在中序中的位置loc=lookfor（indata，ch）

則：左子樹序列長度llen=loc-in1

右子樹序列長度rlen=len-llen-1

于是：前序序列predata 各位置元素如圖10。

圖10

中序序列indata 各位置元素如圖11。程序框架：

圖11

其中，函數(shù)lookfor（char*data，char ch）表示從數(shù)組data[]中查找字符ch，具體實現(xiàn)方法如下：

程序運行結(jié)果如上例中的圖6 所示。

3 利用后序與中序的遍歷結(jié)果，構(gòu)造二叉樹

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

4 結(jié)語

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