數(shù)據(jù)結(jié)構(gòu)3(樹形結(jié)構(gòu))

2.樹形結(jié)構(gòu)伍之昂江蘇省電子商務(wù)重點(diǎn)實(shí)驗(yàn)室南京財(cái)經(jīng)大學(xué)Email:

zawuster@第一部分：數(shù)據(jù)結(jié)構(gòu)樹的基本概念（1）樹狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；每一個(gè)子節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)；沒有前驅(qū)的節(jié)點(diǎn)為根節(jié)點(diǎn)；除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為m個(gè)不相交的子樹。例子：家譜

樹的基本概念（2）節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；樹的度：一棵樹中，最大的節(jié)點(diǎn)度稱為樹的度；葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)；雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；樹的基本概念（3）節(jié)點(diǎn)的層次：從根開始定義起，根為第0層，

根的子節(jié)點(diǎn)為第1層，以此類推；樹的高度：二叉樹中層數(shù)最大的葉節(jié)點(diǎn)的層數(shù)加1；樹的深度：二叉樹中層數(shù)最大的葉節(jié)點(diǎn)的層數(shù)；只有一個(gè)根節(jié)點(diǎn)的二叉樹的高度為1，深度為0。提醒：《數(shù)據(jù)結(jié)構(gòu)》課程中樹和圖結(jié)構(gòu)中的頂點(diǎn)稱為“節(jié)點(diǎn)”；

而《計(jì)算機(jī)網(wǎng)絡(luò)》課程中的點(diǎn)稱為“結(jié)點(diǎn)”，希望同學(xué)們不要寫錯(cuò)別字！提綱二叉樹哈夫曼樹堆二叉樹二叉樹由節(jié)點(diǎn)的有限集合構(gòu)成:或者為空集或者由一個(gè)根節(jié)點(diǎn)及兩棵不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹(它們也是節(jié)點(diǎn)的集合)組成這是個(gè)遞歸的定義。二叉樹可以是空集合，因此根可以有空的左子樹或右子樹，或者左右子樹皆為空。注：在二叉樹中必須指明兒子節(jié)點(diǎn)是“左后繼”還是“右后繼”，即便該節(jié)點(diǎn)只有一個(gè)后繼。二叉樹的五種基本形態(tài)

(a)空

(b)獨(dú)根(c)空右(d)空左(e)左右都不空二叉樹的特性在二叉樹的第i層上至多有2i個(gè)節(jié)點(diǎn)(i≥0,根為0層)。深度為k的二叉樹中至多含有2k+1-1個(gè)節(jié)點(diǎn)(k≥0)。用數(shù)學(xué)歸納法不難證明。

任何二叉樹，度為0的節(jié)點(diǎn)比度為2的節(jié)點(diǎn)多一個(gè)證明：設(shè)有n個(gè)節(jié)點(diǎn)的二叉樹的度為0、1、2的節(jié)點(diǎn)數(shù)

分別為=n0，n1，n2，則

n=n0+n1+n2

設(shè)邊數(shù)為e。因?yàn)槌酝?，每個(gè)節(jié)點(diǎn)都有一條邊進(jìn)入，故 n=e+1。由于這些邊是有度為1和2的的節(jié)點(diǎn)射出的，

因此e=n1+2·n2，于是

n=e+1=n1+2·n2+1

因此由公式（1）（2）得n0+n1+n2=n1+2·n2+1

即

n0=n2+1

滿二叉樹滿二叉樹：若二叉樹中所有的分支節(jié)點(diǎn)的度數(shù)都為2，且葉子節(jié)點(diǎn)都在同一層次上。中國定義，我們以此為準(zhǔn)。隱含意思：每層都放滿。美國國家標(biāo)準(zhǔn)與技術(shù)研究院給出的定義是：如果一顆二叉樹上任何節(jié)點(diǎn)，或者是樹葉，或者恰有兩顆非空子樹，此二叉樹就為滿二叉樹。國際上卻參照此定義。隱含意思：不存在僅含一顆子樹的節(jié)點(diǎn)。兩種滿二叉樹定義的區(qū)別01234567891011121314012345611121314中國定義，課程采用的滿二叉樹美國及國際定義完全二叉樹完全二叉樹：假如一棵包含n個(gè)節(jié)點(diǎn)的二叉樹中每個(gè)節(jié)點(diǎn)都可以和滿二叉樹中編號(hào)為0至n-1的節(jié)點(diǎn)一一對(duì)應(yīng)。 一棵深度為h的完全二叉樹中，前h-1層中的節(jié)點(diǎn)都是“滿”的，且第h層的節(jié)點(diǎn)都集中在左邊。滿二叉樹本身也是完全二叉樹。顯然是按照中國定義的滿二叉樹。0123456789完全二叉樹的特性有n(n>0)個(gè)節(jié)點(diǎn)的完全二叉樹的深度為

log2(n+1)-1，高度為log2(n+1)證明：設(shè)該二叉樹深度為d，該樹最多有2d+1-1個(gè)節(jié)點(diǎn)，我們有：

2d-1<n≤2d+1-1,即：2d<n+1≤2d+1

兩邊取對(duì)數(shù)，有：d<log2(n+1)≤d+1,

該不等式表明：若log2(n+1)為整數(shù)，log2(n+1)=d+1；

若log2(n+1)不為整數(shù)，那么，log2(n+1)>1，

因此，d=log2(n+1)-1，

其中，log2(n+1)

表示向上取整（如：1.5=2）。

顯然，高度h=d+1=log2(n+1)

.證畢。完全二叉樹編號(hào)的規(guī)律有n個(gè)節(jié)點(diǎn)的二叉樹，根節(jié)點(diǎn)標(biāo)為0，即：0≤i≤n-1，對(duì)編號(hào)為i的節(jié)點(diǎn)，我們有：若：i=0，則該節(jié)點(diǎn)為根節(jié)點(diǎn)；若：節(jié)點(diǎn)i有左后繼，那么，該左后繼節(jié)點(diǎn)編號(hào)為2i+1；若：節(jié)點(diǎn)i有右后繼，那么，該右后繼節(jié)點(diǎn)編號(hào)為2i+2；若：節(jié)點(diǎn)i有父節(jié)點(diǎn)，那么，該父節(jié)點(diǎn)編號(hào)為i/2-1；不做理論證明，請(qǐng)通過右下角圖驗(yàn)證。0123456789上述推導(dǎo)的本質(zhì)是等比數(shù)列通項(xiàng)和求和，很多試題都圍繞這些內(nèi)容展開。很多教材從1開始編號(hào)，即：根的層次為1，根節(jié)點(diǎn)編號(hào)為1，上述特性和規(guī)律將發(fā)生細(xì)微變化。請(qǐng)同學(xué)們課后仔細(xì)推導(dǎo)！二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹中的數(shù)據(jù)元素，這種方法僅適用于完全二叉樹。根節(jié)點(diǎn)放到SqBiTree[0]，按照左后繼、右后繼依次存儲(chǔ)；定位按照前面所述編號(hào)規(guī)律來進(jìn)行，方便快捷；如果該樹不是完全二叉樹，將浪費(fèi)存儲(chǔ)空間。const

MAXSIZE=100;

//暫定二叉樹中節(jié)點(diǎn)數(shù)的最大值為100

typedefstruct

{

ElemType*data;

//存儲(chǔ)空間基址(初始化時(shí)分配空間)

int

nodeNum;

//二叉樹中節(jié)點(diǎn)數(shù)

}SqBiTree;

//二叉樹的順序存儲(chǔ)結(jié)構(gòu)

二叉樹的存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1）typedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

}*BiTree;

dataRchildLchild二叉樹的存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（2）上面鏈?zhǔn)浇Y(jié)構(gòu)只能從根向下找，無法直接獲得節(jié)點(diǎn)的父節(jié)點(diǎn)我們當(dāng)然能夠增加1個(gè)指向父節(jié)點(diǎn)的指針。typedefstructTriTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

struct

BiTNode*parent;

//雙親指針

}*TriTree;

二叉樹的遍歷遍歷(周游)：系統(tǒng)地訪問數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都正好被訪問到一次?！罢谩钡暮x：當(dāng)且僅當(dāng)(ifandonlyif)遍歷一棵二叉樹的過程實(shí)際上就是把二叉樹的節(jié)點(diǎn)放入一個(gè)線性序列的過程，或者說把二叉樹進(jìn)行線性化。樹的遍歷、圖的遍歷，是數(shù)據(jù)結(jié)構(gòu)中最重要的議題。三種遍歷策略先序遍歷中序遍歷后序遍歷同樣重要，各有用處，有關(guān)樹的90%的試題都是圍繞三種遍歷展開。遞歸定義二叉樹是由“根節(jié)點(diǎn)”、“左子樹”和“右子樹”三部分構(gòu)成，則遍歷二叉樹的操作可分解為“訪問根節(jié)點(diǎn)”、“遍歷左子樹”和“遍歷右子樹”三個(gè)子操作。因此，不難得到三種遍歷的遞歸定義：先序遍歷：訪問根節(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹；中序遍歷：中序遍歷左子樹；訪問根節(jié)點(diǎn)；中序遍歷右子樹；后序遍歷：后序遍歷左子樹；后序遍歷右子樹；訪問根節(jié)點(diǎn)。三種遍歷的例子先序遍歷：ABDCEGFHI中序遍歷：DBAEGCHFI后序遍歷：DBGEHIFCA題型：給定兩個(gè)遍歷序列，求樹或第三個(gè)遍歷序列已知7個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1245637（數(shù)字為節(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是4652731，畫出這棵樹(或問，該樹的中序遍歷結(jié)果是什么？)啟示：給定任意兩種遍歷序列，唯一確定這棵樹。先序遍歷：遞歸偽代碼template<classT>voidBinaryTree<T>::PreOrder(BinaryTreeNode<T>*root)｛ if(root!=NULL){ Visit(root); //訪問根節(jié)點(diǎn)

PreOrder(root->leftchild());//訪問左子樹

PreOrder(root->rightchild());//訪問右子樹

}｝

注：Visit(root)是個(gè)抽象操作，實(shí)際上，“訪問”可以在該節(jié)點(diǎn)上做任何操作。中序遍歷：遞歸偽代碼template<classT>voidBinaryTree<T>::PreOrder(BinaryTreeNode<T>*root)｛ if(root!=NULL){

PreOrder(root->leftchild());//訪問左子樹Visit(root); //訪問根節(jié)點(diǎn)

PreOrder(root->rightchild());//訪問右子樹

}｝

后序遍歷：遞歸偽代碼template<classT>voidBinaryTree<T>::PreOrder(BinaryTreeNode<T>*root)｛ if(root!=NULL){

PreOrder(root->leftchild());//訪問左子樹

PreOrder(root->rightchild());//訪問右子樹Visit(root); //訪問根節(jié)點(diǎn)

}｝

樹遍歷的非遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)樹遍歷固然一目了然，但是，很多應(yīng)用問題難以用遞歸方法來解決；非遞歸實(shí)現(xiàn)樹遍歷便于我們更精細(xì)的控制遍歷過程，靈活實(shí)現(xiàn)很多看似復(fù)雜的應(yīng)用問題。棧是實(shí)現(xiàn)遞歸最常用的結(jié)構(gòu)，非遞歸實(shí)現(xiàn)需要用到棧。非遞歸實(shí)現(xiàn)：先序遍歷思想遇到一個(gè)節(jié)點(diǎn)，就訪問該節(jié)點(diǎn)，并把此節(jié)點(diǎn)推入棧中，然后下降去遍歷它的左子樹；遍歷完它的左子樹后，從棧頂托出這個(gè)節(jié)點(diǎn)，并按照它的右鏈接指示的地址再去周游該節(jié)點(diǎn)的右子樹結(jié)構(gòu)。非遞歸實(shí)現(xiàn)：先序遍歷偽代碼注意：先將右子樹推進(jìn)棧非遞歸實(shí)現(xiàn)：中序遍歷思想遇到一個(gè)節(jié)點(diǎn)，就把它推入棧中，并去遍歷它的左子樹；注意：此時(shí)不訪問遍歷完左子樹后，從棧頂托出這個(gè)節(jié)點(diǎn)并訪問之，然后按照它的右鏈接指示的地址再去遍歷該節(jié)點(diǎn)的右子樹。節(jié)點(diǎn)擴(kuò)展標(biāo)記位在二叉樹node結(jié)構(gòu)里增加1個(gè)標(biāo)記位tag記錄該節(jié)點(diǎn)狀態(tài)，初始時(shí)：tag=0。tag=0，表示左子樹未訪問；tag=1，表示左子樹已經(jīng)訪問，該訪問自己了。dataRchildLchildtagtypedefstructBiTNode{

ElemTypedata;

structBiTNode*Lchild,*Rchild;//左、右孩子指針

int

tag=0;

}*BiTree;

非遞歸實(shí)現(xiàn)：中序遍歷偽代碼非遞歸實(shí)現(xiàn)：后序遍歷思想遇到一個(gè)節(jié)點(diǎn)，把它推入棧中，遍歷它的左子樹；遍歷結(jié)束后，還不能馬上訪問處于棧頂?shù)脑摴?jié)點(diǎn)，而是要再按照它的右鏈接結(jié)構(gòu)指示的地址去遍歷該節(jié)點(diǎn)的右子樹；遍歷遍右子樹后才能從棧頂托出該節(jié)點(diǎn)并訪問之。tag語義略微發(fā)生變化tag=0，表示左右子樹均未訪問；tag=1，表示左子樹已經(jīng)訪問，該訪問右子樹了；tag=2，表示左右子樹均已經(jīng)訪問，該訪問自己了。非遞歸實(shí)現(xiàn)：后序遍歷偽代碼樹遍歷非遞歸算法總結(jié)非遞歸算法的寫法有很多種，我們只是用統(tǒng)一的框架來描述了這三種遍歷進(jìn)棧出棧操作，出棧過程，我們根據(jù)需要設(shè)置標(biāo)記位來表明該節(jié)點(diǎn)的左(或右)子樹是否被遍歷。希望同學(xué)們理解并熟記該框架，很多應(yīng)用問題只需要改變Visit(p)操作就可以實(shí)現(xiàn)。二叉樹遍歷應(yīng)用舉例(1)統(tǒng)計(jì)二叉樹中葉子節(jié)點(diǎn)的數(shù)量

容易想到，實(shí)現(xiàn)這個(gè)操作只要對(duì)二叉樹"遍歷"一遍，并在遍歷過程中對(duì)"葉子節(jié)點(diǎn)計(jì)數(shù)"即可。顯然這個(gè)遍歷的次序可以隨意，即先序或中序或后序均可，只是為了在遍歷的同時(shí)進(jìn)行計(jì)數(shù)，需要在算法的參數(shù)中設(shè)一個(gè)"計(jì)數(shù)器"。統(tǒng)計(jì)二叉樹中非葉子節(jié)點(diǎn)的數(shù)量void

CountLeaf(BiTreeT,int&count)

{

//先序遍歷二叉樹，以count返回二叉樹中葉子節(jié)點(diǎn)的數(shù)目

if

(T){

if((!T->Lchild)&&(!T->Rchild))

count++;

//對(duì)葉子節(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->Lchild,count);

CountLeaf(T->Rchild,count);

}//if

}//CountLeaf

二叉樹遍歷應(yīng)用舉例(2)求二叉樹的深度和高度任何遍歷均可，每下去一層，深度加1，但是，注意，將當(dāng)前最大深度保存下來。intmaxdepth=-1;//當(dāng)前最大深度void

BiTreeDepth(BiTreeT,intdepth)

{

//

T指向二叉樹的根，depth為T所指節(jié)點(diǎn)所在層次，初值為0

if

(T){

if

(depth>maxdepth)maxdepth=depth;

BiTreeDepth(T->Lchild,depth+1);

BiTreeDepth(T->Rchild,depth+1);

}//if

}//BiTreeDepth

//全局變量maxdepth最終保存的就是樹的深度二叉樹遍歷應(yīng)用舉例(3)-1輸出二叉樹中每一棵樹中從根到所有葉子節(jié)點(diǎn)的路徑從樹的根節(jié)點(diǎn)出發(fā)，沿著各個(gè)分支可以到達(dá)所有葉子節(jié)點(diǎn)，由途徑所有節(jié)點(diǎn)構(gòu)成的節(jié)點(diǎn)序列稱為從根到葉的路徑，途徑分支個(gè)數(shù)稱作路徑長度；用遞歸算法就很難實(shí)現(xiàn)了，因?yàn)?，遞歸算法不保存中間狀態(tài)。輸出路徑：ADFADGK二叉樹遍歷應(yīng)用舉例(3)-2回憶后序遍歷的非遞歸算法當(dāng)Visit(p)時(shí)，p的節(jié)點(diǎn)的所有祖先一定都在棧中，因?yàn)?，后序決定子節(jié)點(diǎn)在父節(jié)點(diǎn)之前被訪問，因此，p被訪問時(shí)，他的所有父節(jié)點(diǎn)都未被訪問，因此，必然在棧中。據(jù)此，我們很容易修改Visit(p)函數(shù)解決這一問題：判斷p是否為葉節(jié)點(diǎn)，即p->Lchild==NULL&&p-Rchild==NULL，若是，反序打印棧中所有節(jié)點(diǎn)，即為根到p的路徑。留為作業(yè)，請(qǐng)同學(xué)們至少寫出偽代碼，最好上機(jī)驗(yàn)證。廣度優(yōu)先遍歷二叉樹上述三種遍歷本質(zhì)上是深度優(yōu)先遍歷。廣度優(yōu)先遍歷：從二叉樹的第一層（根節(jié)點(diǎn)）開始，自上至下逐層遍歷；在同一層中，按照從左到右的順序?qū)?jié)點(diǎn)逐一訪問。例如：ABCDEFGHI廣度優(yōu)先遍歷實(shí)現(xiàn)方式廣度優(yōu)先遍歷沒有遞歸實(shí)現(xiàn)方法，非遞歸實(shí)現(xiàn)依賴于隊(duì)列下一章，圖的廣度遍歷也是如此！廣度優(yōu)先遍歷二叉樹：偽代碼與先序遍歷非遞歸代碼比較，區(qū)別有哪些？提綱二叉樹哈夫曼樹堆Huffman樹(哈夫曼樹)最優(yōu)樹，又稱哈夫曼樹（HuffmanTree）是一類帶權(quán)路徑長度最短的樹，本節(jié)僅限于討論最優(yōu)二叉樹。 路徑：從樹的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的分支構(gòu)成一條路徑。路徑長度：路徑上的分支數(shù)目稱路徑長度，計(jì)算方法為：根節(jié)點(diǎn)為0，路徑上遇到1個(gè)節(jié)點(diǎn)路徑長度增加1，直到葉節(jié)點(diǎn)為止?，F(xiàn)在，假設(shè)每個(gè)葉子節(jié)點(diǎn)上帶有權(quán)值為wk(k=1,2,…,n)，則樹的帶權(quán)路徑長度定義為樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記作

其中：lk為根節(jié)點(diǎn)到也節(jié)點(diǎn)k的路徑長度。例子例如，右圖中的四棵二叉樹，都有5個(gè)葉子節(jié)點(diǎn)且?guī)嗤瑱?quán)值5、6、2、9、7，它們的帶權(quán)路徑長度分別為 WPL=7*3+9*3+5*2+6*

2+2*2=74(左上圖)

WPL=2*1+6*3+7*4+9*4+5*2=94(右上圖)

WPL=6*2+7*2+5*3+2*3+9*2=65(左下圖)

WPL=2*1+5*3+7*3+9*3+6*3=83(右下圖) 最優(yōu)樹構(gòu)造方法哈夫曼最早給出了一個(gè)構(gòu)造最優(yōu)樹的帶有一般規(guī)律的算法，故稱哈夫曼樹。首先，按照“權(quán)”(例如頻率)將字母排為一列。接著，拿走前兩個(gè)字母(“權(quán)”最小的兩個(gè)字母)，再將它們標(biāo)記為Huffman樹的樹葉，將這兩個(gè)樹葉標(biāo)為一個(gè)分支節(jié)點(diǎn)的兩個(gè)子女，而該節(jié)點(diǎn)的權(quán)即為兩樹葉的權(quán)之和。將所得“權(quán)”放回序列中適當(dāng)位置，使“權(quán)”的順序保持。重復(fù)上述步驟直至序列中只剩一個(gè)元素，則Huffman樹建立完畢。以上頁例子5個(gè)節(jié)點(diǎn)5、6、2、9、7為例。哈夫曼樹應(yīng)用：前綴編碼一個(gè)編碼集合中，任何一個(gè)字符的編碼都不是另外一個(gè)字符編碼的前綴，這種編碼叫作前綴編碼Why?前綴編碼是不等長編碼，與等長編碼相比，可以使傳送電文的字符串的總長度盡可能地短。例如：8個(gè)字符組成的字符串“AABACCDA”，如果我們用2位二進(jìn)制碼等長編碼，用16位二進(jìn)制就可以表示這個(gè)字符串。若按頻率：A:4,C:2,B:1,D:1，構(gòu)造哈夫曼樹，并規(guī)定左分支表示字符‘0’，右分支表示字符‘1’，得到編碼：A:0,C:11,B:100,D:101，用14位二進(jìn)制碼就可以表示這個(gè)字符串。其成功的本質(zhì)在于：頻率高的字符的編碼盡量短。這種前綴特性保證了代碼串被反編碼時(shí)，不會(huì)有多種可能。A:4,C:2,B:1,D:1的哈夫曼樹ACBD010011011100101提綱二叉樹哈夫曼樹堆堆最小值堆：最小值堆是一個(gè)關(guān)鍵碼序列

{K0，K1，…Kn-1}，它具有如下特性：Ki≤K2i+1(i=0，1，…，

n/2-1)Ki≤K2i+2類似可以定義最大值堆。堆的性質(zhì)堆實(shí)際上是一個(gè)完全二叉樹的層次序列，可以用數(shù)組表示堆中儲(chǔ)存的數(shù)是局部有序的節(jié)點(diǎn)儲(chǔ)存的值與其子女儲(chǔ)存的值之間存在某種聯(lián)系。有兩種不同的堆，決定于其關(guān)于聯(lián)系的定義堆中任何一個(gè)節(jié)點(diǎn)與其兄弟之間都沒有必然的聯(lián)系堆不唯一。從邏輯角度看，堆實(shí)際上是一種樹型結(jié)構(gòu)建堆過程堆本質(zhì)上是二叉樹，順序存儲(chǔ)；將全部元素全部插入二叉樹中，然后從最后一個(gè)分支節(jié)點(diǎn)逐個(gè)向上“調(diào)整”假設(shè)根的左、右子樹都已是堆，并且根的元素名為R。這種情況下，有兩種可能：(1)R的值小于或等于其兩個(gè)子女，此時(shí)堆已完成；(2)R