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

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

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

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

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

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

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

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

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

struct Location

{

int xindent，ylevel;//結(jié)點(diǎn)坐標(biāo)位置

};

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

{

static int level=0，indent=0;

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

{

level=0;indent=0;

}

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

{

cout<

indent=0; level++;

}

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

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

}

2快速排序與前序遍歷

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

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

3漢諾塔與中序遍歷

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

(1) 每次只能移動(dòng)一個(gè)盤子。

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

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

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

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

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

假設(shè)有n個(gè)盤子時(shí)結(jié)論成立?，F(xiàn)在假設(shè)有n+1個(gè)盤子。要把n＋1個(gè)盤子從A搬到C，即(n＋1，A，B，C)，必須先把前n個(gè)盤子從A搬到B，即(n，A，C，B)，然后把第n+1個(gè)盤子從A直接搬到C，即((n+1)，A，C)，最后把前n個(gè)盤子從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)為左右子樹根的二叉樹的中序遍歷順序(中序遍歷左子樹，訪問(wèn)根結(jié)點(diǎn)，中序遍歷右子樹)(見圖3(a))。而左右子樹都是n階漢諾塔問(wèn)題，已假設(shè)結(jié)論成立。因此對(duì)n+1階漢諾塔問(wèn)題，結(jié)論也成立。到此證明完畢。

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

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

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

5小結(jié)

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