樹(shù)結(jié)構(gòu)綜述

1、JSOI2009春季函授講義（A1）第1頁(yè)共53頁(yè)樹(shù)的結(jié)構(gòu)樹(shù)的結(jié)構(gòu)樹(shù)的定義樹(shù)的定義樹(shù)是由一個(gè)集合以及在該集合上定義的一種關(guān)系構(gòu)成的。集合中的元素稱為樹(shù)的結(jié)點(diǎn)，所定義的關(guān)系稱為父子關(guān)系父子關(guān)系。父子關(guān)系在樹(shù)的結(jié)點(diǎn)之間建立了一個(gè)層次結(jié)構(gòu)。在這種層次結(jié)構(gòu)中有一個(gè)結(jié)點(diǎn)具有特殊的地位，這個(gè)結(jié)點(diǎn)稱為該樹(shù)的根結(jié)點(diǎn)，或簡(jiǎn)稱為樹(shù)根。我們可以形式地給出樹(shù)的遞歸定義如下:1.單個(gè)結(jié)點(diǎn)是一棵樹(shù)，樹(shù)根就是該結(jié)點(diǎn)本身。2.設(shè)T1T2..Tk是樹(shù)，它們的根結(jié)點(diǎn)分別為

2、n1n2..nk。用一個(gè)新結(jié)點(diǎn)n作為n1n2..nk的父親，則得到一棵新樹(shù)，結(jié)點(diǎn)n就是新樹(shù)的根。我們稱n1n2..nk為一組兄弟結(jié)點(diǎn)，它們都是結(jié)點(diǎn)n的兒子結(jié)點(diǎn)。我們還稱n1n2..nk為結(jié)點(diǎn)n的子樹(shù)?？占弦彩菢?shù)，稱為空樹(shù)。空樹(shù)中沒(méi)有結(jié)點(diǎn)。一棵典型的樹(shù)如圖1所示：圖1樹(shù)的層次結(jié)構(gòu)由圖1可以看出樹(shù)的形狀就像一棵現(xiàn)實(shí)中的樹(shù)，只不過(guò)是倒過(guò)來(lái)的。樹(shù)的相關(guān)術(shù)語(yǔ)樹(shù)的相關(guān)術(shù)語(yǔ)1.一個(gè)結(jié)點(diǎn)的兒子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。一棵樹(shù)的度是指該樹(shù)中結(jié)點(diǎn)的最大度

3、數(shù)。2.樹(shù)中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。JSOI2009春季函授講義（A1）第3頁(yè)共53頁(yè)圖2兩棵不同的有序樹(shù)我們還可以將兄弟結(jié)點(diǎn)之間的左右次序關(guān)系加以延拓：如果a與b是兄弟，并且a在b的左邊，則認(rèn)為a的任一子孫都在b的任一子孫的左邊。10.森林是m(m0)棵互不相交的樹(shù)的集合。如果我們刪去一棵樹(shù)的樹(shù)根，留下的子樹(shù)就構(gòu)成了一個(gè)森林。當(dāng)我們刪去的是一棵有序樹(shù)的樹(shù)根時(shí)，留下的子樹(shù)也是有序的，這些樹(shù)組成一個(gè)樹(shù)表。在這種情況下，稱這些樹(shù)組

4、成的森林為有序森林或果園。11.在討論表的時(shí)候，我們對(duì)表的每一位置的元素賦予一個(gè)元素值。這里，我們也用樹(shù)的結(jié)點(diǎn)來(lái)存儲(chǔ)元素，即對(duì)于樹(shù)中的每一個(gè)結(jié)點(diǎn)賦予一個(gè)標(biāo)號(hào)，這個(gè)標(biāo)號(hào)并不是該結(jié)點(diǎn)的名稱，而是存儲(chǔ)于該結(jié)點(diǎn)的一個(gè)值。結(jié)點(diǎn)的名稱總是不變的，而它的標(biāo)號(hào)是可以改變的。我們可以做這樣的類比：樹(shù)：表=標(biāo)號(hào)：元素=結(jié)點(diǎn)：位置樹(shù)的數(shù)學(xué)定義樹(shù)的數(shù)學(xué)定義連通無(wú)回路的無(wú)向圖稱為無(wú)向無(wú)向樹(shù)，簡(jiǎn)稱樹(shù)。若該無(wú)向圖至少含有兩個(gè)連通分支，則稱為森林森林。在無(wú)向樹(shù)中，懸掛

5、頂點(diǎn)稱為樹(shù)葉，度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)。設(shè)D是有向圖，若D的基圖是無(wú)向樹(shù)，則稱D為有向有向樹(shù)。設(shè)T是n(n≥2)階有向樹(shù)，若T中有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則稱T為根樹(shù)。入度為0的頂點(diǎn)稱為樹(shù)根，入度為1出度為0的頂點(diǎn)稱為樹(shù)葉，入度為1出度不為0的頂點(diǎn)稱為內(nèi)點(diǎn)內(nèi)點(diǎn)，內(nèi)點(diǎn)和樹(shù)根統(tǒng)稱為分支點(diǎn)分支點(diǎn)。從樹(shù)根到T的任意頂點(diǎn)v的通路（路徑）長(zhǎng)度稱為v的層數(shù)，層數(shù)最大頂點(diǎn)的層數(shù)稱為樹(shù)高。將平凡樹(shù)也稱為根樹(shù)。注意：注意：在計(jì)算機(jī)