一。樹型結構
結點之間有分支，具有層次關系
1.樹的定義
樹(Tree)是n (n≥0)個結點的有限集。
若n=0,稱為空樹;
若n> 0,則它滿足如下兩個條件:
(1) 有且僅有一個特定的稱為根(Root)的結點;
(2)其餘結點可分為m (m≥0)個互不相交的有限集T1, T2, T3, ...Tm,其中每一個集合本身又是一棵樹，并稱為根的子樹(SubTree)。
其他表示：
2.樹的基本術語
根結點:非空樹中無前驅結點的結點
結點的度:結點擁有的子樹數。
樹的度:樹内各結點的度的最大值。
終端結點/葉子:度=0的結點
分支結點/非終端結點/：度≠0的結點
根結點以外的分支結點稱為内部結點
結點的祖先:從根到該結點所經分支上的所有結點。
結點的子孫:以某結點為根的子樹中的任一-結點
樹的深度:樹中結點的最大層次。
有序樹:樹中結點的各子樹從左至右有次序(最左邊的為第一個孩子)。
森林：是m (m>=0)棵互不相交的樹的集合。
把根結點删除樹就變成了森林。
一棵樹可以看成是一 個特殊的森林。
給森林中的各子樹加上一個雙親結點，森林就變成了樹。
二。二叉樹
為何要重點研究每結點最多隻有兩個"叉” 的樹?
二叉樹的結構最簡單，規律性最強;
可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。
1.二叉樹的定義
二叉樹是n (n20)個結點的有限集，它或者是空集(n= 0),或者由一個根結點及兩棵互不相交的分别稱作這個根的左子樹和右子樹的二叉樹組成。
【特點】：
1、每個結點最多有倆孩子(二叉樹中不存在度大于2的結點)。
2、子樹有左右之分，其次序不能颠倒。
3、二叉樹可以是空集合, 根可以有空的左子樹或空的右子樹。
【思考】
2.案例引入
案例1 ： 資料壓縮問題 - 有字首非等長編碼
案例2 : 利用二叉樹求解表達式的值
若表達式為“第一操作數運算符第二操作數”的形式，則相應的叉樹中以左子樹表示第操作數,右子樹表示第二操作數，根結點的資料域存放運算符(若為一進制運算符，則左子樹為空) ,其中，操作數本身又為表達式。
如：
三。樹和二叉樹的抽象資料類型定義
1.二叉樹的抽象資料類型定義：
ADT BinaryTree{
資料對象D:
D是具有相同特性的資料元素的集合。
資料關系R:
若D=中，則R=中;
若D≠中，則R= {H}; H是如下二進制關系:
①root 唯一//關于根的說明
②D:nDk=中//關于子樹不相交的說明
③//關于資料元素的說明
④//關于左子樹和右子樹的說明
基本操作P:
CreateBiTree(&T,definition)初始條件; definition給出二叉樹T的定義。操作結果:按definition構造二叉樹T。
PreOrderTraverse(T)初始條件: 二叉樹T存在。操作結果:先序周遊T，對每個結點通路一-次。
InOrderTraverse(T)初始條件: 二叉樹T存在。操作結果:中序周遊T，對每個結點通路一次。
PostOrderTraverse(T)初始條件:二叉樹T存在。操作結果:後序周遊T，對每個結點通路一次。
}ADT BinaryTree
性質1:在二叉樹的第i層上 至多有2i-1個結點(i≥1)。
性質2:深度為k的二叉樹至多有2k- 1個結點(k≥1)。
性質3:對任何一棵二叉樹T,如果其葉子數為no，度為2的結點數為n2，則no= n2+1。
2.滿二叉樹 - 一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。
【特點】:
1.每一層上的結點數都是最大結點數(即每層都滿)
2.葉子節點全部在最底層
3.完全二叉樹
深度為k的具有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編号為1~ n的結點一一對應時， 稱之為完全二叉樹。
注:在滿二叉樹中，從最後一個結點開始，連續去掉任意個結點，即是一棵完全二叉樹一定是連續的去掉! ! !
1.葉子隻可能分布在層次最大的兩層上。
2.對任一結點，如果其右子樹的最大層次為i,則其左子樹的最大層次必為i或i+ 1。
性質5：
(1) 如果i= 1,則結點i是二叉樹的根，無雙親;如果i> 1,則其雙親是結點Li/ 2]。
(2)如果2i> n,則結點i為葉子結點，無左孩子;否則，其左孩子是結點2i。
(3)如果2i+ 1 > n,則結點i無右孩子;否則，其右孩子是結點2i + 1。（i為雙親結點的編号）
四。二叉樹的存儲結構
1.二叉樹的順序存儲
按滿二叉樹的結點層次編号，依次存放二叉樹中的資料元素。
2.二叉連結清單存儲結構
struct TElemType
{
int a;//樹的元素的任意資料類型
};
typedef struct BiNode
{
struct TElemType data;
struct BiNode * lchild;
struct BiNode * rchild;
}BiNode,*BiTree; 三叉連結清單，還有一個指針域指向雙親
typedef struct TriTNode{
TelemType data;
struct TriTNode *Ichild, *parent, *rchild;
}TriTNode,*TriTree;