樹是一種非線性結構，它是由**n（n>=0）**個有限結點組成一個具有層次關系的集合。具有層次關系則說明它的結構不再是線性表那樣一對一，而是一對多的關系；隨著層數的增加，每一層的元素個數也在不斷變化（由上一層和該層的對應關系決定）。
關于樹的名稱的由來，是因為它的結構類型很像現實中的樹倒過來，故稱作——樹。
根據樹的名稱，也對其所包含的元素進行了命名和定義。
樹的基本術語
1.結點：包含一個數據元素及若干指向其子樹的分支；
2.結點的度：一個結點擁有的子樹的數目；
3.葉子或終端結點：度為0的結點；
4.非終端結點或分支結點：度不為0的結點；
5.樹的度：樹內各結點的度的最大值；（需要注意，樹的度和結點的度的定義是有略微差異的）
除此之外，還使用人類親緣關系進行了一系列描述：（注：下圖的關系與節點名稱無關，僅代表樹的結構）
6.孩子結點或子結點：結點的子樹的根稱為該結點的孩子結點或子結點；
7.雙親結點或父結點：若一個結點含有子結點，則這個結點稱為其子結點的雙親結點或父結點；
8.兄弟結點：同一個雙親的孩子之間互稱兄弟；
9.祖先結點：從根到該結點所經分支上的所有結點；
10.子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫；
11.結點的層次：從根開始定義起，根為第一層，根的孩子為第二層。若某結點在第L層．則其子樹的根就在第L+1層；
12.堂兄弟結點：其雙親在同一層的結點互為堂兄弟；
13.樹的深度或高度：樹中結點的最大層次；
14.森林：由m(m>=0)棵互不相交的樹的集合稱為森林;
15.有序樹和無序樹：樹中結點的各子樹從左到右是有次序的，不能互換，稱該樹為有序樹，否則稱為無序樹；
16.路徑和路徑長度：路徑是由樹中的兩個結點之間的結點序列構成的。而路徑長度是路徑上所經過的邊的個數
樹的基本特征
針對樹，我們有很多可以說的點。這里我們主要從其結構特征來進行總結。
-
任何一棵樹都是由根和子樹構成的——子樹又是一棵樹——樹是遞歸定義的
-
樹的根結點沒有前驅；除根結點外的所有結點有且只有一個前驅（也就是一個父節點）。
-
樹中所有結點有零個或多個后繼。
-
子樹是不相交的。
-
當不再有子樹的時候就說明該樹已經到了尾結點。
樹的公式
事實上，基于樹的數據結構，可以衍生出很多數學公式來對其進行計算，但是這里只介紹基本的兩個（其他重要的公式會在二叉樹中進行介紹）
節點數量
- 對于一棵有 n 個節點的樹，節點數量公式為：n = I + L 其中，I 是內節點數量，L 是葉節點數量。
邊數
- 一棵有 n 個節點的樹有 n?1 條邊。
樹的構建
樹的存儲結構主要有以下幾種方法，每種方法都有其優缺點和適用場景：
1. 父節點表示法（Parent Representation）
每個節點記錄其父節點的編號或指針。這種方法使用一個數組，其中每個元素表示節點，其值是該節點的父節點的索引。
-
結構：
parent[i] 表示第 i 個節點的父節點 -
示例：
節點: 0 1 2 3 4 5 父節點: -1 0 0 1 1 2 （-1 表示根節點） -
優點：簡單，適合快速查找父節點。
-
缺點：查找子節點較慢，需要遍歷整個數組。
2. 孩子表示法（Child Representation）
每個節點記錄其所有子節點。這種方法使用一個鏈表或數組，其中每個節點包含一個指向其子節點列表的指針。
-
結構：
children[i] 表示第 i 個節點的子節點列表 -
示例：
節點: 0 1 2 3 4 5 子節點: [1,2] [3,4] [5] [] [] [] -
優點：適合快速查找子節點。
-
缺點：查找父節點較慢，需要記錄父節點指針或進行額外處理。
以上兩種方法的缺點和優點是互補的。那么是否有更為方便的方法呢？
3. 孩子兄弟表示法（Left-Child Right-Sibling Representation）
當我們需要定義很多孩子的時候，我們可以使用左孩子右兄弟的定義法
也就是說根節點只指向它的第一個孩子結點，而其他的孩子節點就交給第一個孩子節點去指向
將樹轉換為二叉樹，每個節點記錄其最左子節點和右兄弟節點。這種方法使用兩個指針，一個指向最左子節點，另一個指向右兄弟。
-
結構：
節點: node 左孩子: leftChild 右兄弟: rightSibling -
示例：
節點: 0/ \1 2/ \3 4 轉換為: 節點: 0/ \1 2/3\4 -
優點：能將任意樹轉換為二叉樹，利用二叉樹的遍歷和處理方法。
-
缺點：需要兩個指針，內存開銷較大。
4. 鄰接表表示法（Adjacency List Representation）
通常用于存儲圖結構，但也可以用于樹。每個節點記錄其相鄰節點（即子節點和父節點）。
-
結構：
adjList[i] 表示第 i 個節點的相鄰節點列表 -
示例：
節點: 0 1 2 3 4 5 相鄰節點: [1,2] [0,3,4] [0,5] [1] [1] [2] -
優點：適合處理樹和圖的遍歷和搜索。
-
缺點：需要額外處理以區分子節點和父節點。
5. 鄰接矩陣表示法（Adjacency Matrix Representation）
使用一個二維數組表示節點之間的連接關系。通常用于稠密圖，但在某些情況下也可用于樹。
-
結構：
adjMatrix[i][j] 表示節點 i 和節點 j 之間是否有邊（0 或 1） -
示例：
節點: 0 1 2 3 4 5 鄰接矩陣: [0, 1, 1, 0, 0, 0] [1, 0, 0, 1, 1, 0] [1, 0, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0] [0, 1, 0, 0, 0, 0] [0, 0, 1, 0, 0, 0] -
優點：簡單，適合快速查找任意兩個節點之間是否有邊。
-
缺點：存儲空間開銷大，不適合稀疏樹。
這些存儲結構各有特點，選擇哪種方法主要取決于具體應用需求，例如查找子節點還是父節點更頻繁，內存開銷是否是主要考慮因素等。
樹的初始化和一些基本操作
#include <stdio.h>
#include <stdlib.h>// 定義樹節點結構
typedef struct TreeNode {int data;struct TreeNode* child1;struct TreeNode* child2;struct TreeNode* child3;struct TreeNode* child4;...
} TreeNode;//樹的初始化
TreeNode* createNode(int data)
{TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if(!newNode){printf("failed!\n");return NULL;}newNode->data = data;newNode->child1 = NULL;newNode->child2 = NULL;...return newNode;
}//插入、查找、遍歷...
TreeNode* insertTree(TreeNode* parent,int data);
TreeNode* findTree(TreeNode* parent,int data);
TreeNode* inorderTraversal(TreeNode* parent);
...
總結
單純的樹實際上用處不大（子節點過多）。但是對于文件系統、目錄以及某些分層過多的系統，使用的就是樹。
通常在優化的數據結構中，使用更多的是叫做二叉樹的數據結構
這是基于樹的數據結構，一個根節點只有兩個孩子結點，在下一節我們將會對二叉樹進行剖析，敬請期待。
 FPGA最小系統)
