基本概念1=NA結點的層次（Level）從根開始定義，根為第一層，根的孩子為第二層。二叉樹的高度：樹中結點的最大層次稱為樹的深度（Depth）或高度。二叉樹在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（leftsubtree）和“右子樹，（rightsubtree）0二叉樹常被用作二叉查找樹和二叉堆。二叉樹的每個結點至多只有二棵子樹（不存在度大于2的結點），二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的（i-1）次方個結點；深度為k的二叉樹至多有2的k次-1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1o樹和二叉樹的2個主要差別：樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；樹的結點無左、右之分，而二叉樹的結點有左、右之分。......樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結構。又如在數據庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關系的問題都可用樹來描述。一、樹的概述樹結構的特點是：它的每一個結點都可以有不止一個直接后繼，除根結點外的所有結點都有且只有一個直接前趨。以下具體地給出樹的定義及樹的數據結構表示。（一）樹的定義樹是由一個或多個結點組成的有限集合，其中:必有一個特定的稱為根(ROOT)的結點；剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn,而且，這些集合的每一個又都是樹。樹T1、T2 Tn被稱作根的子樹(Subtree)。樹的遞歸定義如下：(1)至少有一個結點(稱為根)(2)其它是互不相交的子樹樹的度一也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。樹的深度一組成該樹各結點的最大層次，如上圖，其深度為4；森林一指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合｛T1,T2,T3｝就為森林；有序樹一指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。樹的表示樹的表示方法有許多，常用的方法是用括號：先將根結點放入一對圓括號中，然后把它的子樹由左至右的順序放入括號中，而對子樹也采用同樣的方法處理；同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。如上圖可寫成如下形式：(A(B(E(K,L),F),C(G),D(H(M),I,J)))2二叉樹二叉樹的基本形態：二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：空二叉樹一(a)；只有一個根結點的二叉樹一(b)；只有右子樹一(c)；(4)只有左子樹一(d)；(5)完全二叉樹一一(e)注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。兩個重要的概念：完全二叉樹一只有最下面的兩層結點度小于2,并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹；滿二叉樹一除了葉結點外每一個結點都有左右子葉且葉結點都處在最底層的二叉樹,。二叉樹的性質在二叉樹中，第i層的結點總數不超過2A(i-1)；深度為h的二叉樹最多有2Ah-1個結點(h>=1)，最少有h個結點；對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1；具有n個結點的完全二叉樹的深度為int(log2n)+1有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：若I為結點編號則如果I<>1，則其父結點的編號為I/2；如果2*I<=N,則其左兒子(即左子樹的根結點)的編號為2*I；若2*I>N，則無左兒子；如果2*I+1<=N,則其右兒子的結點編號為2*I+1；若2*I+1>N，則無右兒子。給定N個節點，能構成h(N)種不同的二叉樹。h(N)為卡特蘭數的第N項。h(n)=C(n,2*n)/(n+1)。二叉樹的存儲結構：(1)順序存儲方式typenode=recorddata:datatypel,r:integer;end;vartr:array[1..n]ofnode;（2）鏈表存儲方式，如：typebtree=Anode；node=recorddata:datatye;lchild,rchild:btree;end;普通樹轉換成二叉樹：凡是兄弟就用線連起來，然后去掉父親到兒子的連線，只留下父母到其第一個子女的連線。二叉樹很象一株倒懸著的樹，從樹根到大分枝、小分枝、直到葉子把數據聯系起來，這種數據結構就叫做樹結構，簡稱樹。樹中每個分叉點稱為結點，起始結點稱為樹根，任意兩個結點間的連接關系稱為樹枝，結點下面不再有分枝稱為樹葉。結點的前趨結點稱為該結點的”雙親"，結點的后趨結點稱為該結點的”子女”或”孩子"，同一結點的”子女”之間互稱”兄弟”。二叉樹：二叉樹是一種十分重要的樹型結構。它的特點是，樹中的每個結點最多只有兩棵子樹，即樹中任何結點的度數不得大于2。二叉樹的子樹有左右之分，而且，子樹的左右次序是重要的，即使在只有一棵子樹的情況下，也應分清是左子樹還是右子樹。定義：二叉樹是結點的有限集合，這個集合或是空的，或是由一個根結點和兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。（三）完全二叉樹對滿二叉樹，從第一層的結點（即根）開始，由下而上，由左及右，按順序結點編號，便得到滿二叉樹的一個順序表示。據此編號，完全二叉樹定義如下：一棵具有n個結點，深度為K的二叉樹，當且僅當所有結點對應于深度為K的滿二叉樹中編號由1至n的那些結點時，該二叉樹便是完全二叉樹。圖4是一棵完全二叉樹。平衡二叉樹當且僅當兩個子樹的高度差不超過1時，這個樹是平衡二叉樹。（同時是排序二叉樹）平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1.。常用算法有：紅黑樹、AVL樹、Treap等。平衡二叉樹的調整方法平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下：⑴每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1,則平衡二叉樹沒有失去平衡，繼續插入結點；⑵若插入結點的某祖先結點的平衡因子的絕對值大于1,則找出其中最小不平衡子樹的根結點；⑶判斷新插入的結點與最小不平衡子樹的根結點的關系，確定是哪種類型的調整；⑷如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；如果是LR型或LR型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現沖突，應用旋轉優先原則調整沖突；⑸計算調整后的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整后的平衡二叉樹中是否存在平衡因子大于1的結點。

(bj..非平衡二叉樹」西色結點為不平衡園子圖1平1二：叉肉和非平蹭二尺樹L^n^.ciTyabatei(b)左邊的圖左子數的高度為3,右子樹的高度為1,相差超過1(b)右邊的圖-2的左子樹高度為0右子樹的高度為2,相差超過1完全二叉樹(CompleteBinaryTree)完全二叉樹定義該圖片僅限

百度用戶交流使用更多圖片請訪問

完全二叉樹若設二叉樹的高度為h,除第h層外，其它各層(1?h-1)的結點數都達到最大個數，第h層從右向左連續缺若干結點，這就是完全二叉樹。完全二叉樹特點一、 葉子結點只可能在最大的兩層上出現,對任意結點，若其右分支下的子孫最大層次為L,則其左分支下的子孫的最大層次必為L或L+1；二、 出于簡便起見,完全二叉樹通常采用數組而不是鏈表存儲，其存儲結構如下：vartree:array[1..n]oflongint;{n:integer;n>=1}對于tree[i]，有如下特點：若i為奇數且i>1，那么tree[i]的左兄弟為tree[i-1]；若i為偶數且i<n，那么tree[i]的右兄弟為tree[i+1]；若i>1,tree[i]的雙親為tree[idiv2]；若2*i<=n，那么tree[i]的左孩子為tree[2*i]；若2*i+1<=n，那么tree[i]的右孩子為tree[2*i+1]；若i>ndiv2,那么tree[i]為葉子結點(對應于(3))；若i<(n-1)div2.那么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，就可根據完全二叉樹的結點總數計算出葉子結點數。滿二叉樹一棵深度為k,且有2的(k)次方一1個節點的二叉樹特點：每一層上的結