樹求度數的3個公式？
1.節點的度與樹的度
節點的度：結點擁有的子樹數目稱為結點的度，葉子結點 就是度為0的結點
樹的度：樹內各結點的度的最大值
分支節點：度不為0的節點
--------------------------------------------------
節點數n=n0+n1+n2， ( n0：度為0的結點數，n1:度為1的結點 n2：度為2的結點數。 n是總結點)
非空二叉樹，n0=n2+1；
當節點數n為奇數，無度為1的節點；節點n為偶數，有一個度為1的節點；
--------------------------------------------------
分支數=n-1 =1*n1+ 2*n2+3*n3
n0+n1+n2+n3 = n = 分支數+1 = 1*n1+ 2*n2+3*n3+1
2.樹的深度與高度
節點 ni 的深度：從根節點到 ni 的的唯一路徑長。即，節點 ni 所在的層次（根節點為0層），樹的深度 = 樹中節點的最大層次。
節點 ni 的高度：從 ni 到一片樹葉的最長路徑長。即，葉子節點的高度為0，樹的高度 = 根的高度。
樹的深度 = 樹的高度
高度為h的二叉樹至少2^h個節點，至多有2^（h+1）-1 個節點。
含有n≥1 個節點的二叉樹的高度范圍：[ | log2 n」,n-1]
3.完全二叉樹：
只有最下面的兩層結點度小于2，并且最下面一層的結點都集中在該層最左邊的若干位置。
有 n 個節點的完全二叉樹的高度（深度）為 | log2 n」
完全二叉樹第 n 層上至多 2^(n+1)個節點
完全二叉樹第 n 層上節點編號： 2^n - 2^(n+1)-1
--------------------------------------------------
例1：在一棵具有n個結點的完全二叉樹中,樹枝結點的最大編號為( B ).假定樹根結點的編號為1
A.(n-1)/2 B.n/2 C.n/2-1
例2：編號13的左兄弟節點是（ A ），右兄弟節點是（ B ）
A.12 B.14
層數 = | log2 n」= 3
3層編號范圍 8-15
例3：若一棵完全二叉樹有768 個結點，則該二叉樹中葉結點的個數是（ C ）。
A.257 B.258 C.384 D.385
n=n0+n1+n2；
當節點數n為奇數，無度為1的節點；節點n為偶數，有一個度為1的節點，n1 = 1；
768=n0+n1+n2；n2=n0-1；
所以n0=384
例4：一顆完全二叉樹第六層有8個葉結點（根為第一層），則結點個數最多有（）個。
正確答案: D 你的答案: B (錯誤)
A.39 B.72 C.104 D.111
二叉樹第k層最多有2的(k-1)次方個節點
1-6層 : 2^6-1=63個
7 層： 24*2 = 48 第七層的節點是第六層的左邊24個的子節點（因為最右邊8個是葉子節點），所以是48個
所以，63+ 48 = 111
例5：將一棵有100個結點的完全二叉樹從根這一層開始，開始進行層次遍歷編號，那么編號最小的葉節點的編號為（根節點為1）
正確答案: C 你的答案: A (錯誤)
49 50 51 52
解析1:完全二叉樹中，對于編號為i的父結點，左孩子編號為2*i'，右孩子編號為2*i+1；
編號為100的節點對應的父節點編號為50，故最小葉子節點編號為51
解析2：深度為6的滿二叉樹的節點數為 2^6 - 1 = 63；
深度為7的滿二叉書的節點數為 2^7 - 1 = 127;
因此含有100個節點的完全二叉樹的深度為7，葉子節點分布在第6層和第7層。
第七層葉子節點數為：100 - 63 = 37；
37 / 2 = 18余1；
因此，第6層的前18個節點是2度節點，第19個節點是1度節點即只有左子樹，沒有右子樹，即第6層前19個節點為非葉子節點，之后為葉子節點。
因此編號最小的葉子節點編號為：2 ^5 - 1 + 19 + 1 = 51.
其中，2^5 - 1位前5層非葉子節點數（由滿二叉樹的節點計算公式得出）
4.滿二叉樹：
是一顆完全二叉樹；除了葉結點外每一個結點都有左右子葉且葉結點都處在最底層。
第 n 層有 2^(n+1)-1 個節點
深度為k，且有 2^(k+1)－1個節點。
5.堆：
是一顆完全二叉樹；
大頂堆：左右子樹的結點值都小于根結點值，左右子樹都是大頂堆。
小頂堆：左右子樹的結點值都大于根結點值，左右子樹都是小頂堆。
6.二叉排序樹（二叉查找樹）：
左子樹上的值都小于根結點的值，右子樹上的值都大于根結點得值，左右子樹都是二叉排序樹。
例：將整數序列（7-2-4-6-3-1-5）按所示順序構建一棵二叉排序樹a（亦稱二叉搜索樹），之后將整數8按照二叉排序樹規則插入樹a中，請問插入之后的樹a中序遍歷結果是____。
正確答案: A 你的答案: A (正確)
A.1-2-3-4-5-6-7-8 B.7-2-1-4-3-6-5-8 C.1-3-5-2-4-6-7-8
D.1-3-5-6-4-2-8-7 E.7-2-8-1-4-3-6-5 F.5-6-3-4-1-2-7-8
不用看題目直接看答案排除，二叉排序樹的中序遍歷一定有序
7
2
8
1
4
3
6
5
例：假設某棵二叉查找樹的所有鍵均為1到10的整數，現在我們要查找5。下面____不可能是鍵的檢查序列。
A.10,9,8,7,6,5 B.2,8,6,3,7,4,5 C.1,2,9,3,8,7,4,6,5 D.2,3,10,4,8,5 E.4,9,8,7,5 F.以上均正確
?
7.平衡二叉樹（ALV）：
是一顆二叉排序樹；左子樹和右子樹的高度差值不超過1，左右子樹都為平衡二叉樹。
插入，查找，刪除的時間復雜度最好情況和最壞情況都維持在O(logN)
插入操作：在平衡二叉樹中插入結點與二叉查找樹最大的不同在于要隨時保證插入后整棵二叉樹是平衡的。那么調整不平衡樹的基本方法就是： 旋轉，基本思路都是轉換到左旋和右旋。
1） 右旋: 在最小平衡子樹根節點平衡因子>=2且在根節點的左孩子的左孩子插入元素，進行右旋
?
2） 左旋: 在最小平衡子樹根節點平衡因子>=-2且在根節點的右孩子的右孩子插入元素，進行左旋。
?
3） 右左：最小平衡子樹根節點(80)的右孩子(100)的左孩子(90)的子節點(95)插入新元素，先繞根節點的右孩子節點(100)右旋，再圍根節點(80)左旋
?
4） 左右：在最小平衡子樹根節點(80)的左孩子(50)的右孩子(70)的子節點插入新元素，先繞根節點的左孩子節點(50)右旋，再圍根節點(80)左旋
?
8.紅黑樹：
與AVL類似，平衡二叉B樹，并不追求“完全平衡”——它只要求部分地達到平衡要求，降低了對旋轉的要求，從而提高了性能。
紅黑樹的算法時間復雜度和AVL相同
紅黑樹的特性:
（1）每個節點或者是黑色，或者是紅色。
（2）根節點是黑色。
（3）每個葉子節點（NIL）是黑色。 [注意：這里葉子節點，是指為空(NIL或NULL)的葉子節點！]
（4）如果一個節點是紅色的，則它的子節點必須是黑色的。
（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
注意：
(特性(3)中的葉子節點，是只為空(NIL或null)的節點。
特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
根據被插入節點的父節點的情況，可以將"當節點z被著色為紅色節點，并插入二叉樹"劃分為三種情況來處理。
① 情況說明：被插入的節點是根節點。
處理方法：直接把此節點涂為黑色。
② 情況說明：被插入的節點的父節點是黑色。
處理方法：什么也不需要做。節點被插入后，仍然是紅黑樹。
③ 情況說明：被插入的節點的父節點是紅色。
處理方法：那么，該情況與紅黑樹的“特性(5)”相沖突。這種情況下，被插入節點是一定存在非空祖父節點的；進一步的講，被插入節點也一定存在叔叔節點(即使叔叔節點為空，我們也視之為存在，空節點本身就是黑色節點)。理解這點之后，我們依據"叔叔節點的情況"，將這種情況進一步劃分為3種情況(Case)。
現象說明
處理策略
Case 1
當前節點的父節點是紅色，且當前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。
(01) 將“父節點”設為黑色。
(02) 將“叔叔節點”設為黑色。
(03) 將“祖父節點”設為“紅色”。
(04) 將“祖父節點”設為“當前節點”(紅色節點)；即，之后繼續對“當前節點”進行操作。
Case 2
當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的右孩子
(01) 將“父節點”作為“新的當前節點”。
(02) 以“新的當前節點”為支點進行左旋。
Case 3
當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的左孩子
(01) 將“父節點”設為“黑色”。
(02) 將“祖父節點”設為“紅色”。
(03) 以“祖父節點”為支點進行右旋。
上面三種情況(Case)處理問題的核心思路都是：將紅色的節點移到根節點；然后，將根節點設為黑色。下面對它們詳細進行介紹。
紅黑樹的應用
紅黑樹的應用比較廣泛，主要是用它來存儲有序的數據，它的時間復雜度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬內存的管理，都是通過紅黑樹去實現的。
2-3-4樹
2-3-4樹和紅黑樹一樣，也是平衡樹。只不過不是二叉樹，它的子節點數目可以達到4個。
每個節點存儲的數據項可以達到3個。名字中的2,3,4是指節點可能包含的子節點數目。具體而言：
1、若父節點中存有1個數據項，則必有2個子節點。
2、若父節點中存有2個數據項，則必有3個子節點。
3、若父節點中存有3個數據項，則必有4個子節點。
也就是說子節點的數目是父節點中數據項的數目加一。因為以上三個規則，使得除了葉結點外，其他節點必有2到4個子節點，不可能只有一個子節點。所以不叫1-2-3-4樹。而且2-3-4樹中所有葉結點總是在同一層。
9.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.所有葉子結點位于同一層；
如：（M=3）
?
B-樹的特性：
1.關鍵字集合分布在整顆樹中；
2.任何一個關鍵字出現且只出現在一個結點中；
3.搜索有可能在非葉子結點結束；
4.其搜索性能等價于在關鍵字全集內做一次二分查找；
5.自動層次控制；
由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少
利用率，其
