1. 與樹有關的概念

1) 結點的度：結點擁有的子樹數。

2) 樹的度：樹中所有結點的度的最大值。

3) 結點的層數：

4) 樹的深度：樹中結點的最大層數或者稱為樹的高度或者深度。

5) 葉子結點：度為0的點或者終端節(jié)點。

6) 分支結點：度大于0的結點。

7) 森林：m棵互不相交的樹的集合為森林

8) 樹不允許為空。但是二叉樹允許為空，二叉樹不是樹，并且二叉樹是有序樹，左孩子和右孩子是不一樣的。

2. 二叉樹概念：有限個元素的集合，該集合或者為空、或者有一個稱為根的元素以及兩兩不相交的、分別稱為左子樹和右子樹的組成。

1) 二叉樹的性質如下：

①　二叉樹的第i層，共有2^（i-1）個結點。

②　深度為k二叉樹最多有2^k-1個結點。

③　二叉樹中，終端節(jié)點的數目為n0；度為1的結點數目為n1，度為2的結點為n2；則n0 = n2+1；

    據此，可以引出一下結論,對于n個結點的完全二叉樹：

a>,若n為奇數，則樹中只有度為2和度為0的結點。其中度為2的結點數為  (n-1)/2；度為0的結點數為(n-1)/2+1；

b>,若n為偶數，則樹中除了度為2和度為0的結點結點外，還有度為1的結點1個。

④　如果有一棵n個結點的完全二叉樹，自上自下，同一層自左到右連續(xù)給結點編號，則有如下關系：

a>,若i=1，則結點為i為根結點，若i>1，則結點i的父節(jié)點為『i/2』；

b>,若2i<n,則結點i的左孩子結點為2i；

c>,若2i+1<n;則結點i的右孩子結點為2i+1；

d>,若結點i為奇數，則左子樹結點為i-1；

e>,若結點i為偶數，則右子樹結點為i+1；

f>,結點i所在的層次為log2i+1；

由此可以引入如下結論：對于完全二叉樹編號為i的結點有：

1>,若i<=n/2，則編號為i的結點為分支結點，否則為葉結點

2>,若n為奇數，則每個分支結點都有左子樹和右子樹；若n為偶數，則編號最大的分支結點只有左子樹。

⑤　 具有n個結點的完全二叉樹的深度為log2（n+1）（向上取整）

2) 二叉樹的存儲結構

①　二叉樹的順序存儲結構一般適用于完全二叉樹。

②　二叉樹的鏈式存儲結構，有二叉鏈表和三叉鏈表。

3) 二叉樹的遍歷 

①　中序遞歸遍歷

②　先序遞歸遍歷

③　后序遞歸遍歷

④　中序非遞歸

⑤　后序非遞歸

⑥　先序非遞歸

⑦　層次遍歷

     4) 線索二叉樹

3. 樹與森林

1) 樹的存儲結構

2) 森林，樹與二叉樹的轉換

3) 森林與樹的遍歷

4. 樹的應用

1) 二叉排序樹

2) 平衡二叉樹

3) 哈夫曼樹

4) 堆