樹的基本概念

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

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

百度用戶交流使用更多圖片請(qǐng)?jiān)L問

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