二叉樹中序遍歷在漢諾塔遞歸算法教學(xué)中的應(yīng)用

楊建華

摘要：遞歸算法是計算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計課程中的重難點，漢諾塔問題是一個使用遞歸算法實現(xiàn)的經(jīng)典問題。現(xiàn)有教材往往側(cè)重于漢諾塔問題的分析及程序?qū)崿F(xiàn)，缺少對遞歸程序復(fù)雜執(zhí)行過程的解析。教學(xué)實踐中將漢諾塔問題求解的遞歸算法與二叉樹的中序遍歷結(jié)合起來，以圖解的方式直觀展示整個遞歸函數(shù)執(zhí)行過程，有助于學(xué)生真正理解遞歸思想，也為教師對漢諾塔遞歸算法的教學(xué)提供新思路。

關(guān)鍵詞：二叉樹;遞歸;漢諾塔;中序遍歷;圖解

中圖分類號：TP301 ? ? ? ?文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）31-0149-03

Abstract： Recursive algorithm is an important and difficult point in computer specialty courses of Data Structure and Program Design. The Tower of Hanoi problem is a classical problem which is solved through recursive algorithm. The existing teaching materials tend to focus on analysis and program realization of the Tower of Hanoi problem， lacking in analysis of the complex execution process of the recursive program. We can combine the Tower of Hanoi recursive algorithm of problem solving and binary tree Inorder traversal in educational practice. The entire recursive function execution process is displayed directly in a graphical way， which helps students understand the idea of recursion， and provides a new idea for the teaching of the Tower of Hanoi recursive algorithm.

Keywords： binary tree; recursive; the Tower of Hanoi; Inorder traversal; diagram

1 引言

程序調(diào)用自身的編程技巧稱為遞歸。遞歸作為一種算法在程序設(shè)計語言中廣泛應(yīng)用。它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸程序代碼精簡、功能強(qiáng)大。在計算機(jī)專業(yè)的數(shù)據(jù)結(jié)構(gòu)、C++語言程序設(shè)計、算法分析等課程中，遞歸會經(jīng)常遇到，現(xiàn)今流行的高級程序設(shè)計語言也都支持函數(shù)的遞歸調(diào)用。所以，教師對遞歸概念的講解是否清楚，會直接影響學(xué)員今后使用遞歸解決實際問題的編程能力?，F(xiàn)有教材中涉及遞歸概念時都會引用經(jīng)典的漢諾塔問題，但經(jīng)研究發(fā)現(xiàn)此類教材對漢諾塔問題的描述側(cè)重于漢諾塔金片搬運過程的分析及編程實現(xiàn)，而對程序的復(fù)雜遞歸調(diào)用執(zhí)行過程缺乏解析，不便于學(xué)員理解。為此，在教學(xué)實踐中，將漢諾塔遞歸算法與二叉樹中序遍歷結(jié)合起來，以二叉樹中序遍歷圖解來模擬漢諾塔遞歸程序的復(fù)雜調(diào)用過程。

2 漢諾塔問題

2.1原始問題

法國數(shù)學(xué)家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。[1]

2.2抽象成數(shù)學(xué)問題

將原始問題抽象成數(shù)學(xué)問題：有三根針A、B、C，初始時A針上有64個圓盤，圓盤大小不一，小的在上，大的在下;B、C針上無圓盤（如圖1所示），要求把A針上64個圓盤移到C針上。移動時遵循3條規(guī)則：（1）只給一個中間過渡用針（稱針B）;（2）每次只能移動一個圓盤;（3）任何時候，都要保持小盤在上，大盤在下。[2]試編程求出移動步驟與步數(shù)。

2.3遞歸求解思路

設(shè)圓盤總個數(shù)為N，從上至下給圓盤編號為1～N。當(dāng)N=1時，直接將編號為1的圓盤從A針移動到C針;當(dāng)N=2時，先將編號為1的圓盤從A針移動到B針，再將編號為2的圓盤從A針移動到C針，最后將編號為1的圓盤從B針移動到C針;當(dāng)N>2時，可以將A針上編號1～N-1的圓盤看作一個整體，整個搬運過程與N=2時類似，也分為三個步驟：

（1） 借助C針將A針上這N-1個圓盤移動到B針上;

（2） 將A針上最大的圓盤直接移動到C針上;

（3） 借助A針將B針上N-1個圓盤移動到C針上。

同樣，對于這N-1個圓盤的移動方法遞歸上述搬運過程。

2.4 ?漢諾塔問題的C語言實現(xiàn)代碼

#include "stdio.h"

int i=1;//全局變量，記錄移動步數(shù)

void hanoi（int n，char a，char b ，char c）;

void main（）

{

int n;

char a='A'，b='B'，c='C';

printf（"請輸入圓盤的個數(shù)：＼n"）;

scanf（"%d"，&n）;

printf（"圓盤總數(shù)為%d時移動情況如下：＼n"，n）;

hanoi（n，a，b，c）;

}

void hanoi（int n，char a，char b，char c）

{ //算法里（1）～（4）是為了說明執(zhí)行過程加入的標(biāo)號

（1） if（n==0） return;

（2） hanoi（n-1，a，c，b）;

（3） printf（"第%d步：將%d號圓盤%c-->%c＼n"，i++，n，a，c）;

（4） hanoi（n-1，b，a，c）;

}

程序運行時結(jié)果如圖2所示：

3 二叉樹中序遍歷模擬漢諾塔遞歸程序執(zhí)行過程

3.1二叉樹的中序遍歷

所謂遍歷就是按照一定的順序依次訪問樹中的每一個結(jié)點，而且每個結(jié)點只被訪問一次。[3]二叉樹中序遍歷的遞歸算法定義如下：

若二叉樹非空，則依次執(zhí)行如下操作：

⑴遍歷左子樹;

⑵訪問根結(jié)點;

⑶遍歷右子樹。

按中序遍歷圖3所示的二叉樹，結(jié)點信息輸出順序為：D-H-B-I-E-A-J-F-K-C-G。

3.2 二叉樹的中序算法實現(xiàn)

用二叉鏈表作為存儲結(jié)構(gòu)，中序遍歷算法可描述為：

void InOrder（BinTree T）

{ //算法里（1）～（4）是為了說明執(zhí)行過程加入的標(biāo)號

（1） if（T==NULL） ?return;//如果是空結(jié)點，返回

（2） InOrder（T->lchild）;//遍歷左子樹

（3） printf（"%c"，T->data）; // 訪問結(jié)點內(nèi)容

（4） InOrder（T->rchild）;//遍歷右子樹

}

3.3 漢諾塔遞歸算法與二叉樹中序遍歷算法的共同點

將hanoi函數(shù)與InOrder函數(shù)進(jìn)行對比，會發(fā)現(xiàn)除代碼表達(dá)的問題含義不同外，其代碼結(jié)構(gòu)完全一致。兩個函數(shù)中語句（1）都是遞歸結(jié)束語句;語句（2）、（4） 都為遞歸到下一層的函數(shù)調(diào)用;語句（3）都是一條輸出信息語句。據(jù)此共同點，可以將漢諾遞歸執(zhí)行過程轉(zhuǎn)換成二叉樹的中序遍歷過程。教學(xué)實踐中啟發(fā)學(xué)生將hanoi函數(shù)中的語句（2）理解為訪問左子樹，語句（3）理解為輸出結(jié)點信息，語句（4）理解為訪問右子樹。

3.4圖解模擬漢諾塔程序的遞歸執(zhí)行過程

教學(xué)實踐中取漢諾塔圓盤總數(shù)為4進(jìn)行模擬，以主函數(shù)中hanoi（4，A，B，C）為根結(jié)點，為作圖方便省略函數(shù)名，同時注意參數(shù)的傳遞變化規(guī)律。

整個遞歸程序執(zhí)行過程見圖4中的虛線路徑，程序從根結(jié)點開始，不斷沿左子樹遍歷到結(jié)點、結(jié)點、結(jié)點，當(dāng)?shù)竭_(dá)葉子結(jié)點時，此時參數(shù)n=1，再往下層遞歸時由于n=0，直接返回，程序執(zhí)行時只是輸出結(jié)點信息：“第1步，將1號圓盤A-->B”，然后返回到結(jié)點代表的函數(shù)體語句（3），執(zhí)行結(jié)點的信息輸出，再遍歷結(jié)點的右子樹，輸出葉子結(jié)點的信息…… 按二叉樹的中序遍歷會依次輸出結(jié)點至的信息，輸出結(jié)果與圖2中程序?qū)嶋H執(zhí)行結(jié)果完全一致。

通過對圖4的觀察，能得到漢諾塔問題的求解步數(shù)，編號為4的圓盤搬運了2（4-4）=1次，編號為3的圓盤搬運了2（4-3）=2次，編號為2的結(jié)點搬運了2（4-2）=4次，編號為1的結(jié)點搬運了2（4-1）=8次。推廣到圓盤總數(shù)為N時，編號為i的圓盤搬運次數(shù)為2（n-i）次，總搬運次數(shù)為20+21+22+ ……+2N-1=2N-1次。

4 結(jié)束語

通過二叉樹中序遍歷將漢諾塔復(fù)雜的遞歸調(diào)用過程圖形化，使學(xué)生對遞歸復(fù)雜的調(diào)用、返回有了感性的認(rèn)識，加深了對遞歸思想的深入理解。以安徽廣播電視大學(xué)2019春、2019秋兩屆計算機(jī)本科專業(yè)學(xué)員為教學(xué)對象，分別采用傳統(tǒng)方式與二叉樹中序遍歷圖解法講解漢諾塔遞歸算法，課后完成相同的練習(xí)，得出采用新方法教學(xué)，學(xué)員正確率提高近30%，教學(xué)效果顯著提升。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007：54-55.

[2] 張海峰.“遞歸”與“漢諾塔”的直觀教學(xué)演示[J].中原工學(xué)院學(xué)報，2004，15（3）：35-39.

[3] 吳鶴齡.程序設(shè)計基礎(chǔ)[M].北京：中央廣播電視大學(xué)出版社，2004：148.

【通聯(lián)編輯：王力】