基于編碼的二叉樹(shù)生成算法

林　成

[摘要]首先介紹二叉樹(shù)的編碼情況,然后提出基于編碼生成的二叉樹(shù)算法,介紹它的算法思路、給出算法的具體步驟描述。

[關(guān)鍵詞]編碼 二叉樹(shù) 堆

中圖分類(lèi)號(hào):TP3文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1671-7597(2009)0810037-01

二叉樹(shù)是計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)與算法分析中重要的非線性數(shù)據(jù)結(jié)構(gòu)之一,被廣泛應(yīng)用于優(yōu)先級(jí)隊(duì)列、分支決策、分類(lèi)學(xué)、計(jì)算機(jī)語(yǔ)言、組合優(yōu)化、形式文法、圖像處理等眾多領(lǐng)域。借助于一定的編碼方法,我們就可以得到一棵二叉樹(shù)對(duì)應(yīng)的編碼,這樣的編碼稱(chēng)作“有效的(Feasible)”編碼。

一、基于編碼的二叉樹(shù)算法

在堆的生成過(guò)程中,對(duì)于第k層上的可能符合條件的2k-1個(gè)節(jié)點(diǎn)值會(huì)進(jìn)行判斷和回溯。當(dāng)k的值不斷增大時(shí),2k-1的值也更快地增大,導(dǎo)致第k層上的判斷時(shí)間也迅速增加。在單個(gè)數(shù)判斷法與層次判斷法的基礎(chǔ)上,采用子樹(shù)生成算法可以有效的減少由k的增大帶來(lái)的枚舉生成所有堆所花費(fèi)的時(shí)間。在算法中用到的一維數(shù)組:(注:以下所用的除號(hào)V/M均為除后取整,如:3/2=1),算法思想如下:

1.數(shù)組t,t_left,t_right。組成堆的n個(gè)數(shù)按從大到小的順序放在一維數(shù)組t中;符合組成左子樹(shù)條件的n_left個(gè)數(shù)按從大到小的順序放在一維數(shù)組t_left中;組成右子樹(shù)的n_right個(gè)數(shù)按從大到小的順序放在一維數(shù)組t_right中。n_left和n_right的內(nèi)容是隨著左右子樹(shù)根節(jié)點(diǎn)的變化而動(dòng)態(tài)變化的。

2.數(shù)組po,po_left,po_right,po_mid。數(shù)組po用來(lái)表示在生成一個(gè)堆的過(guò)程中數(shù)組t中的某個(gè)數(shù)是否已經(jīng)被選擇。如po[f]=0。,則說(shuō)明數(shù)組t中t[f]這個(gè)元素尚未被選中;如果數(shù)組t中的元素t[f]已被選中,則將t[f]這個(gè)元素放在堆中的位置,即在堆中所處的節(jié)點(diǎn)在順序存儲(chǔ)結(jié)構(gòu)數(shù)組t中的編號(hào)放在po[f]中。同樣,po_left,po_right分別表示在生成左右子樹(shù)過(guò)程中t left,t right中的某個(gè)數(shù)是否已經(jīng)被選擇;po_mid用來(lái)在左子樹(shù)生成完成之后,將po和po_left的結(jié)果合并,表示在右子樹(shù)生成之前,哪些數(shù)字已經(jīng)被選中。

3.數(shù)組nch,nch_left,nch_right。因?yàn)槎咽峭耆鏄?shù),已知組成堆的節(jié)點(diǎn)數(shù)目n,則堆的形狀是不變的。堆中編號(hào)為d的節(jié)點(diǎn)的左右子樹(shù)中的孩子節(jié)點(diǎn)總數(shù)是固定的,將此總數(shù)值放在nch[d]中。同理,左子樹(shù)中每個(gè)節(jié)點(diǎn)的左右子樹(shù)的孩子總數(shù)放在數(shù)組nch_left中:右子樹(shù)中每個(gè)節(jié)點(diǎn)的左右子樹(shù)的孩子總數(shù)放在數(shù)組nch_right中。

4.數(shù)組left。將所有可能作為左子樹(shù)根節(jié)點(diǎn)的節(jié)點(diǎn)值按照從大到小的順序存放在一維數(shù)組left中。

除了全局的4個(gè)一維數(shù)組,本算法還用到下面的棧:

s_left,s_right:堆是一種二叉樹(shù),此算法將左右子樹(shù)在生成過(guò)程中每個(gè)節(jié)點(diǎn)的值分別存儲(chǔ)在一維數(shù)組s_left和s_right中,同時(shí)s_left,s right又是順序棧,j_left,j_right分別為棧頂指針。

棧st_left,st right:棧st_left的棧頂指針為top_left,其每個(gè)節(jié)點(diǎn)有兩個(gè)字段,v和ind.v為數(shù)組t中某個(gè)元素的值,ind為該元素在數(shù)組t中的下標(biāo)。根據(jù)上面的敘述,我們知道:如果po_left[st_left[top_left].

ind]=0,則表示v所在的這個(gè)元素在生成左子樹(shù)的過(guò)程中尚未被選中;否則,表示這個(gè)元素在左子樹(shù)中所處節(jié)點(diǎn)的編號(hào)值。同樣,棧st_right表示右子樹(shù)生成過(guò)程中v所在節(jié)點(diǎn)是否已被選中,和選中的編號(hào)值。top_left和top_right為st_left和st_rightd的棧頂指針。

二、子樹(shù)算法描述

其中,n為組成整個(gè)堆元素的總個(gè)數(shù),n_left為左子樹(shù)的元素總個(gè)數(shù),n_right為右子樹(shù)的元素總個(gè)數(shù),則n=n_left+n_right+1;k_left是在生成左子樹(shù)的過(guò)程中的當(dāng)前最大層數(shù),左子樹(shù)的根的層數(shù)規(guī)定為1;k-right是在生成右子樹(shù)的過(guò)程中的當(dāng)前最大層數(shù),右子樹(shù)的根的層數(shù)規(guī)定為1。

1.置初值,把數(shù)組t中的數(shù)按從大到小排序,并且將數(shù)組t中第一個(gè)元素作為整個(gè)堆的根節(jié)點(diǎn),即po[1]=1。根據(jù)單個(gè)數(shù)判斷法的條件,從數(shù)組t中除去根節(jié)點(diǎn)外的元素中尋找出所有可以作為左子樹(shù)根節(jié)點(diǎn)的元素,按從大到小的順序放入數(shù)組left中,元素個(gè)數(shù)放在left[0]中;用h作為數(shù)組left的指針,h=1。

2.從數(shù)組left中選出當(dāng)前的元素作為左子樹(shù)的根節(jié)點(diǎn),s_left[1]=

left[h];如果h>left[0],則結(jié)束算法。

3.從數(shù)組t中,找出所有值小于或者等于s_left[1]的元素,按從大到小的順序放入數(shù)組t left中,用來(lái)生成左子樹(shù)。值得注意的是,數(shù)組t_left的元素個(gè)數(shù)會(huì)大于左子樹(shù)的應(yīng)有的元素個(gè)數(shù)。

4.j_left=j_left+1,如果左子樹(shù)中棧s_left的當(dāng)前節(jié)點(diǎn)指針j_left等于n_left,即左子樹(shù)生成了一個(gè)堆,則轉(zhuǎn)到6。如果top_left=0,說(shuō)明當(dāng)前左子樹(shù)根節(jié)點(diǎn)的所有可能已經(jīng)枚舉完畢,h=h+1轉(zhuǎn)3。

5.開(kāi)始右子樹(shù)的生成:將數(shù)組po和po_left中所有已經(jīng)被選中過(guò)的元素合并放入數(shù)組po_mid中,由此可以將數(shù)組t中尚未被選中的元素按從大到小的順序放入數(shù)組t_fight作為組成右子樹(shù)的元素。t_right中元素個(gè)數(shù)與右子樹(shù)應(yīng)有元素個(gè)數(shù)相同。

6.把數(shù)組t_right中最大的數(shù)t right[1]作為右子樹(shù)根節(jié)點(diǎn),st_rig

ht[1]=t_right[1],po_right[1]=1,j_right=1。

7.j_ right=j_right+1,如果j_right等于n_right,則右子樹(shù)生成了一個(gè)堆,此時(shí)左右子樹(shù)都滿(mǎn)足堆的條件,即整個(gè)堆找到完整的結(jié)果集,轉(zhuǎn)9。

8.如果top right=0,說(shuō)明當(dāng)前左子樹(shù)的情況下,右子樹(shù)所有可能組合已經(jīng)生成完畢,s_left和st_left退棧轉(zhuǎn)5生成左子樹(shù)的下一個(gè)結(jié)果。

9.打印由棧s_left和s_right組成的整個(gè)堆,s_right和st_right退棧轉(zhuǎn)8。

綜上所述基于編碼的二叉樹(shù)算法首先選根;然后生成堆的左子堆中的節(jié)點(diǎn),每當(dāng)左子堆滿(mǎn)足構(gòu)成堆的條件時(shí),就轉(zhuǎn)到右子堆進(jìn)行生成:右子堆也滿(mǎn)足構(gòu)成堆的條件后,將左右子堆和根一起組合成完整的堆。在左右子堆的生成過(guò)程當(dāng)中,由于將堆分成左右兩個(gè)子堆來(lái)生成,也就將生成整個(gè)堆的過(guò)程從生成層數(shù)為k(k為整個(gè)堆的最大層數(shù))的堆,轉(zhuǎn)換為若干次生成k-m(m為多層生成的層數(shù))層的堆的過(guò)程,有效的減少了生成整個(gè)堆所花費(fèi)的時(shí)間,從而提高了枚舉算法的效率。

參考文獻(xiàn):

[1]潘金貴、顧鐵成等,現(xiàn)代計(jì)算機(jī)常用數(shù)據(jù)結(jié)構(gòu)和算法[M].南京大學(xué)出版社,1994.

[2]馬建平,關(guān)于堆結(jié)構(gòu)的研究[D].西安:西北師范大學(xué),2004.

[3]孫強(qiáng)、沈建華、顧君忠,一種生成所有堆的枚舉實(shí)用算法[J].計(jì)算機(jī)工程,2002,28:80-82.