遍歷模式上的經(jīng)典算法

程序代碼不僅僅是目的，更重要的是繼續(xù)學(xué)習(xí)的方法，特別是像二叉樹、樹和圖的遍歷這樣的包含著存儲結(jié)構(gòu)設(shè)計的基礎(chǔ)性算法，應(yīng)該是分析、設(shè)計、實現(xiàn)和解釋復(fù)雜算法的工具、要素。本文以垂直輸出二叉樹、快速排序、漢諾塔、生成二叉鏈表的設(shè)計和實現(xiàn)為例，說明這個方法。

1垂直輸出二叉樹與層次遍歷

垂直輸出二叉樹的算法可以利用層次遍歷方法1的模式。不同的是，在層次遍歷中對結(jié)點的訪問要改為定位輸出，因此，隊列中的元素不僅要包含結(jié)點指針，而且要包含輸出的位置。

如何確定結(jié)點輸出的位置？顯示器的橫向是X軸，縱向是Y軸，坐標軸的交點在左上角。假設(shè)屏幕寬度(screenwidth)是80。如圖1所示。

二叉樹的第1層只有一個結(jié)點，是根，在(40，1)點輸出。40為偏移量(offset)。

第2層有兩個結(jié)點，分別是上一層結(jié)點的左右孩子，輸出的位置相對其雙親的位置而左右對稱，因此，偏移量應(yīng)該是上一層偏移量的一半(offset=40/2=20)。具體輸出位置分別是(40-offset，2)和(40+offset，2)，即(20，2)和(60，2)。

第3層有四個結(jié)點，分別是上一層的2個結(jié)點(20，2)和(60，2)的左右孩子，偏移量offet=20/2=10，結(jié)點(20，2)的左右孩子的輸出位置分別是(20-offset，3)和(20+offset，3)，即(10，3)和(30，3)， 結(jié)點(60，2) 的左右孩子的輸出位置分別是(60-offset，3)和(60+offset，3)，即(50，3)和(70，3)。

歸納起來，第i層上任一結(jié)點的輸出位置是在訪問第i-1層結(jié)點時，由其雙親的位置確定的。如果其雙親的位置是(parentpos，i-1)，那么該結(jié)點若是左孩子，則輸出位置是(parentpos-offset，i)，若是右孩子，則位置是(parentpos+ offet，i)，其中偏移量offset是上一層偏移量的一半。

如何把輸出光標移到輸出位置呢？y坐標變化，即層數(shù)增加，只要執(zhí)行換行操作即可。關(guān)鍵是如何根據(jù)x坐標的變化來移動光標?？刂聘袷交敵龅某蓡T函數(shù)ios::width(int)，是按照參數(shù)值減去當(dāng)前輸出光標的縮進量來更新輸出寬度的(而且默認情況下是按右對齊輸出)。以圖26.7為例，假設(shè)一個結(jié)點已在位置(20，2)上輸出，這時的光標縮進量(假設(shè)用indent表示)是20，下一步要在(60，2)的位置上輸出，x坐標是60，這時利用成員函數(shù)width(int)來計算的輸出寬度應(yīng)該是40，即x-indent，用參數(shù)表示為width(40)，即width(x-indent)。

struct Location

{

int xindent，ylevel;//結(jié)點坐標位置

};

void Gotoxy(int x，int y)//輸出位置

{

static int level=0，indent=0;

if(y==0)//重復(fù)輸出二叉樹時要重新賦值

{

level=0;indent=0;

}

if(level!=y)//若層數(shù)增加，則縮進量從0開始

{

cout<

indent=0; level++;

}

cout.width(x-indent);//根據(jù)已有縮進量確定當(dāng)前縮進量

indent=x;//記錄當(dāng)前的縮進量

}

2快速排序與前序遍歷

按照樹的集合表示法，二叉樹根的作用在于把集合分成兩部分，一部分代表左子樹結(jié)點，另一部分代表右子樹結(jié)點。

首先，設(shè)計一個劃分數(shù)組元素的算法：以數(shù)組的某一元素為基準，把數(shù)組元素分為前后兩部分，前面的不大于基準，后面的不小于基準，返回值是基準的下標。這個基準相當(dāng)于根。然后按照前序遍歷的順序，對數(shù)組的前后兩部分(左子樹和右子樹)繼續(xù)這種劃分，直到數(shù)組有序(見表2)。

3漢諾塔與中序遍歷

n階漢諾塔問題：有三根石柱，在一根石柱上放著n個盤子，每個盤子都比它下面的小，遵循以下規(guī)則，把盤子移到另一根柱子上：

(1) 每次只能移動一個盤子。

(2) 盤子可以放在任一根柱子上。

(3) 任何時刻，大盤不能壓在小盤之上。

下面用歸納法證明，n階漢諾塔問題可以用n層二叉樹描述，而且它的解就是該二叉樹的中序遍歷序列：

用一個四元組(n，A，B，C)表示這樣一個n階漢諾塔問題：把n個盤子從A柱搬到C柱，中間可以借助B柱。其中A、B、C的地位是相對的，不妨假設(shè)第一個表示起始位置，最后一個表示終止位置，中間表示過渡位置。例如(n，B，A，C)表示把n個盤子從B搬到C，中間可以借助A的n階漢諾塔問題。用一個三元組((n)，A，B)表示把第n個盤子從A直接搬到B。

假設(shè)有兩個盤子，要把兩個盤子從A搬到C，即(2，A，B，C)，就必須先把第1個盤子從A直接搬到B，即((1)，A，B)，再把第2個盤子從A直接搬到C，即 ((2)，A，C)，最后把第1個盤子從B直接搬到C，即((1)，B，C)。序列((1)，A，B)，((2)，A，C)，((1)，B，C)正好是以(2，A，B，C)為根，以(1，A，C，B)和(1，B，A，C)為左右孩子的二叉樹的中序遍歷序列，只是訪問結(jié)點的結(jié)果是，去掉過渡位置，盤子數(shù)加括號)(見圖2)。雙親結(jié)點與左孩子的關(guān)系是，盤子個數(shù)減1，過渡位置和終止位置交換，與右孩子的關(guān)系是，盤子個數(shù)減1，起始位置和過渡位置交換。

假設(shè)有n個盤子時結(jié)論成立。現(xiàn)在假設(shè)有n+1個盤子。要把n＋1個盤子從A搬到C，即(n＋1，A，B，C)，必須先把前n個盤子從A搬到B，即(n，A，C，B)，然后把第n+1個盤子從A直接搬到C，即((n+1)，A，C)，最后把前n個盤子從B搬到C，即(n，B，A，C)。序列(n，A，C，B)，((n+1)，A，C)，(n，B，A，C)正好是以(n+1，A，B，C)為根，以(n，A，C，B)和(n，B，A，C)為左右子樹根的二叉樹的中序遍歷順序(中序遍歷左子樹，訪問根結(jié)點，中序遍歷右子樹)(見圖3(a))。而左右子樹都是n階漢諾塔問題，已假設(shè)結(jié)論成立。因此對n+1階漢諾塔問題，結(jié)論也成立。到此證明完畢。

圖3分別給出了n階和3階漢諾塔問題狀態(tài)樹。3階漢諾塔問題的解用中序序列表示是:((1)，A，C)，((2)，A，B)，((1)，C，A)，((3)，A，C)，((1)，B，A)，((2)，B，C)，((1)，A，C)。

4生成二叉鏈表與后序遍歷

在二叉樹順序存儲結(jié)構(gòu)中，如果一個非0元素的下標是pos，那么該元素的左右孩子下標是2*pos+1和2*pos+2。把二叉樹的順序存儲轉(zhuǎn)為鏈式存儲的算法可以按照層次遍歷的模式完成(見表4)。

5小結(jié)

上述算法的非遞歸代碼都可以和在相應(yīng)的二叉樹遍歷的非遞歸模式中實現(xiàn)。另外，八皇后問題可以在樹的前序遍歷模式中解決，迷宮可以歸于圖的深度有限遍歷，等等，如果需要，請參看清華大學(xué)出版的《C/C++與數(shù)據(jù)結(jié)構(gòu)》(第3版)(下冊)。