數(shù)據(jù)結(jié)構(gòu)與算法b-2014年4月30日課堂

數(shù)據(jù)結(jié)構(gòu)與算二叉主講 建堆不必將值一個個 堆中，通過交換形成堆假設(shè)根的左、右子樹都已是堆，并且根的元素名為R。這種情況下，有兩種可能：(1)R的值小于或等于其兩 ，此時堆已完成(2)R的值大于其某一個或全部兩個 中值較小的一個交換，結(jié)果得到一個堆，除 信息學(xué) Page圖示R信息學(xué) Page堆的類定template<classT>classMinHeap{T*heapArray; int //當(dāng)前堆中元素?cái)?shù)intMaxSize; voidBuildHeap(); MinHeap(constintn)；//初始化堆的最大元素?cái)?shù)目virtual~MinHeap(){delete[]heapArray;//析構(gòu)函數(shù)信息學(xué) PageboolisLeaf(intpos)//返回左孩子位intleftchild(intpos)//返回右孩子位intrightchild(intpos)返回父結(jié)點(diǎn)位intparent(intpos)信息學(xué) Page//刪除給定下標(biāo)的元boolRemove(intpos,T&//向堆 新元素boolInsert(constT&T&RemoveMin()；voidSiftUp(intposition);voidSiftDown(intleft)； 信息學(xué) Page堆成MinHeap<T>::MinHeap(constintn){ heapArray=newT[MaxSize]; //此處進(jìn)行堆元素的賦值工}信息學(xué) Pagetemplate<classboolMinHeap<T>::isLeaf(intpos){}所有i>n/2-1的結(jié)點(diǎn)都沒有 堆的建立應(yīng)從n/2-1開始，不斷遞減結(jié)點(diǎn)下信息學(xué)

Pagetemplate<classintMinHeap<T>::leftchild(intpos){return //返回左孩子位template<classT>intMinHeap<T>::rightchild(intpos){return //返回右孩子位template<classT>intMinHeap<T>::parent(intpos){return(pos- //返回父結(jié)點(diǎn)位信息學(xué) Pagetemplate<classvoidMinHeap<T>::SiftDown(int{int //T //int //j將標(biāo)識關(guān)鍵值較小的子結(jié)while(j<CurrentSize)信息學(xué) Pageif((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1])) //j指向數(shù)值較小的子結(jié)if(temp>heapArray[j]){ //向下繼}else}//while信息學(xué) Pagetemplate<classvoid{//反復(fù)調(diào)用篩選函for(inti=CurrentSize/2-1;i>=0;i--)}信息學(xué) Pagetemplate<classvoidMinHeap<T>::SiftUp(int{intTtemp=heapArray[temppos];while((temppos>0)&&{} 信息學(xué) Pagetemplate<classboolMinHeap<T>::Insert(constT&{if(CurrentSize==MaxSize)//returnFALSE; }信息學(xué) Page從最(優(yōu)先隊(duì)列出隊(duì)要求保持完全二叉樹形狀，并且剩下的n-1個結(jié)點(diǎn)值仍然符合堆的性質(zhì)?？梢詫⒍阎凶詈笠粋€位置上的元素(數(shù)組中實(shí)際的最后一個元素)移到根的位置上，利用siftdown對堆重新調(diào)整。T&{{//空cout<<"Can't}信息學(xué) Page{//交換堆頂和最后一個元 <=1就不要調(diào)整了//從堆頂開始篩return}//end}信息學(xué) Pagetemplate<class

boolMinHeap<T>::Remove(intpos,T&{returnfalse;//指定元素置于最T return}信息學(xué) Page建堆n個結(jié)點(diǎn)的堆，深度dlog2(n+1)-1。根為第層，則第i層(除最深一層)結(jié)點(diǎn)個數(shù)為2i大約一半的結(jié)點(diǎn)深度為d-1(或d)，不移動(葉子約1/4結(jié)點(diǎn)深度為d-2(或d-1）每向上一層，結(jié)點(diǎn)的數(shù)目為前一層的一半，而子樹高度加一。元素移動的最大距離的總數(shù)為log

i

O所有i>n/2-1的結(jié)點(diǎn)都沒 結(jié)點(diǎn)，所北堆的建立應(yīng)從n/2-1北建堆建堆算法的時間代價為由于堆logn層深，結(jié)點(diǎn)、刪除普通元素和刪除最小元素的平均時間代價和時間代價(logn)信息學(xué) Page優(yōu)先有些優(yōu)先隊(duì)列的應(yīng)用要求能夠改變已于隊(duì)列中的對象的優(yōu)先權(quán)，典型實(shí)現(xiàn)方法需要一個輔助數(shù)據(jù)結(jié)構(gòu)（二叉搜索樹）。信息學(xué) Page大4.1二叉樹的概4.24.3二叉樹的抽4.4周游二叉4.5二叉樹的實(shí)4.6二叉搜索4.7堆與優(yōu)先隊(duì)4.8Huffman編碼信息學(xué) PageHuffman構(gòu)造一個具有n每個外部結(jié)點(diǎn)Ki有一個wi對應(yīng)，作為該外部結(jié)點(diǎn)的這個擴(kuò)充二叉樹的葉結(jié)點(diǎn)帶權(quán)外部路徑長度總和最i0argmin(n1wii0信息學(xué) Page設(shè)D={d0，…，dn－1}，通信編碼總長最短didj則di的編碼不能是dj的編碼的前綴，反之亦然信息學(xué) Page前綴一個編碼集合中，任何一個字符的編碼都不會是另外一個字符編碼的前綴，這種編碼叫作前綴編碼。前綴特性保證代碼串例8Z(111100),K(111101),F(11111),C(1110),U(100),D(101),L(110),E(0)對于代碼 出唯一的字符串信息學(xué) Page用d0，d1，…，dn－1作外部結(jié)點(diǎn)，W0，W1，…，Wn－1作把從每個結(jié)點(diǎn)引向其左的邊標(biāo)上號碼0，把從每個結(jié)點(diǎn)引向其右的邊標(biāo)上號碼1。從根到每個葉子的路徑上的信息學(xué) Page各字d8：出現(xiàn)信息學(xué) Page從二叉樹的根開始，用需要譯碼的二進(jìn)制位串中的若干個相鄰位與二叉樹邊上標(biāo)的0、1相匹配，確定一條到達(dá)樹葉的路徑。一旦到達(dá)樹葉，則譯出了一個字符。信息學(xué) Page構(gòu)造HuffmanStep1照“權(quán)”(頻率)將字符排Step2:取走“權(quán)”最小的兩個字符，構(gòu)造一個新元素，將這兩個字符標(biāo)為這個元素的左右；該元Step3:若序列中只剩一個元素，則Huffman樹構(gòu)造完畢,退出；否則，返回Step2。信息學(xué) Page信息學(xué) PageHuffman樹template<classT>classHuffmanTree{HuffmanTreeNode<T>* //Huffman樹的樹//把ht1和ht2為根的Huffman子//合并成一棵以parent為根的二叉voidMergeTree(HuffmanTreeNode<T>&HuffmanTreeNode<T>&HuffmanTreeNode<T>*parent信息學(xué) Page//刪除Huffman樹或其子voidDeleteTree(HuffmanTreeNode<T>*root)；//構(gòu)造函數(shù)，weight 權(quán)值的數(shù)組，n是數(shù)組長HuffmanTree(Tweight[],int//析構(gòu)函virtual~HuffmanTree()}信息學(xué) PageHuffmantemplate<classT>HuffmanTree<T>::HuffmanTree(Tweight[],intn){MinHeap<HuffmanTreeNode<T>>heap(n);*parent,&firstchild,&secondchild;HuffmanTreeNode<T>*NodeList=new