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

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

1垂直輸出二叉樹(shù)與層次遍歷

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

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

二叉樹(shù)的第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í)行換行操作即可?！?br>