樹的基本概念

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

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

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

完全二叉樹若設(shè)二叉樹的高度為h,除第h層外，其它各層(1?h-1)的結(jié)點數(shù)都達到最大個數(shù)，第h層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。完全二叉樹特點一、 葉子結(jié)點只可能在最大的兩層上出現(xiàn),對任意結(jié)點，若其右分支下的子孫最大層次為L,則其左分支下的子孫的最大層次必為L或L+1；二、 出于簡便起見,完全二叉樹通常采用數(shù)組而不是鏈表存儲，其存儲結(jié)構(gòu)如下：vartree:array[1..n]oflongint;{n:integer;n>=1}對于tree[i]，有如下特點：若i為奇數(shù)且i>1，那么tree[i]的左兄弟為tree[i-1]；若i為偶數(shù)且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]為葉子結(jié)點(對應(yīng)于(3))；若i<(n-1)div2.那么tree[i]必有兩個孩子(對應(yīng)于(4))。特別地：滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹完全二叉樹葉子節(jié)點的算法如果一棵具有n個結(jié)點的深度為k的二叉樹，它的每一個結(jié)點都與深度為k的滿二叉樹中編號為1~n的結(jié)點一一對應(yīng)，這棵二叉樹稱為完全二叉樹?？梢愿鶕?jù)公式進行推導(dǎo)，假設(shè)n0是度為0的結(jié)點總數(shù)(即葉子結(jié)點數(shù))，n1是度為1的結(jié)點總數(shù)，n2是度為2的結(jié)點總數(shù)，由二叉樹的性質(zhì)可知：n0=n2+1,則n=n0+n1+n2(其中n為完全二叉樹的結(jié)點總數(shù))，由上述公式把n2消去得：n=2n0+n1—1，由于完全二叉樹中度為1的結(jié)點數(shù)只有兩種可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一個公式：n0=(n+1)/2，就可根據(jù)完全二叉樹的結(jié)點總數(shù)計算出葉子結(jié)點數(shù)。滿二叉樹一棵深度為k,且有2的(k)次方一1個節(jié)點的二叉樹特點：每一層上的結(jié)