樹結構綜述

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

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

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

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

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