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

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

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

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

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

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