基于編碼的二叉樹生成算法

林　成

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

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

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

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

一、基于編碼的二叉樹算法

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

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

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

3.數(shù)組nch,nch_left,nch_right。因為堆是完全二叉樹,已知組成堆的節(jié)點數(shù)目n,則堆的形狀是不變的。堆中編號為d的節(jié)點的左右子樹中的孩子節(jié)點總數(shù)是固定的,將此總數(shù)值放在nch[d]中。同理,左子樹中每個節(jié)點的左右子樹的孩子總數(shù)放在數(shù)組nch_left中:右子樹中每個節(jié)點的左右子樹的孩子總數(shù)放在數(shù)組nch_right中。

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

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

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

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

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

二、子樹算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn):

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

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

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