樹(tree)是n(n>=0)個結點的有限集t，t為空時稱為空樹，否則它滿足如下兩個條件：
(1)有且僅有一個特定的稱為根(root)的結點；
(2)其餘的結點可分為m(m>=0)個互不相交的子集t1,t2,t3…tm，其中每個子集又是一棵樹，并稱其為子樹(subtree)。
樹形結構應用執行個體：
1、日常生活：家族譜、行政組織結構；書的目錄
2、計算機：資料總管的檔案夾；
編譯程式：用樹表示源程式的文法結構；
資料庫系統：用樹組織資訊；
分析算法：用樹來描述其執行過程；
3、表達式表示 ( 如 a * b + (c – d / e) * f )
專業術語
1、結點的度(degree)：某結點的子樹的分支個數
葉子(leaf)（終端結點），分支結點（非終端結點），内部結點（b、c、d、e、h），樹的度（3）
2、結點的孩子(child)
雙親(parent)（d為h、i、j的雙親）
兄弟(sibling)(h、i、j互為兄弟)
祖先，子孫(b的子孫為e、k、l、f)
3、結點的層次
根結點為第一層。某結點在第 i 層，其孩子在第 i+1 層。
樹的深度(depth)就是從跟開始往下數
堂兄弟：雙親在同一層的結點，互為堂兄弟
4、有序樹和無序樹
有序樹：
無序樹：
5、森林(forest)是 m (m≥0) 棵互不相交的樹的集合。
對比樹型結構和線性結構的結構特點
線性結構：第一個元素無前驅，最後一個元素無後繼，其它資料元素一個前驅、一個後繼。（唯一頭結點，唯一尾節點；中間結點有唯一前驅，唯一後繼）
樹形結構：根節點無前驅，多個葉子節點無後繼，其它元素一個前驅，多個後繼。（唯一根結點；多個葉結點；中間結點有唯一前驅，多個後繼）
二叉樹
把滿足以下兩個條件的樹型結構叫做二叉樹（binary tree）：
（1）每個結點的度都不大于2；
（2）每個結點的孩子結點次序不能任意颠倒。即使隻有一棵子樹也要進行區分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差别。
二叉樹一共有5種形态
二叉樹的性質
性質1： 在二叉樹的第i層上至多有2^(i-1)個結點(i>=1)。
采用歸納法證明此性質。
（1）當i=1時，2^( i-1)=2^0 =1,命題成立。
（2）假定i=k時命題成立，即第k層最多有2^(k-1)個結點；
（3）由歸納假設可知，由于二叉樹每個結點的度最大為2，故在第k+1層上最大結點數為第k層上最大結點數的2倍，
即2×2^(k-1)＝2^k=2^(k+1)-1
命題得到證明。
性質2 ：深度為 k 的二叉樹至多有 2^k-1個結點(k≥1)。
證明：由性質1可見，深度為k的二叉樹的最大結點數為
性質3： 對任何一棵二叉樹，如果其終端結點數為n0，度為2的結點數為n2，則n0＝n2＋1。
證明：設二叉樹上結點總數 n = n0 + n1 + n2 （1）
又二叉樹上分支總數 b = n1+2n2 （2）
而除根結點外，其餘結點都有分支進入，即 b = n-1
将（1）（2）式代入，得 n0 = n2 + 1 。
兩類特殊的二叉樹：滿二叉樹和完全二叉樹
滿二叉樹：一棵深度為k且有2^k-1個結點的二叉樹。
完全二叉樹：樹中所含的 n 個結點和滿二叉樹中編号為 1 至 n 的結點一一對應。（編号的規則為，由上到下，從左到右。）
性質4：具有n個結點的完全二叉樹的深度為[log2 n]＋1。
證明：假設此二叉樹的深度為k，則根據性質2及完全二叉樹的定義得到：
2^(k-1)－1<n<=2^k-1 或 2^(k-1)<=n<2^k
取對數得到：k－1 <= log2 n < k 因為k是整數。是以有：k＝【log2n】＋1。
性質5： 如果對一棵有n個結點的完全二叉樹的結點按層序編号（從第1層到第【log2n】+1層，每層從左到右),則對任一結點i（1<=i<=n),有：
1）如果i＝1，則結點i無雙親，是二叉樹的根；如果i>1，則其雙親是結點【i/2】。
2）如果2i>n，則結點i為葉子結點，無左孩子；否則，其左孩子是結點2i。
3）如果2i＋1>n，則結點i無右孩子；否則，其右孩子是結點2i＋1。
所示為完全二叉樹上結點及其左右孩子結點之間的關系。
二叉樹的存儲結構
1）順序存儲結構
完全二叉樹：用一組連續的存儲單元依次自上而下、自左至右存儲各結點元素。即将完全二叉樹上編号為i 的結點的值存儲在下标為 i-1 的數組元素中。結點間的關系可由公式計算得到。
一般情形的二叉樹：增添一些空結點使變成完全二叉樹形态，再按上述方法存儲。
如圖完全二叉樹的存儲
單隻二叉樹的存儲
總結：
1、完全二叉樹用順序存儲既節約空間，存取也友善；
2、一般二叉樹用順序存儲，空間較浪費，最壞情況為右單支二叉樹。（一個深度為k且隻有k個節點的單支樹卻需要長度為2^k-1的一維數組）
2）二叉樹的鍊式存儲方式
常用的有二叉連結清單和三叉連結清單存儲結構結點的左右孩子或雙親靠指針來訓示
有時也可用數組的下标來模拟指針,即開辟三個一維數組data ,lchild,rchild 分别存儲結點的元素及其左,右指針域;下面是鍊式存儲的二叉樹表示：
二叉樹連結清單表示的示例：
周遊二叉樹和線索二叉樹
任何一個非空的二叉樹都由三部分構成
樹的周遊是通路樹中每個結點僅一次的過程。周遊可以被認為是把所有的結點放在一條線上，或者将一棵樹進行線性化的處理。
先序周遊
dlr根左右：通路根結點、先序周遊左子樹、先序周遊右子樹
若二叉樹非空
（1）通路根結點；
（2）先序周遊左子樹；
（3）先序周遊右子樹；
若二叉樹為空，結束——基本項（也叫終止項）
若二叉樹非空——遞歸項
主要過程就是遞歸調用，也可以用棧來實作。
對于先序周遊來說，藍色剪頭第一次經過的結點，就是周遊的序列，以後再次經曆就不算進去了。
非遞歸的先序周遊
根據前序周遊通路的順序，優先通路根結點，然後再分别通路左孩子和右孩子。即對于任一結點，其可看做是根結點，是以可以直接通路，通路完之後，若其左孩子不為空，按相同規則通路它的左子樹；當通路其左子樹時，再通路它的右子樹。是以其處理過程如下：
對于任一結點p：
1)通路結點p，并将結點p入棧;
2)判斷結點p的左孩子是否為空，若為空，則取棧頂結點并進行出棧操作，并将棧頂結點的右孩子置為目前的結點p，循環至1);若不為空，則将p的左孩子置為目前的結點p;
3)直到p為null并且棧為空，則周遊結束。
中序周遊、後序周遊和先序周遊思想基本類似，對于中序周遊來說，藍色剪頭第二次經過的結點，就是周遊的序列，之前的和以後的再次經曆就不算進序列裡去了。對于後序周遊來說，藍色剪頭第三次經過的結點，就是周遊的序列，之前經曆的就不算進去了。
ldr左跟右：中序周遊左子樹、通路根結點、中序周遊右子樹
（1）中序周遊左子樹；
（2）通路根結點；
（3）中序周遊右子樹；
（1）中序周遊左子樹；
（2）通路根結點；
（3）中序周遊右子樹；
中序遞歸周遊算法
中序的非遞歸周遊，使用棧
lrd左右跟：後序周遊左子樹、後序周遊右子樹、通路根結點
後序周遊序列:bdfgeca
同理有非遞歸的後續周遊二叉樹
在後序周遊中，要保證左孩子和右孩子都已被通路，并且左孩子在右孩子通路之後才能通路根結點。是以對于任一結點p，先将其入棧。如果p不存在左孩子和右孩子，則可以直接通路它；或者p存在左孩子或者右孩子，但是其左孩子和右孩子都已被通路過了，則同樣可以直接通路該結點。若非上述兩種情況，則将p的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被通路，左孩子和右孩子都在根結點前面被通路。
二叉樹周遊的總結：
無論先序、中序、後序周遊二叉樹，周遊時的搜尋路線是相同的：從根節點出發，逆時針延二叉樹外緣移動，對每個節點均途經三次。
先序周遊：第一次經過節點時通路。（abcd）
中序周遊：第二次經過節點時通路。（badc）
後序周遊：第三次經過節點時通路。（bdca）
辛苦的勞動，轉載請注明出處，謝謝……
http://www.cnblogs.com/kubixuesheng/p/4378266.html