形數(shù)

在計(jì)算機(jī)科學(xué)中，樹（tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋?lái)像一棵倒掛的樹，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；

沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；

每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；

除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；

樹形數(shù)據(jù)結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。樹形數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域中有著廣泛應(yīng)用，如在編譯程序中，可用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)。 又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹形數(shù)據(jù)結(jié)構(gòu)也是信息的重要組織形式之一。以及在文件管理中，多級(jí)目錄結(jié)構(gòu)就采用樹形數(shù)據(jù)結(jié)構(gòu)。

半圓以它的直徑為旋轉(zhuǎn)軸，旋轉(zhuǎn)所成的曲面叫做球面。球面所圍成的幾何體叫做球體，簡(jiǎn)稱球。半圓的圓心叫做球心。連結(jié)球心和球面上任意一點(diǎn)的線段叫做球的半徑。連結(jié)球面上兩點(diǎn)并且經(jīng)過(guò)球心的線段叫做球的直徑。用一個(gè)平面去截一個(gè)球，截面是圓面。球的截面有以下性質(zhì)：

1） 球心和截面圓心的連線垂直于截面；

2） 球心到截面的距離

球面被經(jīng)過(guò)球心的平面截得的圓叫做大圓，被不經(jīng)過(guò)球心的截面截得的圓叫做小圓。

在球面上，兩點(diǎn)之間的最短連線的長(zhǎng)度，就是經(jīng)過(guò)這兩點(diǎn)的大圓在這兩點(diǎn)間的一段劣弧的長(zhǎng)度，我們把這個(gè)弧長(zhǎng)叫做兩點(diǎn)的球面距離。

1、結(jié)點(diǎn)(Node)：表示樹中的數(shù)據(jù)元素，由數(shù)據(jù)項(xiàng)和數(shù)據(jù)元素之間的關(guān)系組成。在圖1中，共有10個(gè)結(jié)點(diǎn)。

2、結(jié)點(diǎn)的度(Degree of Node)：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)，在圖1中，結(jié)點(diǎn)A的度為3。

3、樹的度(Degree of Tree)：樹中各結(jié)點(diǎn)度的最大值。在圖1中，樹的度為3。

4、葉子結(jié)點(diǎn)(Leaf Node)：度為0的結(jié)點(diǎn)，也叫終端結(jié)點(diǎn)。在圖1中，結(jié)點(diǎn)E、F、G、H、I、J都是葉子結(jié)點(diǎn)。

5、分支結(jié)點(diǎn)(Branch Node)：度不為0的結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)。在圖1中，結(jié)點(diǎn)A、B、C、D是分支結(jié)點(diǎn)。

6、孩子(Child)：結(jié)點(diǎn)子樹的根。在圖1中，結(jié)點(diǎn)B、C、D是結(jié)點(diǎn)A的孩子。

7、雙親(Parent)：結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親。在圖1中，結(jié)點(diǎn)B、C、D的雙親是結(jié)點(diǎn)A。

8、祖先(Ancestor)：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。在圖1中，結(jié)點(diǎn)E的祖先是A和B。

9、子孫(Descendant)：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)。在圖1中，除A之外的所有結(jié)點(diǎn)都是A的子孫。

10、兄弟(Brother)：同一雙親的孩子。在圖1中，結(jié)點(diǎn)B、C、D互為兄弟。

11、結(jié)點(diǎn)的層次(Level of Node)：從根結(jié)點(diǎn)到樹中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)稱為該結(jié)點(diǎn)的層次。根結(jié)點(diǎn)的層次規(guī)定為1，其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1。

12、堂兄弟(Sibling)：同一層的雙親不同的結(jié)點(diǎn)。在圖1中，G和H互為堂兄弟。

13、樹的深度(Depth of Tree)：樹中結(jié)點(diǎn)的最大層次數(shù)。在圖1中，樹的深度為3。

14、無(wú)序樹(Unordered Tree)：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的次序構(gòu)成無(wú)關(guān)緊要的樹。通常樹指無(wú)序樹。

15、有序樹(Ordered Tree)：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹。二叉樹是有序樹，因?yàn)槎鏄渲忻總€(gè)孩子結(jié)點(diǎn)都確切定義為是該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)還是右孩子結(jié)點(diǎn)。

16、森林(Forest)：m(m≥0)棵樹的集合。自然界中的樹和森林的概念差別很大，但在數(shù)據(jù)結(jié)構(gòu)中樹和森林的概念差別很小。從定義可知，一棵樹有根結(jié)點(diǎn)和m個(gè)子樹構(gòu)成，若把樹的根結(jié)點(diǎn)刪除，則樹變成了包含m棵樹的森林。當(dāng)然，根據(jù)定義，一棵樹也可以稱為森林。