*号表示重點
一、樹和二叉樹
1、樹
樹是n(n≥0)個結點的有限集合，n=0時稱為空樹，在任一非空樹中
● 有且僅有一個稱為根的結點。
● 其餘的結點可分為m(m≥0)個互不相交的子集T1，T2…，Tm， 其中每個子集本身又是一棵樹，并稱其為根結點的子樹。
1.2、樹的基本概念
● 雙親和孩子（父節點和子節點）
● 兄弟：具有相同雙親的結點互為兄弟。
● 結點的度：一個結點的子樹的個數記為該結點的度。
● 樹的度：樹中各結點的度的最大值
● 葉子結點：也稱為終端結點，指度為零的結點。
● 内部結點：度不為零的結點稱為分支結點或非終端結點。除 根結點之外，分支結點也稱為内部結點。
● 節點的層次：根為第一層，根的孩子為第二層，以此類推。
● 樹的高度：一棵樹的最大層數記為樹的的高度（或深度）。
● 有序（無序）樹：若将樹中的結點的各子樹看成是從左到右具有次序的，即不能交換，則稱改子樹為有序樹，否則為無序樹。
● 森林：是m(m>=0)棵互不相交的樹的集合。
1.3、樹的存儲結構
● 标準存儲結構
√結點的資料
√指向子結點的指針
● 帶逆存儲結構
√結點的資料
√指向子結點的指針
√指向其父結點的指針
*1.4、樹的周遊(注：樹沒有中序周遊也就是中根周遊，隻有二叉樹有！)
周遊是指對樹中所有結點資訊的通路，即依次對樹中每個節點通路一次且僅通路一次。例：
● 前序周遊（先根周遊）A B E F I J C D G H
● 後序周遊（後根周遊）E I J F B C G H D A
● 層次周遊（按層依次周遊）A B C D E F G H I J
*2、二叉樹
二叉樹（BinaryTree）是n(n>0)個結點的有限集合，它或者是空樹（n=0）,或者是由一個根結點及兩顆互不相交的、分别稱為左子樹和右子樹的二叉樹所組成。
二叉樹與樹的差別：
● 二叉樹的結點的最大度為2，而樹中不限制結點的度。
● 二叉樹的結點的子樹要區分左子樹和右子樹
*2.1、二叉樹的性質
(1)二叉樹第i層上的結點數目最多為2的i-1次幂(i≥1)。
(2)深度為k的二叉樹至多有2的k次幂-1個結點(k≥1)。
(3)在任意一棵二叉樹中，若終端結點(葉子節點)數為n0，度為2的結點 數為n2，則n0=n2+1。
(4)具有n個結點的完全二叉樹的深度為⌊log2n」+1。//⌊ 」取下限整數。
(5)對一棵有n個結點的完全二叉樹的結點按層次自左至右進行 編号，則對任一結點i有：
●若i=1，則結點 i是二叉樹的根，無雙親，若i>1，則其雙 親為⌊ i/2 」。
● 若2i>n，則結點i無左孩子，否則其左孩子為 2i。
● 若2i+1>n，則結點i無右孩子，否則其右孩子為 2i+1。
若深度為k的二叉樹有2k-1個結點，則稱其為滿二叉樹。 深度為k、有n個結點的二叉樹，當且僅當其每一個結點都與 深度為k的滿二叉樹編号從1至n的結點一一對應時，稱之為完全二叉樹（簡而言之就是完全二叉樹中不能在有右子樹的前提下沒有左子樹）。下圖左為滿二叉樹，圖右為完全二叉樹。
2.2、二叉樹的存儲結構 （僅了解）
(1)順序存儲結構
對完全二叉樹既簡單又節省空間，而對于一般二叉樹則不 适用。
(2)鍊式存儲結構
由于二叉樹中結點包含有資料元素、左子樹根、右子樹根 及雙親等資訊，是以可以用三叉連結清單或二叉鍊襲來存儲二叉 樹。連結清單的頭指針指向二叉樹的根結點。
*2.3、二叉樹的周遊（必須會）
● 前序周遊 4 2 1 3 5 6
● 中序周遊 1 2 3 4 5 6
● 後序周遊 1 3 2 6 5 4
關于二叉樹周遊的要求：通過二叉樹的兩種序列，可以畫出這棵樹，并畫出另一序列。例題：
已知二叉樹前序周遊是ABHFDECKG，中序周遊序列是 HBDFAEKCG，它的後序周遊序列是( B ) 。
A、BHFDECKGA B、HDFBKGCEA
C、HFDBKCGEA D、ABEHFCDKG
解：
3、二叉排序樹
又稱為二叉查找樹，定義：或者是一棵空樹，或者是具有下列性質的二叉樹:
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根 結點的值；
（2）若右子樹不空，則右子樹上所有結點 的值均大于或等于它的根結點的值（3）左、右子樹也分别為二叉排序樹；
二叉排序樹：
4、平衡二叉樹
又被稱為AVL樹，具有以下性質：它是一棵空樹或它的左右 兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是 一棵平衡二叉樹。
平衡二叉樹:
錯誤的平衡二叉樹:
5、線索樹
n個結點的二叉連結清單中含有n+1 (2n-(n-1)=n+1)個空指針域。利 用二叉連結清單中的空指針域，存放指向結點在某種周遊次序下 的前趨和後繼結點的指針（這種附加的指針稱為"線索"）。
6、、最優二叉樹
給定n個權值作為n的葉子結點，構造一棵二叉樹，若帶權路 徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈 夫曼樹(Huffman tree)。哈夫曼樹是帶權路徑長度最短的樹， 權值較大的結點離根較近。