樹形數據結構是一類重要的非線性數據結構。樹形數據結構可以表示數據表素之間一對多的關係。其中以樹與二叉樹最為常用，直觀看來，樹是以分支關係定義的層次結構。樹形數據結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形數據結構來形象表示。
基本介紹
- 中文名：樹形數據結構
- 外文名：Tree Data Structure
- 學科：計算機
- 定義：非線性數據結構
- 有關術語：樹
- 領域：數據結構
簡介,相關術語,多級目錄結構,
簡介
在計算機科學中，樹（tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>0）個有限節點組成一個具有層次關係的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
每個節點有零個或多個子節點；
沒有父節點的節點稱為根節點；
每一個非根節點有且只有一個父節點；
除了根節點外，每個子節點可以分為多個不相交的子樹；
樹形數據結構是一類重要的非線性數據結構。樹形數據結構在計算機領域中有著廣泛套用，如在編譯程式中，可用樹來表示源程式的語法結構。又如在資料庫系統中，樹形數據結構也是信息的重要組織形式之一。以及在檔案管理中，多級目錄結構就採用樹形數據結構。
相關術語
1、結點(Node)：表示樹中的數據元素，由數據項和數據元素之間的關係組成。在圖中，共有10個結點。
2、結點的度(Degree of Node)：結點所擁有的子樹的個數，在圖中，結點A的度為3。
3、樹的度(Degree of Tree)：樹中各結點度的最大值。在圖5.1中，樹的度為3。
4、葉子結點(Leaf Node)：度為0的結點，也叫終端結點。在圖5.1中，結點E、F、G、H、I、J都是葉子結點。
5、分支結點(Branch Node)：度不為0的結點，也叫非終端結點或內部結點。在圖5.1中，結點A、B、C、D是分支結點。
6、孩子(Child)：結點子樹的根。在圖中，結點B、C、D是結點A的孩子。
7、雙親(Parent)：結點的上層結點叫該結點的雙親。在圖中，結點B、C、D的雙親是結點A。
8、祖先(Ancestor)：從根到該結點所經分支上的所有結點。在圖中，結點E的祖先是A和B。
9、子孫(Descendant)：以某結點為根的子樹中的任一結點。在圖中，除A之外的所有結點都是A的子孫。
10、兄弟(Brother)：同一雙親的孩子。在圖5.1中，結點B、C、D互為兄弟。
11、結點的層次(Level of Node)：從根結點到樹中某結點所經路徑上的分支數稱為該結點的層次。根結點的層次規定為1，其餘結點的層次等於其雙親結點的層次加1。
2、結點的度(Degree of Node)：結點所擁有的子樹的個數，在圖中，結點A的度為3。
3、樹的度(Degree of Tree)：樹中各結點度的最大值。在圖5.1中，樹的度為3。
4、葉子結點(Leaf Node)：度為0的結點，也叫終端結點。在圖5.1中，結點E、F、G、H、I、J都是葉子結點。
5、分支結點(Branch Node)：度不為0的結點，也叫非終端結點或內部結點。在圖5.1中，結點A、B、C、D是分支結點。
6、孩子(Child)：結點子樹的根。在圖中，結點B、C、D是結點A的孩子。
7、雙親(Parent)：結點的上層結點叫該結點的雙親。在圖中，結點B、C、D的雙親是結點A。
8、祖先(Ancestor)：從根到該結點所經分支上的所有結點。在圖中，結點E的祖先是A和B。
9、子孫(Descendant)：以某結點為根的子樹中的任一結點。在圖中，除A之外的所有結點都是A的子孫。
10、兄弟(Brother)：同一雙親的孩子。在圖5.1中，結點B、C、D互為兄弟。
11、結點的層次(Level of Node)：從根結點到樹中某結點所經路徑上的分支數稱為該結點的層次。根結點的層次規定為1，其餘結點的層次等於其雙親結點的層次加1。
12、堂兄弟(Sibling)：同一層的雙親不同的結點。在圖中，G和H互為堂兄弟。
13、樹的深度(Depth of Tree)：樹中結點的最大層次數。在圖5.1中，樹的深度為3。
13、樹的深度(Depth of Tree)：樹中結點的最大層次數。在圖5.1中，樹的深度為3。
14、無序樹(Unordered Tree)：樹中任意一個結點的各孩子結點之間的次序構成無關緊要的樹。通常樹指無序樹。
15、有序樹(Ordered Tree)：樹中任意一個結點的各孩子結點有嚴格排列次序的樹。二叉樹是有序樹，因為二叉樹中每個孩子結點都確切定義為是該結點的左孩子結點還是右孩子結點。
16、森林(Forest)：m(m≥0)棵樹的集合。自然界中的樹和森林的概念差別很大，但在數據結構中樹和森林的概念差別很小。從定義可知，一棵樹有根結點和m個子樹構成，若把樹的根結點刪除，則樹變成了包含m棵樹的森林。當然，根據定義，一棵樹也可以稱為森林。
多級目錄結構
對於大型檔案系統，通常採用三級或三級以上的目錄結構，以提高對目錄的檢索速度和檔案系統的性能。多級目錄結構又稱為樹型目錄結構，主目錄在這裡被稱為根目錄，把數據檔案稱為樹葉，其它的目錄均作為樹的結點。下圖示出了多級目錄結構。圖中，用方框代表目錄檔案，圓圈代表數據檔案。在該樹型目錄結構中，主(根)目錄中有三個用戶的總目錄項 A、 B 和 C。 在 B 項所指出的 B 用戶的總目錄 B 中， 又包括三個分目錄 F、 E 和
D，其中每個分目錄中又包含多個檔案。如 B 目錄中的 F 分目錄中，包含 J 和 N 兩個檔案。為了提高檔案系統的靈活性，應允許在一個目錄檔案中的目錄項既是作為目錄檔案的 FCB，又是數據檔案的 FCB，這一信息可用目錄項中的一位來指示。例如，在圖 6-19 中，用戶 A的總目錄中，目錄項 A 是目錄檔案的 FCB，而目錄項 B 和 D 則是數據檔案的 FCB。
