基于子樹生成的堆枚舉算法.pdf

1、二叉樹是樹型數(shù)據(jù)結(jié)構(gòu)中最基本也最重要的一種，在計(jì)算機(jī)學(xué)科的眾多領(lǐng)域中有著廣泛的應(yīng)用。對(duì)于二叉樹的枚舉的研究，無論在算法理論上還是在實(shí)際應(yīng)用中，都具有重要的意義。 本文首先介紹了現(xiàn)有的四種基于編碼的二叉樹枚舉生成算法，分別是基于樹排列的編碼生成算法、基于旋轉(zhuǎn)的編碼生成算法、廣義模式下的編碼生成算法、和基于文法的編碼生成算法。 堆是一種重要的二叉樹，它被廣泛應(yīng)用于數(shù)據(jù)排序、最短路徑、任務(wù)調(diào)度、最小生成樹等與優(yōu)先級(jí)隊(duì)列相關(guān)的領(lǐng)

2、域。所以，對(duì)于堆的枚舉算法的研究對(duì)相關(guān)應(yīng)用領(lǐng)域會(huì)有很大的幫助。堆的枚舉有兩種含義，一種是計(jì)數(shù)，即計(jì)算出具有某種特性的堆的總數(shù)目；另一種是生成，即一個(gè)一個(gè)地產(chǎn)生具有某種特性的所有具體堆。 本文介紹了各種類型的堆的結(jié)構(gòu)及其發(fā)展，然后介紹了新近發(fā)現(xiàn)的最大值堆的一種性質(zhì)，以及基于這一性質(zhì)提出的一種最大值堆的生成算法。這種采用單個(gè)數(shù)判斷法和層次判斷法的生成算法避免了生成過程中下層節(jié)點(diǎn)的冗余回溯，提高了生成堆的效率。 最后，本文提出

3、一種基于子樹生成的堆枚舉算法?；谧訕渖傻乃惴ǖ乃枷胧菍⑸梢粋€(gè)堆的過程分為：先將堆中最大的節(jié)點(diǎn)作為堆的根，然后分別生成根的左子樹的一個(gè)堆(以下稱為左子堆)和根的右子樹的一個(gè)堆(以下稱為右子堆)，再將根、左子堆、右子堆組合成一個(gè)完整堆的過程。 由于將堆分成左右兩個(gè)子堆來生成，也就將生成整個(gè)堆的過程從生成層數(shù)為k(k為整個(gè)堆的最大層數(shù))的堆，降低到了生成兩個(gè)k-1層的堆，可以有效的減少生成整個(gè)堆所花費(fèi)的時(shí)間，提高枚舉算法的效率。

4、 在基于子樹生成的堆枚舉算法的基礎(chǔ)上，本文進(jìn)一步提出了多層的子樹生成堆的枚舉新算法，以及多層子樹生成堆的新算法的非遞歸實(shí)現(xiàn)方法。多層子樹生成算法是將基于子樹生成的算法分別在原有的左右子堆中再次運(yùn)用，分成更多個(gè)更小規(guī)模的子堆，進(jìn)一步提高生成堆的效率。并且，在程序?qū)崿F(xiàn)過程中可以運(yùn)用循環(huán)的方法來代替遞歸，減少堆棧所占用的系統(tǒng)開銷。 經(jīng)過C程序的對(duì)比實(shí)驗(yàn)得出：同文獻(xiàn)提到的堆的生成算法相比，多層子樹生成算法在嵌套層數(shù)為2、堆的節(jié)點(diǎn)