常用數據邏輯結構

集合——數據元素間除“同屬于一個集合”外，無其它關系

線性結構——一個對一個，如線性表、棧、隊列

樹形結構——一個對多個，如樹

圖形結構——多個對多個，如圖

樹形結構特點：非線性結構，只有一個直接前驅，

但可能有多樹形結構特點：非線性結構，只有一個直接前驅，

但可能有多個直接后繼（1：n）個直接后繼（1：n）

樹型結構（非線性結構）：結點之間一對多關系、具有層次關系

樹型結構是一類非常重要的非線性結構。直觀地，樹型結構是以分支關系定義的層次結構。

樹的定義   

樹(tree)是由n(n≥0)個結點組成的有限集合T。n=0的樹稱為空樹；對n>0的樹，有:

(1)僅有一個特殊的結點稱為根(root)結點，根結點沒有前驅結點；

(2)當n>1時，除根結點外其余的結點分為m(m>0)個互不相交的有限集合T1,T2，…，Tm，其中每個集合Ti本身又是一棵樹，稱之為根的子樹（subtree）。

注：樹的定義具有遞歸性，即“樹中還有樹”；僅有一個根結點的樹是最小樹;

樹的基本術語——從結構上分

結點（node）：由數據元素和構造數據元素之間關系的指針組成

結點的度：結點所擁有的子樹的個數

樹的度：樹中所有結點的度的最大值

葉結點：度為0的結點，也稱作終端結點

分支結點：度不為0的結點，除葉結點之外的其余結點。

結點的層次：從根結點到樹中某結點所經路徑上的分支數

規定樹中根結點的層次為1，其余結點的層次等于其雙親結點的層次加1。若某結點在第l(l≧1)層，則其子結點在第l+1層。

樹的深度：樹中所有結點的層次的最大值

森林：m（m≥0）棵樹的集合

樹的基本術語——從關系上分

從根結點開始，到達某結點p所經過的所有結點成為結點p的層次路徑(有且只有一條)。

結點p的層次路徑上的所有結點（p除外）稱為p的祖先(ancester)。

以某一結點為根的子樹中的任意結點稱為該結點的子孫結點(descent)。

孩子(child)結點：樹中一個結點的子樹的根結點

雙親(parent)結點：若樹中某結點有孩子結點，則這個結點就稱作它的孩子結點的雙親結點

兄弟(sibling)結點：具有相同的雙親結點的結點

樹的基本術語——從結構上分

無序樹：樹中任意一個結點的各孩子結點之間的次序構成    無關緊要的樹

有序樹：樹中任意一個結點的各孩子結點有嚴格排列次序的樹

樹的表示形式

⑴  倒懸樹。是最常用的表示形式。

⑵ 嵌套集合（文氏圖）。是一些集合的集體，對于任何兩個集合，或者不相交，或者一個集合包含另一個集合。

⑶ 廣義表形式。

⑷  凹入法表示形式（凹入表）。

樹的表示方法的多樣化說明了樹結構的重要性。

樹的存儲結構

定長結點的多重鏈表結構

不定長結點的多重鏈表結構

不定長的結點存貯法不便于操作。

定長結點存貯法浪費空間。

假設樹有n個結點，樹的度為k，那么，共有nk個鏈域，使用了n-1個鏈域，浪費的鏈域數為 （nk– n +1），浪費的比例= (nk– n +1 ) / nk趨向于1

結論：度為2的樹最節省存貯空間。