標(biāo)號樹編解碼的線性算法

摘要：標(biāo)號樹的編碼是一串能夠映射一棵標(biāo)號樹結(jié)構(gòu)的標(biāo)號序列，由于在現(xiàn)代優(yōu)化算法中便于運(yùn)算而常常被采用。本文對四種常見的標(biāo)號樹的編解碼方法進(jìn)行了綜述，并就標(biāo)號樹直觀的邊集表示和編碼表示之間的轉(zhuǎn)換算法進(jìn)行討論，實(shí)現(xiàn)了四種標(biāo)號樹編解碼的線性算法。

關(guān)鍵詞：標(biāo)號樹；Prufer編碼；Nevile編碼；DM編碼

● 引言

標(biāo)號樹是計算機(jī)領(lǐng)域中常見的一種數(shù)據(jù)組織形式，它的傳統(tǒng)存儲方法通常有雙親表示法、孩子表示法、孩子兄弟表示法、邊集表示法等，這些表示方法，在遺傳、粒子群等現(xiàn)代優(yōu)化算法中，由于很難進(jìn)行運(yùn)算，所以很少被使用。而標(biāo)號樹的編碼是一串可以映射一棵標(biāo)號樹的標(biāo)號序列，由于其存儲簡單、便于運(yùn)算，常常被采用，因而對于標(biāo)號樹編碼的深入討論，無論在計算機(jī)的理論還是應(yīng)用上，都有著十分重要的意義。

1918年P(guān)rufer在證明Cayley定理時，最先提出了Prufer編碼，1953年Neville提出了三種編碼方法，其中第一種和Prufer碼一樣，后兩種稱之為Neville2碼、Neville3碼，近年來Deo和Micikevicius又提出了一種新的編碼方法。我們將上述四種編碼簡稱為PR、N2、N3、DM碼。

根據(jù)編碼定義，以上四種編碼除DM編解碼的算法時間為О（n），其他三種都為О（n2）。近年來一些文獻(xiàn)用算法語言給出了它們的線性算法思想。本文在綜述上述四種編解碼規(guī)則之后，用C語言，就標(biāo)號樹直觀的邊集表示和編碼表示之間的轉(zhuǎn)換，給出了編碼和解碼的線性算法。

● 標(biāo)號樹的編碼

1.編碼方法

總的來說，四種編碼方法都是以葉節(jié)點(diǎn)的刪除為基礎(chǔ)，直至只剩下一條邊為止，按照n-2個葉節(jié)點(diǎn)的刪除順序，依次將其在刪除前的鄰接點(diǎn)編號組成一個數(shù)字序列，就是其標(biāo)號樹的編碼。四種編碼的不同在于葉節(jié)點(diǎn)的刪除順序不同。

（1）PR編碼

刪除標(biāo)號樹中最小編號的葉節(jié)點(diǎn)；重復(fù)第一步，直至該標(biāo)號樹剩一條邊。

如圖1所示的標(biāo)號樹，PR編碼的葉子節(jié)點(diǎn)刪除順序應(yīng)為3、4、5、6、8、1、2、9，其相應(yīng)的鄰接點(diǎn)順序?yàn)椋?，10，6，7，1，2，7，7）。

（2）N2編碼

按升序?qū)?biāo)號樹的葉節(jié)點(diǎn)整批刪除；在修正過的標(biāo)號樹上重復(fù)第一步，直至該標(biāo)號樹剩一條邊。

如圖1，N2編碼的葉子節(jié)點(diǎn)刪除順序應(yīng)為第一層的3、4、5、8、9和第二層的1、6、10，其相應(yīng)的鄰接點(diǎn)順序?yàn)椋?，10，6，1，7，2，7，7）。

（3）N3編碼

從最小葉節(jié)點(diǎn)開始，逐個刪除其所在鏈上的節(jié)點(diǎn)，直至該鏈被刪除；重復(fù)第一步，直至該標(biāo)號樹剩一條邊。

如圖1，N3編碼的葉節(jié)點(diǎn)刪除順序應(yīng)為第一條鏈3，第二條鏈4、10，第三條鏈5、6，第四條鏈8、1、2，其相應(yīng)的鄰接點(diǎn)順序?yàn)椋?，10，7，6，7，1，2，7）。

（4）DM編碼

按升序?qū)?biāo)號樹的葉節(jié)點(diǎn)整批刪除；對修正過的標(biāo)號樹按照其葉節(jié)點(diǎn)出現(xiàn)的先后順序進(jìn)行整批刪除；重復(fù)第二步，直至該標(biāo)號樹剩一條邊。

如圖1，DM編碼的葉子節(jié)點(diǎn)刪除順序應(yīng)為第一層的3、4、5、8、9和第二層的10，6，1，其相應(yīng)的鄰接點(diǎn)順序?yàn)椋?，10，6，1，7，7，7，2）。

2.編碼算法

（1）存儲結(jié)構(gòu)

typedef struct node

{ int data；

struct node *next；

} Node；

typedef Node LTree[N+1]；

LTree t；

標(biāo)號樹的存儲結(jié)構(gòu)采用了圖的鄰接表存儲形式，其說明語句如上，標(biāo)號樹的鄰接表存儲示意圖見圖2。將標(biāo)號樹中每個節(jié)點(diǎn)i的度數(shù)存放在t[i]的data域中，將與該節(jié)點(diǎn)i相鄰的所有鄰接點(diǎn)，以鏈表鏈接在t[i]的next域中，為了節(jié)點(diǎn)i和t數(shù)組下標(biāo)的一致，這里數(shù)組的長度定義為N+1。

（2）PR編碼算法

PR編碼算法的思想：在鄰接表t中順序查找出第一個度數(shù)為1的節(jié)點(diǎn)j（t[j].data=1），當(dāng)前最小的葉節(jié)點(diǎn)u=j，求出和u相鄰的節(jié)點(diǎn)v，寫入編碼數(shù)組，刪除最小葉節(jié)點(diǎn)u（t[u].data--，t[v].data--）；比較v和j，如果v

PR編碼算法實(shí)現(xiàn)見函數(shù)PR（ ），c數(shù)組存放標(biāo)號樹的PR編碼；函數(shù)GetAdjvex（ ）實(shí)現(xiàn)標(biāo)號樹t中求解u節(jié)點(diǎn)的鄰接點(diǎn)運(yùn)算。

PR（ LTree t，int c[] ）

{ int i，j，u，v；

u=v=j=0；

for（i=1；i

* { if（v

//找編號最小的葉子節(jié)點(diǎn)u

else

{ while（t[++j].data！=1） ；

u=j；

}

v=GetAdjvex（t，u）； // 找葉子u相鄰節(jié)點(diǎn)v

c[i]=v； //將節(jié)點(diǎn)v寫入c數(shù)組

t[u].data--； t[v].data--； // 刪除邊（u，v）

}

}

int GetAdjvex（LTree t ，int u ）

{ Node *p=t[u].next；

while（ t[p->data].data==0） p=p->next；

//相鄰點(diǎn)度數(shù)為0，表該節(jié)點(diǎn)已刪除

return p->data；

}

函數(shù)形式上雖然是二層循環(huán)，但while循環(huán)所遍歷的t數(shù)組沒有回溯，在整個編碼過程中只遍歷了一遍；另外求鄰接節(jié)點(diǎn)GetAdjvex函數(shù)中雖然也有循環(huán)，但整個編碼過程中鄰接節(jié)點(diǎn)的探查，最多為2N個，所以該編碼算法時間效率是線性的。

（3）N3編碼算法

N3編碼算法的實(shí)現(xiàn)參見函數(shù)PR（），只要在第五行打“*”的條件語句中去掉v

（4）DM編碼算法

DM編碼是按層處理葉節(jié)點(diǎn)的，所以這里借用一個隊(duì)列q數(shù)組進(jìn)行分層處理。

將標(biāo)號樹的所有葉節(jié)點(diǎn)升序加入隊(duì)列q中，之后對q進(jìn)行出隊(duì)運(yùn)算，求隊(duì)頭節(jié)點(diǎn)u的相鄰節(jié)點(diǎn)v，刪除節(jié)點(diǎn)u后的v節(jié)點(diǎn)如變成葉子，則加入q隊(duì)列中。重復(fù)出隊(duì)運(yùn)算直至隊(duì)列q為空。

（5）N2編碼算法

N2編碼和DM編碼相似，也是按層處理葉節(jié)點(diǎn)的，但每層葉子都要升序排列。這里設(shè)計了5個輔助數(shù)組（見圖3），其中隊(duì)列q數(shù)組的作用仍是分層處理，ql數(shù)組存放q數(shù)組中對應(yīng)節(jié)點(diǎn)的層數(shù)（開始為1層，以后逐層加1），數(shù)組tf[u]存放u節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，數(shù)組tl[u]存放u節(jié)點(diǎn)的層次，數(shù)組n[i]存放第i層節(jié)點(diǎn)的統(tǒng)計個數(shù)。

在分層處理結(jié)束后，遍歷數(shù)組tf中的數(shù)據(jù)一次，將每個非0數(shù)據(jù)tf[i]，根據(jù)其在數(shù)組中的先后位置、數(shù)組tl[i]中的層次及數(shù)組n[tl[i]]中該層的統(tǒng)計個數(shù)，可以計算出該數(shù)據(jù)在最后編碼的位置，其編碼算法效率也是線性的。

● 解碼

1.解碼方法

根據(jù)編碼序列，還原標(biāo)號樹的邊集數(shù)據(jù)稱之為解碼。由于編碼序列中的數(shù)據(jù)是和刪除葉節(jié)點(diǎn)對應(yīng)的鄰接點(diǎn)，所以只要找出葉節(jié)點(diǎn)的刪除順序，就可以還原出每條刪除的邊，也就可以還原出原來的標(biāo)號樹結(jié)構(gòu)。

將編碼中的節(jié)點(diǎn)按編碼順序依次存放在集合P中，將不在集合P中的節(jié)點(diǎn)按升序整理到集合NP中，則NP中的節(jié)點(diǎn)即為開始時的葉節(jié)點(diǎn)。

（1）PR解碼

分別取集合P和NP中最左邊的數(shù)據(jù)u、v連接成邊加入到樹中；刪除u、v，如P中不再出現(xiàn)u則把u按升序加入到NP中；重復(fù)第二步驟，直到P為空；將NP中剩下兩節(jié)點(diǎn)編號連接成邊，加入到樹中。

（2）N2解碼

將NP中所有節(jié)點(diǎn)依次和P中左邊數(shù)據(jù)連接成邊加入到樹中，然后分別從P和NP中刪除所有使用過的節(jié)點(diǎn)，將P中刪除掉的而在后邊不再出現(xiàn)的節(jié)點(diǎn)按升序加入NP中；重復(fù)第二步驟，直到P為空；將NP中剩下兩節(jié)點(diǎn)編號連接成邊，加入到樹中。

（3）N3解碼

分別取集合P和NP中最左邊的數(shù)據(jù)u、v連接成邊加入到樹中；刪除u、v，如P中不再出現(xiàn)u則把u插入到NP中最前頭；重復(fù)第二步驟，直到P為空；將NP中剩下兩節(jié)點(diǎn)編號連接成邊，加入到樹中。

（4）DM解碼

將NP中所有節(jié)點(diǎn)依次和P中左邊數(shù)據(jù)連接成邊加入到樹中，然后分別從P和NP中刪除所有使用過的節(jié)點(diǎn)，將P中刪除掉而在后邊不再出現(xiàn)的節(jié)點(diǎn)按順序加入NP中；重復(fù)第二步驟，直到P為空；將NP中剩下兩節(jié)點(diǎn)編號連接成邊加入到樹中。

2.解碼算法

（1）存儲結(jié)構(gòu)

以PR編碼（6，10，6，7，1，2，7，7）的解碼為例，將編碼數(shù)據(jù)存放在c數(shù)組中，統(tǒng)計編碼中各節(jié)點(diǎn)i出現(xiàn)的次數(shù)，將其寫入數(shù)組d中（如圖4），則數(shù)組d中數(shù)據(jù)為0的下標(biāo)，即為不在編碼中的節(jié)點(diǎn)；每找到一條邊，將兩端節(jié)點(diǎn)在數(shù)組d中對應(yīng)的數(shù)據(jù)減1，當(dāng)數(shù)據(jù)為-1時，表示該節(jié)點(diǎn)在NP集合中已刪除，當(dāng)數(shù)據(jù)減為0時，表示該節(jié)點(diǎn)由P集合進(jìn)入NP集合中。

（2）PR解碼算法

PR解碼算法的思想和編碼相同：在數(shù)組d中順序查找出第一個數(shù)據(jù)為0的下標(biāo)j，則當(dāng)前最小的葉節(jié)點(diǎn)u=j，其相鄰節(jié)點(diǎn)v從c數(shù)組中順序讀取，將邊（u，v）寫入邊集數(shù)組e中，刪除u節(jié)點(diǎn)（d[u]--，d[v]--）；比較v和j，如果v

PR解碼算法實(shí)現(xiàn)見函數(shù)PRDecode（ ），在第二個for循環(huán)中，內(nèi)部的while循環(huán)由于沒有回溯，所以時間效率為線性。

void PRDecode（int c[]，int e[][2]）

{

int d[N+1]={0}， u=0，v=0，i，j；

for（i=1；i<=N-1；i++）

d[c[i]]++； //統(tǒng)計編碼中各節(jié)點(diǎn)的個數(shù)

for（i=1，j=0；i<=N-2；i++）

* { if（v

else

{ while（d[++j]） ； u=j；}

v=c[i]；

e[i][0]=u； e[i][1]=v；//將邊（u，v）存入e數(shù)組

d[u]--； d[v]--； // 刪除u，v節(jié)點(diǎn)

}

j=0； // 找NP集合中最后2節(jié)點(diǎn)

while（d[++j]）； u=j；

while（d[++j]）； v=j；

e[i][0]=u； e[i][1]=v；

}

（3）N3解碼算法

N3解碼算法的實(shí)現(xiàn)參見函數(shù)PRDecode（ ），只要在第七行打“*”的條件語句中去掉v

（4）DM解碼算法

DM解碼思想和編碼一樣是按層處理葉子節(jié)點(diǎn)的，所以在算法實(shí)現(xiàn)中引入一個隊(duì)列q進(jìn)行分層處理。DM解碼算法效率是線性的。

（5）N2解碼算法

N2解碼算法思想和DM解碼算法相似，也是按層處理葉子節(jié)點(diǎn)的，但每層葉子需要重新升序排序。

和N2編碼算法設(shè)計一樣，N2解碼設(shè)計了4個輔助數(shù)組，隊(duì)列q數(shù)組、ql數(shù)組、tl數(shù)組、n數(shù)組，它們的作用和N2編碼算法中的輔助數(shù)組一樣。由于編碼順序即為刪除葉節(jié)點(diǎn)的鄰接節(jié)點(diǎn)順序，所以這里無需數(shù)組tf。N2解碼算法的也是線性的。

● 結(jié)束語

本文給出了標(biāo)號樹常用的四種編碼的線性算法，其中DM編解碼的線性算法可以根據(jù)定義直接求得，而其他三種編碼的線性算法借鑒了基數(shù)排序的思想，帶有一定的技巧性。

參考文獻(xiàn)：

[1]王曉東，吳英杰.Prufer編解碼的最優(yōu)算法[J].小型微型計算機(jī)系統(tǒng)，2008，04：687-690.

[2]林志慶，吳英杰，王曉東.Neville編解碼問題的線性時間算法[J].小型微型計算機(jī)系統(tǒng)，2010，10：1984-1988.

[3]Saverio Caminiti，Irene Finocchi，Rossella Petreschi et al. On coding labeled trees[J].Theoretical Computer Science，2007，382（2）：97-108.

[4]Paulius Micikevicius，Saverio Caminiti，Narsingh Deo et al. Linear-time Algorithms for Encoding Trees as Sequences of Node Labels[C]. Congressus Numerantium vol.183.2006：65-75.