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