二叉樹操作的遞歸算法分析

詹澤梅

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

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

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

2 遞歸

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

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

例如： 求n！

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

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

3.1遍歷二叉樹

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

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

3.2 建立二叉樹的二叉鏈表

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

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

3.3 求二叉樹的深度

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

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

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

4 總結(jié)

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

參考文獻(xiàn)：

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

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