樹的定義
樹是由n（n≥0）個結點組成的有限集合（記為T）。
如果n=0，它是一棵空樹，這是樹的特例。
如果n>0，這n個結點中存在（有僅存在）一個結點作為樹的根結點（root），其餘結點可分為m（m≥0）個互不相交的有限集T1、T2、…、Tm，其中每個子集本身又是一棵符合本定義的樹，稱為根結點的子樹。
樹是一種非線性資料結構，具有以下特點：
每一結點可以有零個或多個後繼結點，但有且只有一個前驅結點（根結點除外）。
資料結點按分支關係組織起來，清晰地反映了資料元素之間的層次關係。
抽象資料型別樹的描述
樹的邏輯結構表示方法
樹形表示法。這是樹的最基本的表示，使用一棵倒置的樹表示樹結構，非常直觀和形象。
文氏圖表示法。使用集合以及集合的包含關係描述樹結構。
凹入表示法。使用線段的伸縮關係描述樹結構。
括號表示法。將樹的根結點寫在括號的左邊，除根結點之外的其餘結點寫在括號中並用逗號分隔。
列表表示法。 "[根結點，子樹1，子樹2，…，子樹m]"。
樹的基本術語
結點的度。樹中每個結點具有的子樹數或者後繼結點數稱為該結點的度。
樹的度。樹中所有結點的度的最大值稱之為樹的度。
分支結點。度大於0的結點稱為分支結點或非終端結點。度為1的結點稱為單分支結點，度為2的結點稱為雙分支結點，依次類推。
葉子結點（或葉結點）。度為零的結點稱為葉子結點或終端結點。
孩子結點。一個結點的後繼稱之為該結點的孩子結點。
雙親結點（或父親結點）。一個結點稱為其後繼結點的雙親結點。
子孫結點。一個結點的子樹中除該結點外的所有結點稱之為該結點的子孫結點。
祖先結點。從樹根結點到達某個結點的路徑上透過的所有結點稱為該結點的祖先結點（不含該結點自身）。
兄弟結點。具有同一雙親的結點互相稱之為兄弟結點。
結點層次。樹具有一種層次結構，根結點為第一層，其孩子結點為第二層，如此類推得到每個結點的層次。
樹的高度。樹中結點的最大層次稱為樹的高度或深度。
森林。零棵或多棵互不相交的樹的集合稱為森林。
樹的性質
性質1： 樹中的結點數等於所有結點的度數加1。
性質2：度為m的樹中第i層上至多有mi-1個結點，這裡應有i≥1。
數學歸納法證明
當一棵m次樹的第i層有mi-1個結點（i≥1）時，稱該層是滿的，若一棵m次樹的所有葉子結點在同一層，並且每一層都是滿的，稱為滿m次樹。顯然，滿m次樹是所有相同高度的m次樹中結點總數最多的樹。
也可以說，對於n個結點，構造的m次樹為滿m次樹或者接近滿m次樹，此時樹的高度最小。
若一棵三次樹中度為3的結點為2個，度為2的結點為1個，度為1的結點為2個，則該三次樹中總的結點個數和度為0的結點個數分別是多少？
樹的基本運算
樹的運算主要分為三大類：
查詢滿足某種特定關係的結點，如尋找當前結點的雙親結點等；
遍歷樹中每個結點。
樹的遍歷運算是指按某種方式訪問樹中的每一個結點且每一個結點只被訪問一次。
有以下3種遍歷方法：
先根遍歷
若樹不空，則先訪問根結點，然後依次先根遍歷各棵子樹。
後根遍歷
若樹不空，則先依次後根遍歷各棵子樹，然後訪問根結點。
層次遍歷
若樹不空，則自上而下自左至右訪問樹中每個結點。
注意：先根和後根遍歷演算法都是遞迴的。
樹的儲存結構
雙親儲存結構
這種儲存結構是一種順序儲存結構，用一組連續空間儲存樹的所有結點，同時在每個結點中附設一個偽指標指示其雙親結點的位置。
雙親儲存結構
利用了每個結點（根結點除外）只有唯一雙親的性質。
這種儲存結構中，求某個結點的雙親結點十分容易，但求某個結點的孩子結點時需要遍歷整個結構。
例子：若一棵樹採用雙親儲存結構t儲存，設計一個演算法求指定索引是i的結點的層次。
孩子鏈儲存結構
個結點包含結點值和所有孩子結點指標，可按一個結點的度設計結點的孩子結點指標個數
孩子鏈儲存結構
優點是查詢某結點的孩子結點十分方便。
缺點是查詢某結點的雙親結點比較費時。
若一棵樹採用孩子鏈儲存結構t儲存，設計一個演算法求其高度
解：一棵樹的高度為根的所有子樹高度的最大值加1。求整棵樹的高度為"大問題"，求每棵子樹高度為"小問題"。設f(t)為求樹t的高度，對應的遞迴模型如下：
長子兄弟鏈儲存結構
長子兄弟鏈儲存結構是為每個結點設計三個域：一個數據元素域，一個指向該結點的長子的指標域，一個指向該結點的下一個兄弟結點指標域。
長子兄弟鏈儲存結構
優點是查詢某結點的孩子結點十分方便。
缺點是查詢某結點的雙親結點比較費時。
若一棵樹採用長子兄弟鏈儲存結構t儲存，設計一個演算法求其高度。
解：一棵樹的高度為根的所有子樹高度的最大值加1。求整棵樹的高度為"大問題"，求每棵子樹高度為"小問題"。設f(t)為求樹t的高度，對應的遞迴模型如下：
列表儲存結構
將樹的列表表示（樹的邏輯表示法之一）直接採用Python中的列表資料型別表示，稱為樹的列表儲存結構。
若一棵樹採用列表儲存結構t儲存，設計一個演算法求其高度。 解：一棵樹的高度為根的所有子樹高度的最大值加1。求整棵樹的高度為"大問題"，求每棵子樹高度為"小問題"。設f(t)為求樹t的高度，對應的遞迴模型如下：