樹[數據結構名詞]

樹[數據結構名詞]

樹狀圖是一種數據結構,它是由n(n>=1)個有限結點組成一個具有層次關係的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點: 每個結點有零個或多個子結點;沒有父結點的結點稱為根結點;每一個非根結點有且只有一個父結點;除了根結點外,每個子結點可以分為多個不相交的子樹;

基本信息

定義

樹

樹(tree)是包含n(n>=0)個結點的有窮集,其中:

(1)每個元素稱為結點(node);

(2)有一個特定的結點被稱為根結點或樹根(root)。

(3)除根結點之外的其餘數據元素被分為m(m≥0)個互不相交的集合T1,T2,……Tm-1,其中每一個集合Ti(1<=i<=m)本身也是一棵樹,被稱作原樹的子樹(subtree)。

樹也可以這樣定義:樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關係構成的。集合中的元素稱為樹的結點,所定義的關係稱為父子關係。父子關係在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位,這個結點稱為該樹的根結點,或稱為樹根。

我們可以形式地給出樹的遞歸定義如下:

單個結點是一棵樹,樹根就是該結點本身。

設T1,T2,..,Tk是樹,它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親,則得到一棵新樹,結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點,它們都是結點n的子結點。我們還稱T1,T2,..,Tk為結點n的子樹。

空集合也是樹,稱為空樹。空樹中沒有結點。

相關術語

節點的度:一個節點含有的子樹的個數稱為該節點的度;

葉節點或終端節點:度為0的節點稱為葉節點;

非終端節點或分支節點:度不為0的節點;

雙親節點或父節點:若一個節點含有子節點,則這個節點稱為其子節點的父節點;

孩子節點或子節點:一個節點含有的子樹的根節點稱為該節點的子節點;

兄弟節點:具有相同父節點的節點互稱為兄弟節點;

樹的度:一棵樹中,最大的節點的度稱為樹的度;

節點的層次:從根開始定義起,根為第1層,根的子節點為第2層,以此類推;

樹的高度或深度:樹中節點的最大層次;

堂兄弟節點:雙親在同一層的節點互為堂兄弟;

節點的祖先:從根到該節點所經分支上的所有節點;

子孫:以某節點為根的子樹中任一節點都稱為該節點的子孫。

森林:由m(m>=0)棵互不相交的樹的集合稱為森林;

種類

無序樹:樹中任意節點的子結點之間沒有順序關係,這種樹稱為無序樹,也稱為自由樹;

有序樹:樹中任意節點的子結點之間有順序關係,這種樹稱為有序樹;

二叉樹:每個節點最多含有兩個子樹的樹稱為二叉樹;

完全二叉樹

滿二叉樹

霍夫曼樹:帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹;

深度

定義一棵樹的根結點層次為1,其他節點的層次是其父結點層次加1。一棵樹中所有結點的層次的最大值稱為這棵樹的深度。

表示方法

圖像表達法

樹的表示方法有很多種,最常用的是圖像表示法。

一下是一個普通的樹(非二叉樹):

樹[數據結構名詞] 樹[數據結構名詞]

符號表達法

用括弧先將根結點放入一對圓括弧中,然後把它的子樹由左至右的順序放入括弧中,而對子樹也採用同樣的方法處理;同層子樹與它的根結點用圓括弧括起來,同層子樹之間用逗號隔開,最後用閉括弧括起來。如前文樹形表示法可以表示為:(1(2(5(9,10)),3(6,7),4(8)))

遍歷表達法

樹[數據結構名詞] 樹[數據結構名詞]

遍歷表達法有3種方法:先序遍歷、中序遍歷、後序遍歷

例如右圖:

其先序遍歷為ABDECF

其中序遍歷為DBEAFC

其後序遍歷為DEBFCA

具體請參照參考資料

其他

關於二叉樹的其他知識請參照參考資料。

父節點表示法

存儲結構

基本操作

設已有鏈佇列類型LinkQueue的定義及基本操作(參見佇列)。

構造空樹

清空或銷毀一個樹也是同樣的操作

構造樹

判斷樹是否為空

獲取樹的深度

獲取第i個節點的值

改變節點的值

獲取節點的父節點

獲取節點的最左孩子節點

獲取節點的右兄弟節點

輸出樹

向樹中插入另一棵樹

刪除子樹

層序遍歷樹

孩子鍊表表示法

存儲結構

相關詞條

相關搜尋

熱門詞條