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

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

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

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

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

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