樹(shù)的一種線性化算法

林淑飛

(北方民族大學(xué)計(jì)算機(jī)學(xué)院，寧夏銀川750021)

樹(shù)的一種線性化算法

林淑飛

(北方民族大學(xué)計(jì)算機(jī)學(xué)院，寧夏銀川750021)

給出了一種樹(shù)的線性化算法以及從線性化結(jié)果重構(gòu)樹(shù)的算法.這種線性表表示法比樹(shù)的其它表示法更簡(jiǎn)潔、更易管理、更節(jié)約空間.在線性表表示方式下，實(shí)現(xiàn)了樹(shù)的求結(jié)點(diǎn)雙親、求結(jié)點(diǎn)孩子、求樹(shù)的高度3個(gè)運(yùn)算.從具體實(shí)現(xiàn)過(guò)程可以看出，線性表表示法對(duì)樹(shù)的常見(jiàn)運(yùn)算的實(shí)現(xiàn)都比較方便.

數(shù)據(jù)結(jié)構(gòu);樹(shù);線性化;線性表

樹(shù)是一種非線性結(jié)構(gòu).具體地說(shuō)，樹(shù)形結(jié)構(gòu)是一種層次結(jié)構(gòu)，這種層次結(jié)構(gòu)的特點(diǎn)是，任一結(jié)點(diǎn)的前驅(qū)如果存在則一定是唯一的，后繼如果存在則可以有多個(gè).樹(shù)形結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的應(yīng)用十分廣泛，如在編譯程序中，可用樹(shù)表示源程序的語(yǔ)法結(jié)構(gòu);在數(shù)據(jù)庫(kù)系統(tǒng)中，可用樹(shù)來(lái)組織信息;在操作系統(tǒng)中，可用樹(shù)組織文件.

樹(shù)的各種操作的實(shí)現(xiàn)效率具體取決于樹(shù)的表示方式.樹(shù)的表示方式有很多，常用的有雙親表示法、孩子表示法和孩子兄弟表示法等.本文介紹一種線性表表示法，即一種樹(shù)的線性化算法.需要說(shuō)明的是，本文研究的樹(shù)是有序的.

1 樹(shù)的線性化算法

樹(shù)的線性化簡(jiǎn)單地說(shuō)就是將樹(shù)中的結(jié)點(diǎn)用一個(gè)線性表來(lái)表示.線性化樹(shù)要求不能丟失樹(shù)的精確結(jié)構(gòu)［1－2］，即對(duì)于任意結(jié)點(diǎn)應(yīng)該能準(zhǔn)確找到其父結(jié)點(diǎn)(若存在的話)和其所有的孩子結(jié)點(diǎn)(若存在孩子結(jié)點(diǎn)的話).

如果我們?cè)噲D通過(guò)簡(jiǎn)單地按層從上到下的順序列出樹(shù)中的結(jié)點(diǎn)來(lái)線性化樹(shù)，就可能會(huì)丟失樹(shù)的精確結(jié)構(gòu).例如，若用線性表L:(A)(BCD)(EFG) (HI)線性化圖1所示的樹(shù)，就無(wú)法知道F是C的孩子還是D的孩子.出現(xiàn)這種情況的原因是，我們將同一層上具有不同雙親的結(jié)點(diǎn)放在了一個(gè)括號(hào)中.若將線性表L中的(EFG)分成(EF)(G)，即用線性表(A)(BCD)(EF)(G)(HI)表示圖1所示的樹(shù)，仍然有錯(cuò)誤，因?yàn)闊o(wú)法知道E、F是B的孩子，還是C的孩子［3］.避免這個(gè)錯(cuò)誤的一種方式是，如果某個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，但是按照從上到下、從左到右的順序，在它之后有非葉結(jié)點(diǎn)，那么需要用一個(gè)空括號(hào)來(lái)虛擬此葉結(jié)點(diǎn)的孩子.例如，圖1所示的樹(shù)中，B是葉結(jié)點(diǎn)，依從上到下、從左到右的順序，C是在它之后，但C不是葉結(jié)點(diǎn)，所以需用“()”虛擬B的孩子，樹(shù)的線性化結(jié)果為:(A)(BCD)()(EF)(G) (HI)［4－7］.

樹(shù)的這種線性化算法具體描述如下，設(shè)T表示樹(shù)，L表示將T線性化所得的線性表，i為指針，sum為整型變量，初始L為空、sum為0.

Step 1若T為空，則算法結(jié)束;否則轉(zhuǎn)Step 2;

Step 2L=L+“(”+T的根結(jié)點(diǎn)+“)”，并令i指向L的頭元素;

Step 3i向后移動(dòng)，直到遇到一個(gè)T中的結(jié)點(diǎn);

Step 4若i所指結(jié)點(diǎn)不是葉結(jié)點(diǎn)，L=L+“(”+ i所指結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)+“)”;否則L=L+“()”;

Step 5sum=sum+1;

Step 6如果sum等于T的結(jié)點(diǎn)個(gè)數(shù)，轉(zhuǎn)Step 7，否則轉(zhuǎn)Step 3;

Step 7刪除L末尾的若干個(gè)“()”，算法結(jié)束.

2 樹(shù)的重構(gòu)算法

上述樹(shù)的線性化算法所得的線性表，和樹(shù)是一一對(duì)應(yīng)的.1棵樹(shù)可以線性化成1個(gè)唯一的帶若干括號(hào)的線性表，反之也成立.當(dāng)然并不是任意一個(gè)帶若干括號(hào)的線性表都可重構(gòu)成一棵樹(shù).例如，(AB) (CD)就不能重構(gòu)成樹(shù)，因?yàn)楦Y(jié)點(diǎn)不能有2個(gè); (A)(BC)()()(DE)也不能表示一棵樹(shù)，因?yàn)镈、E成了無(wú)前驅(qū)的結(jié)點(diǎn).

下面給出由樹(shù)的線性化算法所得的線性表重構(gòu)樹(shù)的算法.為了說(shuō)明方便，設(shè)L表示線性表，且L以“#”結(jié)束;T用來(lái)描述樹(shù)，T={D，R}(D是結(jié)點(diǎn)的集合，R是關(guān)系的集合，初始D和R均為空).

算法描述如下:

Step 1如果L為空表，則T為空，算法結(jié)束;否則轉(zhuǎn)Step 2;

Step 2如果L只有1個(gè)括號(hào)，則D中增加1個(gè)元素，即樹(shù)的根結(jié)點(diǎn)，R仍為空，算法結(jié)束，否則轉(zhuǎn)Step 3;

Step 3令指針i指向L的第1個(gè)“(”，指針j指向L的第2個(gè)“(”;

Step 4i向后移動(dòng)，直到遇到j(luò)或遇到1個(gè)T中的結(jié)點(diǎn);

Step 5如果i和j相遇，說(shuō)明L不能重構(gòu)成1棵樹(shù)，算法結(jié)束;否則轉(zhuǎn)Step 6;

Step 6D=D+{i所指元素};

Step 7j向后移動(dòng)，指向L的下一個(gè)元素;

Step 8如果j所指元素為“)”，轉(zhuǎn)Step 7;如果j所指元素為“#”，轉(zhuǎn)Step 10;如果j所指為“(”，轉(zhuǎn)Step 4;如果j所指元素為其它，轉(zhuǎn)Step 9;

Step 9R=R+{i所指元素，j所指元素}，轉(zhuǎn)Step 7;

Step 10i向后移動(dòng)，直到遇到“#”或遇到1個(gè)T中的結(jié)點(diǎn);

Step 11如果遇到“#”，算法結(jié)束，否則轉(zhuǎn)Step 12;

Step 12D=D+{i所指元素}，轉(zhuǎn)Step 10.

3 線性化樹(shù)的基本操作

樹(shù)的基本操作有求樹(shù)根、求非根結(jié)點(diǎn)的雙親、求某結(jié)點(diǎn)的孩子、求某結(jié)點(diǎn)的左右兄弟等等.線性化樹(shù)的這些基本操作都是十分方便的，下面以求結(jié)點(diǎn)的雙親、求結(jié)點(diǎn)的孩子、求樹(shù)的高度這3個(gè)操作為例說(shuō)明［8－9］.

3.1 求結(jié)點(diǎn)的所有孩子

從樹(shù)的線性化過(guò)程可以看出，每個(gè)括號(hào)都是用來(lái)存放某個(gè)結(jié)點(diǎn)的所有孩子，包括空括號(hào)，空括號(hào)說(shuō)明某結(jié)點(diǎn)無(wú)孩子.這樣，除了第1個(gè)括號(hào)內(nèi)是根結(jié)點(diǎn)，其余每個(gè)括號(hào)內(nèi)依次存放著每個(gè)結(jié)點(diǎn)的所有孩子，例如，(A)(BC)()(DE)(F)()(GH)(I)所表示的樹(shù)中，A是根結(jié)點(diǎn)，第2個(gè)括號(hào)中的B、C是A的孩子，第3括號(hào)包含著B(niǎo)的孩子(第3個(gè)括號(hào)為空，說(shuō)明B是葉結(jié)點(diǎn))，第4個(gè)括號(hào)包含著C的孩子，第5～8個(gè)括號(hào)分別包含著D、E、F、G的孩子，H和I顯然是葉結(jié)點(diǎn).

所以要求某個(gè)結(jié)點(diǎn)的所有孩子，只需在表示樹(shù)的線性表中確定此結(jié)點(diǎn)是第幾個(gè)結(jié)點(diǎn)，“(”和“)”不計(jì).如果某結(jié)點(diǎn)是第n個(gè)結(jié)點(diǎn)，那么它的孩子就在第n+1個(gè)括號(hào)中.若第n+1個(gè)括號(hào)為空或不存在第n+1個(gè)括號(hào)，說(shuō)明此結(jié)點(diǎn)為葉結(jié)點(diǎn).如在(A) (BC)()(DE)(F)()(GH)(I)中，E是第5個(gè)結(jié)點(diǎn)，所以E的孩子在第6個(gè)括號(hào)內(nèi)，即E是葉結(jié)點(diǎn); G是第7個(gè)結(jié)點(diǎn)，所以G的孩子在第8個(gè)括號(hào)內(nèi)，即I是G的孩子.

3.2 求結(jié)點(diǎn)的雙親

與求結(jié)點(diǎn)的孩子的過(guò)程相逆，欲求某結(jié)點(diǎn)的雙親，先看此結(jié)點(diǎn)在線性表中的第幾個(gè)括號(hào)內(nèi).如果此結(jié)點(diǎn)在第n個(gè)括號(hào)內(nèi)，那么樹(shù)的線性表中第n－1個(gè)結(jié)點(diǎn)就是其雙親，注意“(”和“)”不計(jì)數(shù).例如，在(A)(BC)()(DE)(F)()(GH)(I)中，H是在第7個(gè)括號(hào)內(nèi)，所以H的雙親是第6個(gè)結(jié)點(diǎn)F;D是在第4個(gè)括號(hào)內(nèi)，所以D的雙親是第3個(gè)結(jié)點(diǎn)C.

需要注意的是，如果某個(gè)結(jié)點(diǎn)是在線性表的第n個(gè)括號(hào)內(nèi)，但是線性表中第n－1個(gè)結(jié)點(diǎn)卻在此括號(hào)內(nèi)或后，即在第m(m＞=n)個(gè)括號(hào)中，這樣就說(shuō)明此線性表并不能被重構(gòu)成1棵樹(shù).例如，(A) (BC)()(DE)()()(HI)中，H是在第7個(gè)括號(hào)內(nèi)，但是第6個(gè)結(jié)點(diǎn)也在第7個(gè)括號(hào)內(nèi)，所以此線性表是非法的，并不能表示1個(gè)棵樹(shù).

3.3 求樹(shù)的高度

樹(shù)的高度與表示樹(shù)的線性表中的括號(hào)數(shù)和結(jié)點(diǎn)個(gè)數(shù)有著密切的關(guān)系.所以遍歷線性表的同時(shí)，可計(jì)算出樹(shù)的高度.

計(jì)算樹(shù)的高度的具體方法如下.假設(shè)L表示線性表，以“#”結(jié)束;Depth表示樹(shù)的高度，初值為0; now表示當(dāng)前層的結(jié)點(diǎn)數(shù)，初值為1;i是遍歷L的指針變量;

Step 1i指向L的頭元素;計(jì)數(shù)變量x=0，y=0;

Step 2如果i所指元素為樹(shù)的結(jié)點(diǎn)，則x++;如果i所指元素為“)”，則y++;如果i所指元素為“#”，則轉(zhuǎn)Step 5;

Step 3判斷y與now是否相等.如果y=now，則Depth++，now=x，x=0，y=0;

Step 4i向后移動(dòng)，指向L的下一個(gè)元素，并轉(zhuǎn)Step 2;

Step 5Depth++，算法結(jié)束.

4 結(jié)語(yǔ)

樹(shù)的幾種表示法中，對(duì)樹(shù)的運(yùn)算而言，雙親孩子表示法較其它表示法更方便.但是雙親孩子表示法需要的存儲(chǔ)空間大而且不易管理和操作.本文給出了一種線性化樹(shù)的算法以及從線性化樹(shù)所得的線性表重構(gòu)樹(shù)的算法.從第3節(jié)可以看出，樹(shù)的這種線性化表示，就樹(shù)的取結(jié)點(diǎn)雙親、取結(jié)點(diǎn)孩子這2個(gè)運(yùn)算而言，并不比雙親孩子表示法的復(fù)雜;而就求樹(shù)的高度這個(gè)運(yùn)算來(lái)說(shuō)，比雙親孩子表示要簡(jiǎn)單的多.其實(shí)，這種表示法對(duì)樹(shù)的其它常見(jiàn)運(yùn)算的實(shí)現(xiàn)都比較方便.

［1］HAREL D.算法學(xué)——計(jì)算精髓［M］.3版.霍紅衛(wèi)，譯.北京:高等教育出版社，2007.

［2］萬(wàn)常選，劉喜平.XML數(shù)據(jù)庫(kù)技術(shù)［M］.2版.北京:清華大學(xué)出版社，2008.

［3］MEYER A R，RITCHIE R.The complexity of loop programs［C］//ACM＇67 Proceedings Of The 1967 22nd National Conference.New York:ACM Press，1967.

［4］ZHANG N，KACHOLIA V.A succinct physical storage scheme for efficient evaluation of path queries in XML［C］//Proceeding of the 20th International Conference on Data Engineering(ICDE 2004).Boston:IEEE Computer Society，2004:54－65.

［5］吳恒山，段雄文.葉結(jié)點(diǎn)編碼四叉樹(shù)的鄰域?qū)ふ宜惴ǎ跩］.計(jì)算機(jī)應(yīng)用，2005，25(11):2624－2626.

［6］張群洪，陳崇成.一種改進(jìn)的動(dòng)態(tài)二叉樹(shù)的自組織神經(jīng)網(wǎng)絡(luò)算法［J］.計(jì)算機(jī)應(yīng)用，2007，27(9):2262－2267.

［7］葉曉彤，鄧云.基于唯一二叉樹(shù)的XML函數(shù)表達(dá)式標(biāo)識(shí)轉(zhuǎn)換［J］.計(jì)算機(jī)工程，2009，35(10):75－77.

［8］胡順?lè)?，向云?qiáng).基于JXTA的平面幾何輔助教學(xué)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［J］.云南民族大學(xué)學(xué)報(bào):自然科學(xué)版，2011，20(2):139－143.

［9］宋金歌，楊景，陳平，等.一種非負(fù)矩陣分解的快速稀疏算法［J］.云南民族大學(xué)學(xué)報(bào):自然科學(xué)版，2011，20 (4):262－266.

(責(zé)任編輯莊紅林)

A Linearization Algorithm of the Trees

LIN Shu-fei
(Department of Computer Science，Beifang Ethnic University，Yinchuan 750021，China)

A linearization algorithm of the trees is given.The algorithm with the reconstruction of the trees from the linearization result is designed.This linear representation of the trees is more concise，more space－saving，easier to manage than any other notation.In this linear representation，parent and children of the trees are found and the depth of the trees is calculated.From the process of realization，it has been proved that this method is very convenient in the common operations of the trees.

data structure;trees;linearization;linear list

TP 312

A

1672－8513(2012)04－0298－03

10.3969/j.issn.1672－8513.2012.04.017

2012－03－29.

北方民族大學(xué)基金(2011Y028).

林淑飛(1979－)，女，碩士，講師.主要研究方向:算法分析與設(shè)計(jì).