南京邮电大学数据结构A第5章.ppt

5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.3 优先权队列类 templateclass T class PrioQueue { public: PrioQueue(int mSize=20); ~PrioQueue(){delete[] q;}; bool IsEmpty() const{return n==0;} bool IsFull() const{return n==maxSize;} void Append(const T x); void Serve(T x); //获取优先权最高的元素（即堆顶元素） private: void AdjustDown (int r, int j); //向下调整 void AdjustUp (int j); //向上调整 T*q; int n,maxSize; }; 5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.3 优先权队列类 template class T PrioQueueT::PrioQueue(int mSize) { maxSize=mSize; n=0; q=new T[maxSize]; } 5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.4 实现优先权队列 void AdjustUp (int j) 设（q[0],…,q[j-1]）这j位置上的元素已满足特性：q[i]?q[2i+1] 且q[i]?q[2i+2] (i=0,1,?,?(j-2)/2?)，运行此函数将使得增加一个元素q[j]，(q[0],q[1],…,q[j]) 这j+1个元素也满足堆的特性。 5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.4 实现优先权队列 template class T void PrioQueueT::AdjustUp (int j) { int i=j;T temp=q[i]; while (i0 tempq[(i-1)/2]){ q[i]=q[(i-1)/2]; i=(i-1)/2; } q[i]=temp; } 5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.4 实现优先权队列 5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.4 实现优先权队列 template class T void PrioQueueT::Append(const T x) { if(IsFull()) { cout “Overflow”; return; } q[n++]=x; AdjustUp(n-1); } 5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.4 实现优先权队列 template class T void PrioQueueT::Serve(T x) { if(IsEmpty()){ cout “Underflow”; return; } x=q[0];q[0]=q[--n]; AdjustDown (0, n-1); } 5.6 堆和优先权队列 5.5.3 树和森林的遍历 5.6.4 实现优先权队列 5.7 哈夫曼树和哈夫曼编码 5.5.3 树和森林的遍历 本节将讨论： 树的路径长度 哈夫曼树和哈夫曼算法 课堂提要 第5章 树 5.1 树的基本概念 5.2 二叉树 5.3 二叉树的遍历 5.5 树和森林 5.7 哈夫曼树和哈 夫曼编码 5.7 哈夫曼树和哈夫曼编码 5.7.1 树的路径长度 定义5.7 从根到树中任意结点的路径长度是指从根结点到该结点的路径上所包括的边的数目。 树的内路径长度定义为除叶子结点外，从根到树中其他所有结点的路径长度之和。 树的外路径长度是指从根到树中所有叶子结点的路径长度之和。 5.7 哈夫曼树和哈夫曼编码 5.7.1 树的路径长度 定理5.1 设I和E分别是一棵扩充二叉树的内路径长度和外路径长度，n是树中非叶结点的数目，则E=I+2n。 证明：归纳法，设扩充二叉树中，非叶子结点个数为n (1) n=1时，E1 = 2, I1 = 0, E1 = I1 + 2满足 (2)设n-1时满足等式En-1 = In-1 + 2(n-1) v v 得到： In-1 = In – k En-1 = En –2