1. 與樹有關(guān)的概念
1) 結(jié)點的度：結(jié)點擁有的子樹數(shù)。
2) 樹的度：樹中所有結(jié)點的度的最大值。
3) 結(jié)點的層數(shù)：
4) 樹的深度：樹中結(jié)點的最大層數(shù)或者稱為樹的高度或者深度。
5) 葉子結(jié)點：度為0的點或者終端節(jié)點。
6) 分支結(jié)點：度大于0的結(jié)點。
7) 森林：m棵互不相交的樹的集合為森林
8) 樹不允許為空。但是二叉樹允許為空，二叉樹不是樹，并且二叉樹是有序樹，左孩子和右孩子是不一樣的。
2. 二叉樹概念：有限個元素的集合，該集合或者為空、或者有一個稱為根的元素以及兩兩不相交的、分別稱為左子樹和右子樹的組成。
1) 二叉樹的性質(zhì)如下：
① 二叉樹的第i層，共有2^（i-1）個結(jié)點。
② 深度為k二叉樹最多有2^k-1個結(jié)點。
③ 二叉樹中，終端節(jié)點的數(shù)目為n0；度為1的結(jié)點數(shù)目為n1，度為2的結(jié)點為n2；則n0 = n2+1；
據(jù)此，可以引出一下結(jié)論,對于n個結(jié)點的完全二叉樹：
a>,若n為奇數(shù)，則樹中只有度為2和度為0的結(jié)點。其中度為2的結(jié)點數(shù)為 (n-1)/2；度為0的結(jié)點數(shù)為(n-1)/2+1；
b>,若n為偶數(shù)，則樹中除了度為2和度為0的結(jié)點結(jié)點外，還有度為1的結(jié)點1個。
④ 如果有一棵n個結(jié)點的完全二叉樹，自上自下，同一層自左到右連續(xù)給結(jié)點編號，則有如下關(guān)系：
a>,若i=1，則結(jié)點為i為根結(jié)點，若i>1，則結(jié)點i的父節(jié)點為『i/2』；
b>,若2i<n,則結(jié)點i的左孩子結(jié)點為2i；
c>,若2i+1<n;則結(jié)點i的右孩子結(jié)點為2i+1；
d>,若結(jié)點i為奇數(shù)，則左子樹結(jié)點為i-1；
e>,若結(jié)點i為偶數(shù)，則右子樹結(jié)點為i+1；
f>,結(jié)點i所在的層次為log2i+1；
由此可以引入如下結(jié)論：對于完全二叉樹編號為i的結(jié)點有：
1>,若i<=n/2，則編號為i的結(jié)點為分支結(jié)點，否則為葉結(jié)點
2>,若n為奇數(shù)，則每個分支結(jié)點都有左子樹和右子樹；若n為偶數(shù)，則編號最大的分支結(jié)點只有左子樹。
⑤ 具有n個結(jié)點的完全二叉樹的深度為log2（n+1）（向上取整）
2) 二叉樹的存儲結(jié)構(gòu)
① 二叉樹的順序存儲結(jié)構(gòu)一般適用于完全二叉樹。
② 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，有二叉鏈表和三叉鏈表。
3) 二叉樹的遍歷
① 中序遞歸遍歷
② 先序遞歸遍歷
③ 后序遞歸遍歷
④ 中序非遞歸
⑤ 后序非遞歸
⑥ 先序非遞歸
⑦ 層次遍歷
4) 線索二叉樹
3. 樹與森林
1) 樹的存儲結(jié)構(gòu)
2) 森林，樹與二叉樹的轉(zhuǎn)換
3) 森林與樹的遍歷
4. 樹的應(yīng)用
1) 二叉排序樹
2) 平衡二叉樹
3) 哈夫曼樹
4) 堆