第3chapter3.1樹的基本概念

1、第3章 樹3.1 樹的基本概念3.2 二叉樹3.3 樹與森林3.4 樹的應(yīng)用樹是n（n0）個(gè)結(jié)點(diǎn)的有限集。當(dāng)n=0時(shí)，稱為空樹；在任意一棵非空樹中滿足如下條件： (1) 有且僅有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 (2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵樹，稱為根root的子樹。 每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 樹的概念結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。 樹的基本術(shù)語葉子(leaf) ：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。

2、分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)。 樹的基本術(shù)語路徑與路徑長(zhǎng)度：路徑的長(zhǎng)度等于路徑所通過的結(jié)點(diǎn)數(shù)目減1(即路徑上分支數(shù)目)。子女結(jié)點(diǎn)、父母結(jié)點(diǎn)、祖先、后繼 樹的基本術(shù)語結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層數(shù)為0，根的孩子層數(shù)為1，依此類推。樹深度：樹中結(jié)點(diǎn)的最大層次。 樹的高度：層數(shù)最大的葉結(jié)點(diǎn)的層數(shù)加1。 0123 樹的基本術(shù)語7樹中的基本術(shù)語有序樹 在樹T中如果子樹T1，T2，Tm的相對(duì)次序是重要的，則稱樹T為有向有序樹，簡(jiǎn)稱有序樹。在有序樹中可以稱T1是根的第一棵子樹，T2是根的第二棵子樹，等等 樹的基本性質(zhì)89 (1) 樹型表示法。這是樹的最基本的表示,使用一棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象。樹的邏輯表示法10(2)文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹結(jié)構(gòu)。樹的邏輯表示法11(3)凹入表示法。使用線段的伸縮描述樹結(jié)構(gòu)。樹的邏輯表示法12(4)括號(hào)表示法(廣義表表示法)。將樹的根結(jié)點(diǎn)寫在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫在括號(hào)中并用逗號(hào)間隔來描述樹結(jié)構(gòu)。樹的邏輯表示法13森林