树型结构课件.pptVIP

6.5樹的線性表示

樹的線性表示便於樹的輸入、輸出，同時在存儲時也比較節省存儲空間。本節主要介紹樹的兩種線性表示方法：括弧表示法和層號表示法。

6.5.1樹的括弧表示

1、樹的括弧表示的規則為：

（1）若樹T為空樹，則其括弧表示為空；

（2）若樹T只包含一個結點，則其括弧表示即為該

結點本身；

（3）如果樹T由根結點A和它的m棵子樹T1，T2，……Tm

構成，則其括弧表示為：

A(T1的括弧表示，T2的括弧表示，……Tm的括弧表示)

其中子樹的括弧表示同樣應該遵循以上規則。樹型結構6.1樹的基本概念

樹是由n(n≥0)個結點構成的有限集合，n=0的樹稱為空樹；當n≠0時，樹中的結點應該滿足以下兩個條件：

(1)??有且僅有一個特定的結點稱之為根；

(2)其餘結點分成m(m≥0)個互不相交的有限集合T1,

T2,……Tm，其中每一個集合又都是一棵樹，稱

T1,T2,……Tm為根結點的子樹。

BDEFGAHIJKC圖6.1在樹中採用線段連接兩個相關聯的結點，如A和B，D和H等。其中A和D是上端結點，B和H是下端結點。稱A、D分別是B、H的雙親（或父母或前件），B和H分別為A和D的子女（或孩子或後件）。顯然，雙親和子女的關係是相對而言的。圖6.1中，B是A的子女，但又是E和F的雙親。由於E和F的雙親為同一結點，稱E和F互為兄弟。在任何一棵樹中，除根結點外，其他任何一個結點有且僅有一個雙親，有0個或多個子女，且它的子女恰巧為其子樹的根結點。我們將一結點擁有的子女數稱為該結點的度，樹中所有結點度的最大值稱為樹的度。圖6.1中，A的度為3，B的度為2，而C的度為0，整棵樹的度為3。稱度為0的結點為終端結點或葉子結點，稱度不為0的結點為非終端結點或分支結點。顯然，A、B、D、H均為分支結點，而E、F、C、G、J、K、I均為葉子結點。

稱樹中連接兩個結點的線段為樹枝。在樹中，若從結點Ki開始沿著樹枝自上而下能到達結點Kj，則稱從Ki到Kj存在一條路徑，路徑的長度等於所經過的樹枝的條數。在圖6.1中，從結點A到結點J存在一條路徑，路徑的長度為3；從D到K也存在一條路徑，路徑的長度為2。仔細觀察不難發現，從樹根到樹中任何一個結點均存在一條路徑。

將從樹根到某一結點Ki的路徑中Ki前所經過的所有結點稱為Ki的祖先；反之，以某結點Ki為根的子樹中的任何一個結點都稱為Ki的子孫。圖6.1中，

A、D、H均為J和K的祖先，而G、H、I、J和K均為D的子孫。

樹中結點的層次：從樹根開始定義，根結點為第一層，根的子女結點構成第二層，依次類推，若某結點Kj位於第i層，則其子女就位於第i+1層。稱樹中結點的最大層次數為樹的深度或高度。圖6.1中，A結點位於第一層，B、C、D位於第2層，E、F、G、H和I位於第三層等等，整棵樹的高度為4。

若樹中任意結點的子樹均看成是從左到右有次序的，不能隨意交換，則稱該樹是有序树；否則稱之為無序樹。下圖6.3中的兩棵樹，若看成是有序樹，它們是不等價的；若看成是無序樹，兩者相等。

DCEFABDEFAB由m(m≥0)棵互不相交的樹構成的集合稱為森林。森林和樹的概念十分相近，一棵樹中每個結點，其子樹的集合即為一個森林；而在森林中的每棵樹之上加一個共同的根，森林就成為了一棵樹。C圖6.3有序樹和無序樹的比較樹型結構的其他表示方法：

A(B(E,F),C,D(G,H(J,K),I))

(a)圖6.1的括弧表示法BHJKGIEFDCA(b)圖6.1的嵌套集合表示法ABEFCDGHJKI(C)圖6.1的凹入表示法6.2樹類的定義

ADTtree{

數據對象D：具有相同性質的數據元素構成的有限

集合。

数据关系R：如果D為空或D僅含一個元素，則R為

空；否則D中存在一個特殊的結點root，稱

之為根結點，其無前驅；其他結點被分成互

不相交的m(m?0)個集合，分別構成root的m

棵子樹；若這些子樹非空，