樹結構中，結點總數（包括根和葉子）=邊數（等于度）+1
1.二叉樹 性質1：對任何一顆二叉樹T，如果其終端節點數為n0,度為2的節點數為n2，則n0 = n2+1; 性質2：具有n個結點的完全二叉樹的深度為|log2 (n)|+1
二叉樹進行層次周遊，應借助一個隊列，二叉樹的先序、中序、後序的非遞歸周遊需要用到棧。
（1）完全二叉樹 一、葉子結點隻可能在最大的兩層上出現,對任意結點，若其右分支下的子孫最大層次為L，則其左分支下的子孫的最大層次必為L 或 L+1；
完全二叉樹的存儲結構通常采用順序存儲結構。 完全二叉樹中，非葉子結點頂多沒有右孩子，沒有左孩子的話，就表示沒有子節點。
對完全二叉樹的編号是由上而下，由左而右進行的，是以若某節點無左孩子，則必然無右孩子。即為葉子結點。 二、出于簡便起見,完全二叉樹通常采用數組而不是連結清單存儲,其存儲結構如下:
var tree:array[1..n]of longint;{n:integer;n>=1}
對于tree[i]，有如下特點：
（1）若i為奇數且i>1，那麼tree[i]的左兄弟為tree[i-1]；
（2）若i為偶數且i<n，那麼tree[i]的右兄弟為tree[i+1]；
（3）若i>1，tree[i]的雙親為tree[i div 2]；
（4）若2*i<=n，那麼tree[i]的左孩子為tree[2*i]；若2*i+1<=n，那麼tree[i]的右孩子為tree[2*i+1]；
（5）若i>n div 2,那麼tree[i]為葉子結點（對應于（3））；
（6）若i<(n-1) div 2.那麼tree[i]必有兩個孩子（對應于（4））。
特别地：滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹
完全二叉樹葉子節點的算法
如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編号為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可 知：n0＝n2＋1，則n= n0＋n1＋n2（其中n為完全二叉樹的結點總數），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉樹中度為1的結點數隻有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一個公式：n0＝（n＋1） /2 ，就可根據完全二叉樹的結點總數計算出葉子結點數。
哈夫曼樹是一種最優二叉樹，利用哈夫曼樹尋找一顆最佳判定樹，即總的比較次數最少的判定樹。 是以，哈夫曼樹中不存在結點度為1的結點。 哈夫曼樹不是滿二叉樹，是正則二叉樹（也叫正規二叉樹），其中隻有度為0和度為2的結點，因為n0 = n2 + 1，是以n個葉子的正則二叉樹自然隻有2n-1個結點。至于滿二叉樹當然也是正則二叉樹的特例。
二叉連結清單 性質1：在n個結點的二叉連結清單中，有n+1個空指針域 利用中序周遊，并結合先序周遊或後序周遊就能重新構造二叉樹（單一周遊序列無法構造 二叉樹）。
2.AVL平衡二叉樹 定義：平衡二叉樹或為空樹,或為如下性質的二叉排序樹:
（1）左右子樹深度之差的絕對值不超過1;
（2）左右子樹仍然為平衡二叉樹.
平衡因子BF=左子樹深度－右子樹深度.
平衡二叉樹每個結點的平衡因子隻能是1，0，-1。若其絕對值超過1，則該二叉排序樹就是不平衡的。
構造與調整方法平衡二叉樹的常用算法有紅黑樹、AVL、Treap、伸展等。最小平衡二叉樹的節點公式如下：F(n) = F(n-1)+F(n-2)+1.
平衡二叉樹的缺點： 插入和删除運算變得複雜化，進而降低了他們的運算速度。
平衡二叉樹的時間複雜度是log(n)，如果二叉樹的元素個數為n，那麼不管是對樹進行插入節點、查找、删除節點都是log(n)次循環調用就可以了。它的時間複雜度相對于其他資料結構如數組等是最優的。 3.RBT紅黑樹 AVL是嚴格平衡樹，是以在增加或者删除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多；
紅黑是弱平衡的，用非嚴格的平衡來換取增删節點時候旋轉次數的降低；
是以簡單說，搜尋的次數遠遠大于插入和删除，那麼選擇AVL樹，如果搜尋，插入删除次數幾乎差不多，應該選擇RB樹。
紅黑樹上每個結點内含五個域，color，key，left，right，p。如果相應的指針域沒有，則設為NIL。
一般的，紅黑樹，滿足以下性質，即隻有滿足以下全部性質的樹，我們才稱之為紅黑樹：
1）每個結點要麼是紅的，要麼是黑的。
2）根結點是黑的。
3）每個葉結點，即空結點（NIL）是黑的。
4）如果一個結點是紅的，那麼它的倆個兒子都是黑的。
5）對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。
紅黑樹插入操作的平均時間複雜度為O（logn）,最壞時間複雜度為O（logn）;
4.B-樹
是一種平衡多路搜尋樹（并不是二叉的）：
1.定義任意非葉子結點最多隻有M個兒子；且M>2；
2.根結點的兒子數為[2, M]；
3.除根結點以外的非葉子結點的兒子數為[M/2, M]；
4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的
子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
8.所有葉子結點位于同一層；
5.B+樹
B+樹是B-樹的變體，也是一種多路搜尋樹：
1.其定義基本與B-樹同，除了：
2.非葉子結點的子樹指針與關鍵字個數相同；
3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹
（B-樹是開區間）；
5.為所有葉子結點增加一個鍊指針；
6.所有關鍵字都在葉子結點出現；
如：（M=3）
B+的搜尋與B-樹也基本相同，差別是B+樹隻有達到葉子結點才命中（B-樹可以在
非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；
B+的特性：
1.所有關鍵字都出現在葉子結點的連結清單中（稠密索引），且連結清單中的關鍵字恰好
是有序的；
2.不可能在非葉子結點命中；
3.非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲
（關鍵字）資料的資料層；
4.更适合檔案索引系統；比如對已經建立索引的資料庫記錄，查找10<=id<=20，那麼隻要通過根節點搜尋到id=10的葉節點，之後隻要根據葉節點的連結清單找到第一個大于20的就行了，比B-樹在查找10到20内的每一個時每次都從根節點出發查找提高了不少效率。
B+樹插入操作的平均時間複雜度O（logn）,最壞時間複雜度為O（logn）;