什么是”樹“
樹（tree）是包含n（n>0）個結點的有窮集，其中：
（1）每個元素稱為結點（node）
（2）有一個特定的結點被稱為根結點或樹根（root）
（3）除根結點之外的其余數據元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹也可以這樣定義：樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關系構成的。集合中的元素稱為樹的結點，所定義的關系稱為父子關系。父子關系在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。
我們可以形式地給出樹的遞歸定義如下:
單個結點是一棵樹，樹根就是該結點本身。
設T1,T2,..,Tk是樹，它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們還稱T1,T2,..,Tk為結點n的子樹。
空集合也是樹，稱為空樹?？諛渲袥]有結點。
相關概念：
- 節(jié)點的度：一個節(jié)點含有的子樹的個數成為該節(jié)點的度
- 葉節(jié)點或終端節(jié)點：度為0的節(jié)點成為葉節(jié)點
- 非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點
- 雙親節(jié)點或者父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點成為其子節(jié)點的父節(jié)點
- 孩子節(jié)點或者子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點
- 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點
- 節(jié)點的層次：從根節(jié)點定義起，根節(jié)點為第一層，根節(jié)點的子節(jié)點為第二層，以此類推
- 樹的高度或深度：樹中最大的層次
- 堂兄弟節(jié)點：雙親在同一層的節(jié)點互稱堂兄弟
- 節(jié)點的祖先：從根節(jié)點到該節(jié)點所經分支上的所有節(jié)點
- 子孫：以某節(jié)點為根的子樹中任一節(jié)點都成為該節(jié)點的子孫
樹的種類：
- 無序樹：樹中任意節(jié)點的子結點之間沒有順序關系，這種樹稱為無序樹,也稱為自由樹
- 有序樹：樹中任意節(jié)點的子結點之間有順序關系，這種樹稱為有序樹
- 二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹
- 滿二叉樹:除最后一層無任何子節(jié)點外，每一層上的所有結點都有兩個子結點二叉樹。
- 完全二叉樹: 若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續(xù)集中在最左邊，這就是完全二叉樹。完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有N個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹.若一棵二叉樹至多只有最下面的兩層上的結點的度數可以小于2，并且最下層上的結點都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹。
- 霍夫曼樹：帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹
樹的遍歷：
- 先序遍歷：從根節(jié)點開始，先遍歷左子樹，然后遍歷右子樹，在遍歷子樹的時候，依舊按照從根節(jié)點遍歷左右子樹的原則遍歷(A,B,D,E,C,F)
- 中序遍歷：從最左的葉子節(jié)點開始，先遍歷左節(jié)點，然后根節(jié)點，再右節(jié)點(D,B,E,A,F,C)
- 后序遍歷：從最左的葉子節(jié)點開始，先遍歷左節(jié)點，然后右節(jié)點，再跟節(jié)點(D,E,B,F,C,A)
二叉樹:
對樹而言，需要重點掌握二叉樹。二叉樹是一種特殊的順序樹，它規(guī)定有左右兩個孩子，即左右孩子順序不能替換，所以二叉樹是一種有序樹。二叉樹的結點數為大于0小于等于2。
二叉樹性質：
對樹而言，需要重點掌握二叉樹。二叉樹是一種特殊的順序樹，它規(guī)定有左右兩個孩子，即左右孩子順序不能替換，所以二叉樹是一種有序樹。二叉樹的結點數為大于0小于等于2。對于二叉樹，需要掌握以下性質：
性質1:
在二叉樹的第i層上至多有
i=1，結點數為1
i=2，結點數為2
i=3，結點數為4
i=4，結點數為8
i=n, 結點數為:
性質2:
深度為K的二叉樹至多有
換言之，如果二叉樹的深度確定，則其最大的結點數也是確定的。
證明（可以利用性質1）
深度為K的二叉樹的結點個數=二叉樹中每一層結點個數的總和。即為：
（等比公式）
性質3:
二叉樹中，終端結點
（注：度表示分支的個數，也指分支因子，終端結點也指葉子結點）
分析：二叉樹中結點的度可以為0,1,2，也就是說需要證明結點的度為0與度為2的結點之間的關系是不變的。
證明：設二叉樹中度為i的結點數為
則整棵二叉樹的結點總數為：
除根結點外，每一個結點都是另一個結點的孩子，所以孩子數為(2):n-1
度為i(I = 0,1,2)的結點，有i個孩子，
孩子數 =
因為：(3) = (2),所以，
(4) – (1) ,得:
證畢.
性質1、2、3是二叉樹的通用特性。
在介紹其它性質之前，先了解另一種特殊的二叉樹，即滿二叉樹，其定義如下：
滿二叉樹是指深度為K，且有)2^{k}-1)個結點的二叉樹。
特點：(1) 每層上結點數都達到最大
(2) 度為1的結點個數=0,即不存在分支數為1的結點
如下即為一棵滿二叉樹：(注意其順序：結點層序編號方法，從根結點起從上至下逐層從左至右對二叉樹的結點進行連續(xù)編號)
1
/ \
2 3
/ \ / \
4 5 6 7
完全二叉樹：深度為k,結點數為n的二叉樹，當且僅當每個結點的編號都與相同深度的滿二叉樹中從1到n的結點一一對應時，稱為完全二叉樹。
1
/ \
2 3
/ \
4 5 （注意編號順序，與滿二叉樹一一對應）
(向下取整)+ 1
由性質2及完全二叉樹的定義有：
結點數滿足：
可寫成:
有:
向下取整，
性質5：在按層序編號的n個結點的完全二叉樹中，任意一個結點i(1<=i<=n)有：
(1)i = 1時，結點i是樹的根，否則(i> 1)，結點i的雙親為i/2(向下取整),如
2<=i=2.5<=3,取i = 2.
(2)2i > n時，結點i無左孩子，為葉結點，否則結點i的左孩子為結點2i
(3) 2i+1 > n時，結點i無右孩子，否則結點i的右孩子為結點2i +1.
性質4與性質五是針對完全二叉樹而言的。性質6是針對二叉樹的鏈式存儲結構而言。
性質6: 含有n個結點的二叉鏈表中，有n + 1個空鏈域。
因為
又有
(2)-(1):
即
