1、樹：n個結點的有限集，n=0時為空樹，
1）特點：
（1）有且僅有一個特定的稱為根的結點，
（2）有若干個互不相交的子樹，這些子樹本身也是一棵樹，
（3）樹的根結點沒有前驅結點，除根結點外的所有結點有且只有一個前驅結點，
（4）樹中所有結點可以有零個或多個后繼結點，
2）通俗的定義：
（1）樹由節點和邊組成，
（2）每個結點只有一個父結點，但可以有多個子結點，
（3）但有一個結點例外，該結點沒有父結點，該結點稱為根結點，
3）樹分類：
（1）一般樹：任意一個結點的子結點的個數都不受限制，
（2）二叉樹：任意一個結點的子結點個數最多兩個，且子結點的位置不可更改，二叉樹的子樹有左右之分，
（3）森林：n個互不相交的樹的集合，
4）樹的基本性質
（1）樹中的結點數等于所有結點的度數+1，
（2）度為m的樹中第i層上至多有mi-1個結點，
（3）高度為h的m叉樹至多有(mh-1)/(m-1)個結點，
（4）具有n個結點的m叉樹的最小高度為logm(n(m-1)+1)，
2、專業術語：
1）深度：樹中結點的最大層次，即從根節點到最底層節點的層數，根結點是第一層，
2）葉子結點：沒有子結點的結點，
3）非終端結點：實際上就是非葉子結點，
4）度：子結點的個數，結點的度：結點擁有的子樹個數，樹的度：樹內各結點的度的最大值，
5）層次：從根開始定義起，根為第一層，根的孩子為第二層，
6）結點的高度：從葉子結點開始自底向上逐層累加，
7）路徑長度：從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路徑上的分支數目為長度，
8）樹的路徑長度：從樹根到每個結點的路徑長度之和，
9）樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，記作WPL，
3、樹的存盤：
1）雙親表示法：采用一組連續空間來存盤每個結點，同時在每個結點中增設一個偽指標，指示雙親結點在陣列中的位置，
（1）優點：求父節點方便，
（2）雙親表示法的存盤結構描述
typedef struct {
int data;
int parent;
}PTNode;
typedef struct {
PTNode nodes[Maxsize];
int n;
}PTree;
2）孩子表示法：將每個結點的孩子結點都用單鏈表鏈接起來形成一個線性結構，n個結點就有n個孩子鏈表（葉子結點的孩子鏈表為空表），
（1）優點：求子節點方便，
3）孩子兄弟表示法（二叉樹表示法）：每個結點包含三部分：結點值、指向結點第一個孩子結點的指標、指向結點下一個兄弟結點的指標，
（1）優點：求父節點和子節點都很方便，方便實作樹轉化為二叉樹；
（2）具體轉化方法：保證任意一個結點的左指標域指向它的第一個孩子、右指標域指向它的下一個兄弟，只要能滿足此條件，就可以把一個普通樹轉化為二叉樹，
（3）特點：一個普通樹轉化成的二叉樹一定沒有右子樹，因為根結點沒有兄弟，
（4）孩子兄弟表示法的存盤結構型別描述
typedef struct CSNode {
int data;
struct CSNode *firstchild, *nextsibling;
}CSNode,*CSTree;
計算以孩子兄弟表示法存盤的森林的葉子數
int leaves(CSTree t)
{
if (t == NULL)
{
return 0;
}
if (t->firstchild == NULL)
{
return 1 + leaves(t->nextsibling);
}
else
{
return leaves(t->firstchild) + leaves(t->nextsibling);
}
}
遞回求以孩子兄弟表示法表示的樹的深度
int height(CSTree t)
{
int l, r;
if (t == NULL)
{
return 0;
}
else
{
l = height(t->firstchild);
r = height(t->nextsibling);
if (l + 1 > r)
{
return l + 1;
}
else
{
return r;
}
}
}
4、森林的存盤：先把森林轉化為二叉樹，再存盤二叉樹，
5、樹操作：
1）樹的遍歷
（1）先根遍歷
先訪問根結點、再按從左到右的順序遍歷根結點的每棵子樹，
（2）后根遍歷
先按從左到右的順序遍歷根結點的每棵子樹、再訪問根結點，
2）森林的遍歷
（1）先序遍歷
先訪問森林中第一棵樹的根結點，再先序遍歷第一棵樹中根結點的子樹森林，再先序遍歷除去第一棵樹之后剩余的樹組成的森林，
（2）中序遍歷
先中序遍歷森林中第一棵樹中根結點的子樹森林，再訪問森林中第一棵樹的根結點，再中序遍歷除去第一棵樹之后剩余的樹組成的森林，
6、樹應用：
1）樹是資料庫中資料組織的一種重要形式，
作業系統子父行程的關系和面對物件語言中類的繼承關系本身就是一棵樹，
2）并查集的結構定義
int UFSets[Maxsize];
（1）初始化
void initial(int S[])
{
for (int i = 0; i < Maxsize; i++)
{
S[i] = -1;
}
}
（2）查找并回傳包含元素e的樹的根
int find(int S[], int e)
{
while (S[e]>=0)
{
e = S[e];
}
return e;
}
（3）求兩個不想交子集合的并集
void uniontree(int S[], int root1, int root2)
{
S[root2] = root1;
}
7、赫夫曼樹（最優樹）：一棵帶權路徑長度最短的樹，沒有度為1 的結點，一棵有n0個葉子結點的樹，共有2n0-1個結點，
1）構造程序
（1）將n個結點作為n棵含一個結點的二叉樹，
（2）從中選取兩棵根結點權值最小的樹作為新結點的左、右子樹，新結點的權值為左右子樹根結點的權值之和，
（3）重復，
2）特點
（1）每個初始結點最終成為葉結點，權值越小的結點到根結點的路徑長度越大，
（2）構造程序中共新建了n-1個結點，所以結點總數為2n-1個，
（3）不存在度為1 的結點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57181.html
標籤：其他
上一篇：資料結構（C語言版）---佇列