文章目錄

• 一. 樹的概念
• 二. 樹的存儲結構
• • • (一). 雙親表示法
    • (二). 孩子表示法
    • • • 1. 定長結點鏈表存儲結構
        • 2. 孩子鏈表存儲結構
    • (三). 孩子兄弟表示法

一. 樹的概念

樹（Tree）是n（n>=0）個結點的有限集。

當 n = 0 時，稱為空樹。

在任意一顆非空樹中：

• 有且僅有一個特定的稱為 根（Root） 的結點；
  如上圖，A為根
• 當 n > 1 時，其余結點可分為m（m > 0）個互不相交的有限集T1，T2，T3…Tm，其中每一個集合本身又是一顆樹，并且稱為根的子樹。
  B,C,D稱為A的子樹

樹的結點包含一個數據元素及若干指向其子樹的分支。

結點擁有的子樹個數稱為結點的度。
A的子樹個數有3個，即度為3。B的子樹個數為0，即度為0。

度為0的結點稱為葉子或終端結點。
B,H,F,G的度為0，即B,H,F,G稱為葉子結點。

度不為0的結點稱為非終端結點或分支結點。
如A,C,D,E。

樹的度是樹內各結點的度的最大值。
A的度為3，在所有結點中式最大的，即樹的度就是3。

結點的子樹的根稱為該結點的孩子，相應的，該結點稱為孩子的雙親。
結點H是結點E的孩子結點，反之，E是H的雙親結點。

同一個雙親的孩子之間互稱為兄弟。
E和F互為兄弟。

結點的祖先是從根到該結點所經分支上的所有結點，反之，以某結點的根的子樹中的任一結點都稱為該結點的子孫。
H的祖先是A,C,E。 C的子孫是E,F,H。

結點的層次從根開始定義起，根為第一層，根的孩子為第二層。

若某結點在第 l 層，則其子樹的根就在第 l + 1 層。其雙親在同一層的結點互稱為堂兄弟。

樹中結點的最大層次稱為樹的深度或高度。
圖中樹的深度為3。

如果將樹中結點的各子樹看成從左至右是有序次的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。

二. 樹的存儲結構

(一). 雙親表示法

這種存儲結構是一種順序存儲結構，用一組連續空間存儲樹的所有結點，同時在每個結點中附設一個下標（偽指針）指示其雙親結點的位置。

結點結構表示為：

data值就是結點的數據值，parent表示這個數據結點的雙親結點在這個空間中存放的位置。

如

可表示為：

因為parent指向雙親的位置，并沒有指向孩子結點的指針，因此使用雙親表示法找出雙親結點的時間復雜度為O（1），找出孩子結點必須要全部遍歷一遍，時間復雜度為O（n）。

雙親存儲結構的類型聲明：

#define MAX_TREE_SIZE 100struct PTNode{TElem Type data;int parent; //雙親位置域 };struct PTree{PTNode nodes[MAX_TREE_SIZE];int r,n; //根的位置，結點數 };

(二). 孩子表示法

由于樹中每個結點可能有多棵子樹，則可用多重鏈表，即每個結點有多個指針域，其中每個指針指向一棵子樹的根節點，此時鏈表中的結點可以有如下兩種結點格式：

1. 定長結點鏈表存儲結構

孩子鏈表存儲結構可按樹的度設計結點的孩子結點指針域個數

2. 孩子鏈表存儲結構

把每個結點的孩子結點排列起來，看成是一個線性表，且以單鏈表作存儲結構，則n個結點有n個孩子鏈表（葉子的孩子鏈表為空表）。
而n個頭指針又組成一個線性表，為了便于查找，可采用順序存儲結構。如下圖：

為此，需要設計兩種結點結構：

樹的孩子鏈表孩子兄弟表示：

typedef struct CTNode{ //孩子結點 struct CTNode *next;int child; };typedef struct{TElem data;ChildPtr firstchild; //孩子鏈表頭指針 }CTBox; typedef struct {CTBox nodes[MAX_TREE_SIZE];int r,n; //根的位置，結點數 }CTree;

(三). 孩子兄弟表示法

又稱二叉樹表示法，或二叉鏈表表示法。

以二叉鏈表作樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點，分別命名為 firstchild域和 nextchild域。

樹的二叉鏈表（孩子—兄弟）存儲表示：

typedef struct CSNode{TElemType data;CSNode *firstchild, *nextchild; }CSNode *CSTree;

總結

以上是生活随笔為你收集整理的树的概念及存储结构（双亲表示法，孩子表示法，孩子兄弟表示法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。