遍歷模式上的經典算法

程序代碼不僅僅是目的，更重要的是繼續學習的方法，特別是像二叉樹、樹和圖的遍歷這樣的包含著存儲結構設計的基礎性算法，應該是分析、設計、實現和解釋復雜算法的工具、要素。本文以垂直輸出二叉樹、快速排序、漢諾塔、生成二叉鏈表的設計和實現為例，說明這個方法。

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

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

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

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

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

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

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

如何把輸出光標移到輸出位置呢？y坐標變化，即層數增加，只要執行換行操作即可。關鍵是如何根據x坐標的變化來移動光標。控制格式化輸出的成員函數ios::width(int)，是按照參數值減去當前輸出光標的縮進量來更新輸出寬度的(而且默認情況下是按右對齊輸出)。以圖26.7為例，假設一個結點已在位置(20，2)上輸出，這時的光標縮進量(假設用indent表示)是20，下一步要在(60，2)的位置上輸出，x坐標是60，這時利用成員函數width(int)來計算的輸出寬度應該是40，即x-indent，用參數表示為width(40)，即width(x-indent)。

struct Location

{

int xindent，ylevel;//結點坐標位置

};

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

{

static int level=0，indent=0;

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

{

level=0;indent=0;

}

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

{

cout<

indent=0; level++;

}

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

indent=x;//記錄當前的縮進量

}

2快速排序與前序遍歷

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

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

3漢諾塔與中序遍歷

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

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

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

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

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

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

假設有兩個盤子，要把兩個盤子從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)為左右孩子的二叉樹的中序遍歷序列，只是訪問結點的結果是，去掉過渡位置，盤子數加括號)(見圖2)。雙親結點與左孩子的關系是，盤子個數減1，過渡位置和終止位置交換，與右孩子的關系是，盤子個數減1，起始位置和過渡位置交換。

假設有n個盤子時結論成立。現在假設有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)為左右子樹根的二叉樹的中序遍歷順序(中序遍歷左子樹，訪問根結點，中序遍歷右子樹)(見圖3(a))。而左右子樹都是n階漢諾塔問題，已假設結論成立。因此對n+1階漢諾塔問題，結論也成立。到此證明完畢。

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

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

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

5小結

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