詹澤梅

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

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

中圖分類號： TP311 文獻標(biāo)識碼：A 文章編號：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ù)據(jù)結(jié)構(gòu)課程內(nèi)容中的重點和難點，學(xué)好數(shù)據(jù)結(jié)構(gòu)就必須要掌握二叉樹的存儲結(jié)構(gòu)和基本操作的算法。二叉樹最常用的存儲結(jié)構(gòu)是二叉鏈表，根據(jù)二叉鏈表的示意圖，我們很容易理解二叉樹的這種存儲形式。因此，掌握二叉樹的關(guān)鍵就是要理解二叉樹基本操作的算法。本文將分析二叉樹操作的遞歸求解方法，以求和數(shù)據(jù)結(jié)構(gòu)愛好者共同學(xué)習(xí)和研究。

2 遞歸

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

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

例如： 求n！

3 二叉樹操作的遞歸求解方法

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

3.1遍歷二叉樹

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

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

3.2 建立二叉樹的二叉鏈表

建立二叉樹的二叉鏈表存儲結(jié)構(gòu)是二叉樹的必備操作，因為在程序中，只有創(chuàng)建了二叉樹的二叉鏈表存儲結(jié)構(gòu)，才可以進行二叉樹的其他操作。顯然，二叉樹中的每個結(jié)點對應(yīng)二叉鏈表中的一個結(jié)點，因此，創(chuàng)建二叉鏈表，就是要為二叉樹中的每個結(jié)點建立一個結(jié)點存儲結(jié)構(gòu)。可以按照某種遍歷順序依次為各個結(jié)點建立存儲結(jié)構(gòu)。若按照中序遍歷順序或后序遍歷順序建立，則在建立二叉鏈表過程中，已建立的結(jié)點是分散的、不能連接成一個鏈表，這就不易掌控所有已建立的結(jié)點。如果按先序遍歷順序建立，則已建立的結(jié)點都可鏈接在根指針?biāo)傅亩骀湵碇?。因此，可按先序遍歷的順序為各個結(jié)點建立存儲結(jié)構(gòu)。

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

3.3 求二叉樹的深度

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

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

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

4 總結(jié)

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

參考文獻：

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

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