樹的一種線性化算法

林淑飛

(北方民族大學計算機學院，寧夏銀川750021)

樹的一種線性化算法

林淑飛

(北方民族大學計算機學院，寧夏銀川750021)

給出了一種樹的線性化算法以及從線性化結果重構樹的算法.這種線性表表示法比樹的其它表示法更簡潔、更易管理、更節約空間.在線性表表示方式下，實現了樹的求結點雙親、求結點孩子、求樹的高度3個運算.從具體實現過程可以看出，線性表表示法對樹的常見運算的實現都比較方便.

數據結構;樹;線性化;線性表

樹是一種非線性結構.具體地說，樹形結構是一種層次結構，這種層次結構的特點是，任一結點的前驅如果存在則一定是唯一的，后繼如果存在則可以有多個.樹形結構在計算機科學中的應用十分廣泛，如在編譯程序中，可用樹表示源程序的語法結構;在數據庫系統中，可用樹來組織信息;在操作系統中，可用樹組織文件.

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

1 樹的線性化算法

樹的線性化簡單地說就是將樹中的結點用一個線性表來表示.線性化樹要求不能丟失樹的精確結構［1－2］，即對于任意結點應該能準確找到其父結點(若存在的話)和其所有的孩子結點(若存在孩子結點的話).

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

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

Step 1若T為空，則算法結束;否則轉Step 2;

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

Step 3i向后移動，直到遇到一個T中的結點;

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

Step 5sum=sum+1;

Step 6如果sum等于T的結點個數，轉Step 7，否則轉Step 3;

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

2 樹的重構算法

上述樹的線性化算法所得的線性表，和樹是一一對應的.1棵樹可以線性化成1個唯一的帶若干括號的線性表，反之也成立.當然并不是任意一個帶若干括號的線性表都可重構成一棵樹.例如，(AB) (CD)就不能重構成樹，因為根結點不能有2個; (A)(BC)()()(DE)也不能表示一棵樹，因為D、E成了無前驅的結點.

下面給出由樹的線性化算法所得的線性表重構樹的算法.為了說明方便，設L表示線性表，且L以“#”結束;T用來描述樹，T={D，R}(D是結點的集合，R是關系的集合，初始D和R均為空).

算法描述如下:

Step 1如果L為空表，則T為空，算法結束;否則轉Step 2;

Step 2如果L只有1個括號，則D中增加1個元素，即樹的根結點，R仍為空，算法結束，否則轉Step 3;

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

Step 4i向后移動，直到遇到j或遇到1個T中的結點;

Step 5如果i和j相遇，說明L不能重構成1棵樹，算法結束;否則轉Step 6;

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

Step 7j向后移動，指向L的下一個元素;

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

Step 9R=R+{i所指元素，j所指元素}，轉Step 7;

Step 10i向后移動，直到遇到“#”或遇到1個T中的結點;

Step 11如果遇到“#”，算法結束，否則轉Step 12;

Step 12D=D+{i所指元素}，轉Step 10.

3 線性化樹的基本操作

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

3.1 求結點的所有孩子

從樹的線性化過程可以看出，每個括號都是用來存放某個結點的所有孩子，包括空括號，空括號說明某結點無孩子.這樣，除了第1個括號內是根結點，其余每個括號內依次存放著每個結點的所有孩子，例如，(A)(BC)()(DE)(F)()(GH)(I)所表示的樹中，A是根結點，第2個括號中的B、C是A的孩子，第3括號包含著B的孩子(第3個括號為空，說明B是葉結點)，第4個括號包含著C的孩子，第5～8個括號分別包含著D、E、F、G的孩子，H和I顯然是葉結點.

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

3.2 求結點的雙親

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

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

3.3 求樹的高度

樹的高度與表示樹的線性表中的括號數和結點個數有著密切的關系.所以遍歷線性表的同時，可計算出樹的高度.

計算樹的高度的具體方法如下.假設L表示線性表，以“#”結束;Depth表示樹的高度，初值為0; now表示當前層的結點數，初值為1;i是遍歷L的指針變量;

Step 1i指向L的頭元素;計數變量x=0，y=0;

Step 2如果i所指元素為樹的結點，則x++;如果i所指元素為“)”，則y++;如果i所指元素為“#”，則轉Step 5;

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

Step 4i向后移動，指向L的下一個元素，并轉Step 2;

Step 5Depth++，算法結束.

4 結語

樹的幾種表示法中，對樹的運算而言，雙親孩子表示法較其它表示法更方便.但是雙親孩子表示法需要的存儲空間大而且不易管理和操作.本文給出了一種線性化樹的算法以及從線性化樹所得的線性表重構樹的算法.從第3節可以看出，樹的這種線性化表示，就樹的取結點雙親、取結點孩子這2個運算而言，并不比雙親孩子表示法的復雜;而就求樹的高度這個運算來說，比雙親孩子表示要簡單的多.其實，這種表示法對樹的其它常見運算的實現都比較方便.

［1］HAREL D.算法學——計算精髓［M］.3版.霍紅衛，譯.北京:高等教育出版社，2007.

［2］萬常選，劉喜平.XML數據庫技術［M］.2版.北京:清華大學出版社，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］吳恒山，段雄文.葉結點編碼四叉樹的鄰域尋找算法［J］.計算機應用，2005，25(11):2624－2626.

［6］張群洪，陳崇成.一種改進的動態二叉樹的自組織神經網絡算法［J］.計算機應用，2007，27(9):2262－2267.

［7］葉曉彤，鄧云.基于唯一二叉樹的XML函數表達式標識轉換［J］.計算機工程，2009，35(10):75－77.

［8］胡順仿，向云強.基于JXTA的平面幾何輔助教學系統設計與實現［J］.云南民族大學學報:自然科學版，2011，20(2):139－143.

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

(責任編輯莊紅林)

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.

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

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