詹澤梅

摘要：二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)課程中的重點(diǎn)內(nèi)容。由于二叉樹(shù)本身具有遞歸的特點(diǎn)，因此二叉樹(shù)的許多操作可采用遞歸方法求解。該文首先介紹了遞歸方法，然后采用遞歸方法分析二叉樹(shù)的幾個(gè)常見(jiàn)操作，并給出詳細(xì)算法。

關(guān)鍵詞：遞歸；二叉樹(shù)；遍歷；算法

中圖分類號(hào)： TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）23-0097-02

Abstract： Binary tree is the key content of the data structure course. Because the binary tree itself has the characteristic of recursion， so many operations of the binary tree can be solved by recursive methods. This paper first introduces the recursive method， and then uses the recursive method to analyze several common operations of the binary tree ， and gives the detailed algorithms.

Key words：recursion； binary tree； traversal； algorithm

1概述

二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容中的重點(diǎn)和難點(diǎn)，學(xué)好數(shù)據(jù)結(jié)構(gòu)就必須要掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和基本操作的算法。二叉樹(shù)最常用的存儲(chǔ)結(jié)構(gòu)是二叉鏈表，根據(jù)二叉鏈表的示意圖，我們很容易理解二叉樹(shù)的這種存儲(chǔ)形式。因此，掌握二叉樹(shù)的關(guān)鍵就是要理解二叉樹(shù)基本操作的算法。本文將分析二叉樹(shù)操作的遞歸求解方法，以求和數(shù)據(jù)結(jié)構(gòu)愛(ài)好者共同學(xué)習(xí)和研究。

2 遞歸

遞歸是一種非常有用的算法設(shè)計(jì)工具。一個(gè)函數(shù)、過(guò)程如果在其定義或說(shuō)明內(nèi)部直接地或間接地出現(xiàn)有其本身的引用，這種用自己定義自己的方法稱之為遞歸 [1]。

遞歸方法實(shí)際上是將一個(gè)原問(wèn)題轉(zhuǎn)化為和原問(wèn)題相同的子問(wèn)題，只不過(guò)子問(wèn)題的規(guī)模比原問(wèn)題的規(guī)模要小。這種轉(zhuǎn)換多次進(jìn)行，直到滿足某個(gè)約束條件為止。用遞歸方法求解問(wèn)題關(guān)鍵就是要確定兩方面內(nèi)容：（1）子問(wèn)題（2）遞歸結(jié)束條件。

例如： 求n！

3 二叉樹(shù)操作的遞歸求解方法

二叉樹(shù)的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)（左子樹(shù)和右子樹(shù)），且左右子樹(shù)也是二叉樹(shù)。因此，二叉樹(shù)或者為空，或者可分為三部分：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)。由于二叉樹(shù)中的左子樹(shù)和右子樹(shù)也是二叉樹(shù)，因此，二叉樹(shù)的組成具有遞歸的特點(diǎn)，那么，二叉樹(shù)的許多操作可考慮用遞歸方法來(lái)描述。下面將討論幾個(gè)常見(jiàn)二叉樹(shù)操作的遞歸算法。

3.1遍歷二叉樹(shù)

遍歷二叉樹(shù)是指按某條搜索路徑巡訪二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次[2]。常見(jiàn)的二叉樹(shù)遍歷方法有三種：先序遍歷、中序遍歷、后序遍歷，下面以先序遍歷為例，分析其遞歸算法。

先序遍歷二叉樹(shù)的思想是：若二叉樹(shù)為空，則沒(méi)有任何結(jié)點(diǎn)可訪問(wèn)，因此空操作；當(dāng)二叉樹(shù)不為空時(shí)，先序遍歷二叉樹(shù)就是要：訪問(wèn)根結(jié)點(diǎn)、先序遍歷左子樹(shù)、先序遍歷右子樹(shù)。采用遞歸方法分析：1）原問(wèn)題為先序遍歷二叉樹(shù)。2）原問(wèn)題可分為三步：訪問(wèn)根結(jié)點(diǎn)、先序遍歷左子樹(shù)和先序遍歷右子樹(shù)。訪問(wèn)根結(jié)點(diǎn)直接對(duì)應(yīng)訪問(wèn)語(yǔ)句，例如輸出語(yǔ)句。先序遍歷左子樹(shù)和先序遍歷右子樹(shù)這兩個(gè)問(wèn)題都屬于先序遍歷二叉樹(shù)的問(wèn)題，與原問(wèn)題一樣，只不過(guò)左子樹(shù)和右子樹(shù)比原二叉樹(shù)規(guī)模要小。因此，子問(wèn)題為先序遍歷左子樹(shù)和先序遍歷右子樹(shù)。3）遞歸結(jié)束條件就是二叉樹(shù)為空。

3.2 建立二叉樹(shù)的二叉鏈表

建立二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)是二叉樹(shù)的必備操作，因?yàn)樵诔绦蛑校挥袆?chuàng)建了二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)，才可以進(jìn)行二叉樹(shù)的其他操作。顯然，二叉樹(shù)中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)二叉鏈表中的一個(gè)結(jié)點(diǎn)，因此，創(chuàng)建二叉鏈表，就是要為二叉樹(shù)中的每個(gè)結(jié)點(diǎn)建立一個(gè)結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)?？梢园凑漳撤N遍歷順序依次為各個(gè)結(jié)點(diǎn)建立存儲(chǔ)結(jié)構(gòu)。若按照中序遍歷順序或后序遍歷順序建立，則在建立二叉鏈表過(guò)程中，已建立的結(jié)點(diǎn)是分散的、不能連接成一個(gè)鏈表，這就不易掌控所有已建立的結(jié)點(diǎn)。如果按先序遍歷順序建立，則已建立的結(jié)點(diǎn)都可鏈接在根指針?biāo)傅亩骀湵碇小Ｒ虼?，可按先序遍歷的順序?yàn)楦鱾€(gè)結(jié)點(diǎn)建立存儲(chǔ)結(jié)構(gòu)。

建立二叉樹(shù)的二叉鏈表的算法思想是：若二叉樹(shù)為空樹(shù)，則根指針應(yīng)設(shè)置為空；若二叉樹(shù)非空，則為根結(jié)點(diǎn)建立存儲(chǔ)結(jié)構(gòu)，再建立左子樹(shù)的二叉鏈表和右子樹(shù)的二叉鏈表。采用遞歸方法分析：1）原問(wèn)題為建立二叉樹(shù)的二叉鏈表。2）子問(wèn)題為建立左子樹(shù)的二叉鏈表和建立右子樹(shù)的二叉鏈表。3）遞歸結(jié)束條件是二叉樹(shù)為空樹(shù)。

3.3 求二叉樹(shù)的深度

二叉樹(shù)深度可按如下規(guī)則求?。寒?dāng)二叉樹(shù)為空樹(shù)，則深度為0；當(dāng)二叉樹(shù)只有一個(gè)結(jié)點(diǎn)，則深度為1；否則，二叉樹(shù)的深度為左子樹(shù)深度和右子樹(shù)深度中的較大值，再加上1。采用遞歸方法分析：1）原問(wèn)題為求二叉樹(shù)的深度。2）子問(wèn)題為：求左子樹(shù)深度和求右子樹(shù)深度。3）遞歸結(jié)束條件是二叉樹(shù)為空或者二叉樹(shù)只含有一個(gè)結(jié)點(diǎn)。

3.4 返回結(jié)點(diǎn)e的左兄弟

采用遞歸方法分析：1）原問(wèn)題為在一棵二叉樹(shù)中找結(jié)點(diǎn)e的左兄弟。2）子問(wèn)題可設(shè)定為在左子樹(shù)中找結(jié)點(diǎn)e的左兄弟，和在右子樹(shù)中找結(jié)點(diǎn)e的左兄弟。3）遞歸結(jié)束條件可有兩種情況：a）若二叉樹(shù)為空樹(shù)，則結(jié)點(diǎn)e的左兄弟不存在；b）若根結(jié)點(diǎn)的右孩子為結(jié)點(diǎn)e，則結(jié)點(diǎn)e的左兄弟為根結(jié)點(diǎn)的左孩子。

4 總結(jié)

二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)課程中的重要內(nèi)容，掌握二叉樹(shù)關(guān)鍵是掌握二叉樹(shù)各種操作的算法。本文采用遞歸方法分析了二叉樹(shù)的先序遍歷、創(chuàng)建二叉鏈表、求深度、求結(jié)點(diǎn)e的左兄弟這四個(gè)操作的求解方法。對(duì)于二叉樹(shù)的許多其他操作，也可以與此類似，采用遞歸方法求解。

參考文獻(xiàn)：

[1] 李偉.淺析C語(yǔ)言遞歸算法[J].電腦知識(shí)與技術(shù)，2012（10）.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，2008.