![樹[數據結構名詞]](/img/a/f46/nBnauM3X0IzNxkDO2MjM3IDN0UTMyITNykTO0EDMwAjMwUzLzIzLwczLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg "樹[數據結構名詞]")
定義
樹樹（tree）是包含n（n>=0）個結點的有窮集，其中：
（1）每個元素稱為結點（node）；
（2）有一個特定的結點被稱為根結點或樹根（root）。
（3）除根結點之外的其餘數據元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹也可以這樣定義：樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關係構成的。集合中的元素稱為樹的結點，所定義的關係稱為父子關係。父子關係在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。
我們可以形式地給出樹的遞歸定義如下:
單個結點是一棵樹，樹根就是該結點本身。
設T1,T2,..,Tk是樹，它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們還稱T1,T2,..,Tk為結點n的子樹。
空集合也是樹，稱為空樹。空樹中沒有結點。
相關術語
節點的度：一個節點含有的子樹的個數稱為該節點的度；
葉節點或終端節點：度為0的節點稱為葉節點；
非終端節點或分支節點：度不為0的節點；
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
兄弟節點：具有相同父節點的節點互稱為兄弟節點；
樹的度：一棵樹中，最大的節點的度稱為樹的度；
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次；
堂兄弟節點：雙親在同一層的節點互為堂兄弟；
節點的祖先：從根到該節點所經分支上的所有節點；
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。
森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
種類
無序樹：樹中任意節點的子結點之間沒有順序關係，這種樹稱為無序樹,也稱為自由樹;
有序樹：樹中任意節點的子結點之間有順序關係，這種樹稱為有序樹；
二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；
完全二叉樹
滿二叉樹
霍夫曼樹：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；
深度
定義一棵樹的根結點層次為1，其他節點的層次是其父結點層次加1。一棵樹中所有結點的層次的最大值稱為這棵樹的深度。
表示方法
圖像表達法
樹的表示方法有很多種，最常用的是圖像表示法。
一下是一個普通的樹（非二叉樹）：
![樹[數據結構名詞]](/img/4/078/wZwpmL4UjM4QjN0QTOxEDN0UTMyITNykTO0EDMwAjMwUzL0kzL1UzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
樹[數據結構名詞]符號表達法
用括弧先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如前文樹形表示法可以表示為：（1（2（5（9，10）），3（6，7），4（8）））
遍歷表達法
![樹[數據結構名詞]](/img/2/310/wZwpmLwYDN3QzN0QTMyEDN0UTMyITNykTO0EDMwAjMwUzL0EzLwQzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
樹[數據結構名詞]遍歷表達法有3種方法：先序遍歷、中序遍歷、後序遍歷
例如右圖：
其先序遍歷為ABDECF
其中序遍歷為DBEAFC
其後序遍歷為DEBFCA
具體請參照參考資料
其他
關於二叉樹的其他知識請參照參考資料。
父節點表示法
存儲結構
基本操作
設已有鏈佇列類型LinkQueue的定義及基本操作（參見佇列）。
構造空樹
清空或銷毀一個樹也是同樣的操作
構造樹
判斷樹是否為空
獲取樹的深度
獲取第i個節點的值
改變節點的值
獲取節點的父節點
獲取節點的最左孩子節點
獲取節點的右兄弟節點
輸出樹
向樹中插入另一棵樹
刪除子樹
層序遍歷樹
孩子鍊表表示法
存儲結構
