第5章二叉树

第 5 章二叉树 5.1 二叉树的概念 5.2 二叉树的周游 5.3 二叉树的存储结构 5.4 二叉搜索树 5.5 堆 5.6 Huffman 编码树 5.1 二叉树的概念 5.1.1 二叉树的定义及相关概念 5.1.2 满二叉树 完全二叉树 扩充二叉树 5.1.3 二叉树的主要性质 1 2 5.1.1 二叉树的定义和基本术语 二叉树的五种基本形态 二叉树由结点的有限集合构成 这个有限集合 或者为空集 ; 或者由一个根结点及两棵互不相 交的分别称为左子树 右子树的二叉树组成 这是一个递归定义 二叉树可以是空集合, 因 空二叉树 左右为空 左非空 右非空 左右都不空 此根可以有空的左子树或右子树, 或者左右子 树皆为空 3 4 5.1.2 满二叉树 完全二叉树 扩充二叉树 如果一棵二叉树的任何结点, 或者是树叶, 或者恰有两棵非空子树, 则此二叉树称作满二叉树 完全二叉树如果一棵二叉树最多只有最下面的两层结点度数可以小于 2; 最下面一层的结点都集中在该层最左边的位置上, 则称此二叉树为完全二叉树 5 6 1

扩充二叉树 扩充二叉树 当二叉树里出现空的子树时, 就增加新的 特殊的结点 空树叶 对于原来二叉树里度数为 1 的分支结点, 在它下面增加一个空树叶 对于原来二叉树的树叶, 在它下面增加两个空树叶扩充的二叉树是满二叉树, 新增加的空树叶 ( 外部结点 ) 的个数等于原来二叉树的结点 ( 内部结点 ) 个数加 1 7 8 扩充二叉树 外部路径长度 E 从扩充的二叉树的根到每个外部结点的路径长度之和 内部路径长度 I 扩充的二叉树里从根到每个内部结点的路径长度之和 E 和 I 两个量之间的关系为 E=I+2n 5.1.3 二叉树的主要性质 1. 满二叉树定理 : 非空满二叉树的树叶结点数量等于其分支结点数量加 1 证明 : 设二叉树结点总数为 n, 叶结点数为 m, 分支结点数为 b n = m + b ( 公式 1) 每个分支结点恰有两个子结点, 故有 2*b 条边 ; 一棵二叉树, 除根结点外, 每个结点都恰有一条边联接父结点, 故共有 n-1 条边 即 n - 1 = 2b ( 公式 2) 由 ( 公式 1),( 公式 2) 得 n-1=m+b-1 = 2b, 得出 m = b + 1 9 10 2. 满二叉树定理推论 : 一个非空二叉树的空子树 ( 指针 ) 数目等于其结点数加 1 证明 : 设二叉树 T, 将其所有空子树换为树叶, 记 新的扩充满二叉树为 T 所有原来 T 的结点现在是 T 的分支结点 根据满二叉树定理, 新添加的树 叶数目等于 T 结点个数加 1, 而每个新添加的树叶 对应 T 的一个空子树 因此 T 中空子树数目等于 T 中结点数加 1 3. 任何一棵二叉树, 度为 0 的结点比度为 2 的结点多一个 n 0 = n 2 + 1 证明 : 设有 n 个结点的二叉树度为 0 1 2 的结点数分别为 =n 0,n 1,n 2, 则 n = n 0 + n 1 + n 2 ( 公式 3) 设边数为 e 因为除根以外, 每个结点都有一条边进入, 故 n = e + 1 由于这些边是有度为 1 和 2 的的结点射出的, 因此 e = n 1 + 2 n 2, 于是 n = e + 1= n 1 + 2 n 2 + 1 ( 公式 4) 因此由 ( 公式 3)( 公式 4) 得 n 0 + n 1 + n 2 = n 1 + 2 n 2 + 1 即 n 0 = n 2 + 1 11 12 2

4. 二叉树的第 i 层 ( 根为第 0 层,i 0) 最多有 2 i 个结点 证明 :( 数学归纳法 ) i=0, 只有根结点, 2 0 =1 成立假设 0 j<i,2 j 成立, 当 j+1,2 j *2=2 j+1 则第 j 层至多有 2 j+1 二叉树的高度定义为二叉树中层数最大的叶结点的层数加 1 二叉树的深度定义为二叉树中层数最大的叶结点的层数 13 14 5. 深度为 k 的二叉树至多有 2 k+1-1 个结点 证明 : 利用性质 4 2 0 +2 1 +2 2 +2 3 +...+2 k =2 k+1-1 6. 有 n 个结点 (n>0) 的完全二叉树的高度为 log 2 (n+1), 深度为 log 2 (n+1) -1 证明 : 设高度为 k, 则有 : 2 k-1-1<n<=2 k -1 2 k-1 <=n<2 k k-1<=log 2 n<k 因为 k 是整数, 所以 k= log 2 (n+1) 15 16 7. 对于具有 n 个结点的完全二叉树, 结点按层次由左到右编号, 则有 : (1) 如果 i=0 为根结点 ; 如果 i>0, 其父结点编号是 (i-1)/2. (2) 当 2i+1<n, 结点的左子结点是 2i+1; 否则没有左子结点 (3) 当 2i+2<n, 结点的右子结点是 2i+2; 否则 i 没有右子结点 5.2 二叉树的周游 5.2.1 二叉树的抽象数据类型 5.2.2 深度周游二叉树 5.2.3 广度周游二叉树 17 18 3

5.2.1 二叉树的抽象数据类型 T value() const; 二叉树结点 二叉树的操作 : 整棵二叉树的运算 初始化二叉树 合并两棵二叉树 二叉树的结点运算 访问结点的左 / 右子结点 父结点 访问结点存储的数据 class BinaryTreeNode { friend class BinaryTree<T>; private: T info; BinaryTreeNode *leftchild,*rightchild; public: BinaryTreeNode(); BinaryTreeNode(const T& ele); BinaryTreeNode(const T& ele, BinaryTreeNode<T>* l, BinaryTreeNode<T>* leftchild() const; BinaryTreeNode<T>* rightchild() const; void setleftchild(bianrytreenode<t>*); void setrightchild(binarytreenode<t>*); void setvalue(const T& val); bool isleft() const; BinaryTreeNode<T>& operator= (const BianryTreeNode<T>& Node); BinaryTreeNode<T> *r); 19 20 class BinaryTree { 二叉树 private: BinaryTreeNode<T> * root; public: BinaryTree(){ root = NUL; ~BinaryTree() { DeleteBinaryTree(root); bool isempty() const; BinaryTreeNode<T>* Root(){ return root; BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current); BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T>* current); BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T>* current); void CreateTree(const T& info, BinaryTree<T>& lefttree, BinaryTree<T>& righttree); void PreOrder(BinaryTreeNode<T>* root); void InOrder(BinaryTreeNode<T>* root); void PostOrder(BinaryTreeNode<T>* root); void LevelOrder(BinaryTreeNode<T>* root); void DeleteBinaryTree(BinaryTreeNode<T>* root); 21 5.2.2 深度优先周游二叉树 所谓周游是指系统地访问数据结构中的每个结点一次且仅一次 周游一棵二叉树的过程就是将二叉树的结点放入一个线性序列的过程, 即将二叉树线性化 22 深度优先周游二叉树 可以有下列三种周游顺序 : 1 前序周游 (tlr 次序 ): 访问根结点 ; 前序周游左子树 ; 前序周游右子树 2 中序周游 (LtR 次序 ): 中序周游左子树 ; 访问根结点 ; 中序周游右子树 3 后序周游 (LRt 次序 ): 后序周游左子树 ; 后序周游右子树 ; 访问根结点 深度优先周游二叉树 1 前序周游 : ABDCEGFHI 2 中序周游 : DBAEGCHFI 3 后序周游 : DBGEHIFCA 23 24 4

前序周游二叉树 ( 递归实现 ) void BinaryTree<T>::PreOrder( BinaryTreeNode<T>* root ){ if ( root!= NULL) { Visit(root->value()); // 访问根结点 PreOrder(root->leftchild()); // 前序周游左子树 PreOrder(root->rightchild()); // 前序周游右子树 中序周游二叉树 ( 递归实现 ) void BinaryTree<T>::InOrder(BinaryTreeNode<T>* root) { if ( root!= NULL) { InOrder(root->leftchild()); // 中序周游左子树 Visit(root->value()); // 访问根结点 InOrder(root->rightchild()); // 中序周游右子树 25 26 后序周游二叉树 ( 递归实现 ) void BinaryTree<T>::PostOrder(BinaryTreeNode<T>* root) { if( root!= NULL) { PostOrder(root->leftchild()); // 后序周游左子树 PostOrder(root->rightchild()); // 后序周游右子树 Visit(root->value()); // 访问根结点 非递归深度优先周游二叉树将递归转换为非递归需要借用栈模拟执行递归的过程 即利用一个栈记录尚未周游的结点或子树, 以备以后访问 27 28 前序周游二叉树算法 ( 非递归 ) pointer = root; a 空指针入栈 ; while ( pointer 非空 ){ b Visit(pointer); if (pointer 有右结点 ) 右结点入栈 ; c d if (pointer 有左结点 ) 左结点入栈 ; e 退栈 ; g f h 前序周游二叉树 ( 非递归 ) void BinaryTree<T>::PreOrderWithoutRecursion(BinaryTreeNode<T>* root) { using std::stack; stack<binarytreenode<t>*> astack; BinaryTreeNode<T> * pointer = root; astack.push(null); while (pointer) { Visit(pointer->value()); if (pointer->rightchild()!= NULL) astack.push(pointer->rightchild()); if (pointer->leftchild()!= NULL) astack.push(pointer->leftchild()); pointer=astack.top(); astack.pop(); 29 30 5

中序周游二叉树算法 ( 非递归 ) pointer = root; while ( 栈非空 pointer 非空 ) { if (pointer 非空 ) { 入栈 ;pointer 指向左结点 ; else { pointer = 退栈 ; Visit(pointer); Pointer 指向右结点 ; c b e d g a f h 中序周游二叉树 ( 非递归 ) void BinaryTree<T>::InOrderWithoutRecursion(BinaryTreeNode<T>* root) { using std::stack; stack<binarytreenode<t>*> astack; BinaryTreeNode<T> * pointer = root; while (!astack.empty() pointer) { if (pointer) { astack.push(pointer); pointer = pointer->leftchild(); else { pointer = astack.top(); astack.pop(); Visit(pointer->value()); pointer = pointer->rightchild(); 31 32 后序周游二叉树算法 ( 非递归 ) pointer = root; while ( 栈非空 pointer 非空 ) { while (pointer 非空 ) { 入栈 ;pointer 指向左结点 ; pointer = 退栈 ; if ( 标志为左 ){ 换右标志入栈 ; pointer 指向右结点 ; else { Visit(pointer); pointer = NULL; c b e d g a f h 33 后序周游二叉树 ( 非递归 ) // 栈元素的定义 enum Tags{ Left, Right ; class StackElement { public: BinaryTreeNode<T> * pointer; Tags tag; ; 34 后序周游二叉树 ( 非递归 ) void BinaryTree<T>::PostOrderWithoutRecursion(BinaryTreeNode<T>* root) { using std::stack; StackElement<T> element; stack<binarytreenode<t>> astack; BinaryTreeNode<T> * pointer = root; astack.push(null); while (!astack.empty() pointer) { while ( pointer) { 入栈 ;pointer 指向左结点 ; element = astack.top(); astack.pop(); if (element.tag == Left) { 换右标志入栈 ; pointer 指向右结点 ; else { Visit(pointer->value()); pointer = NULL; element.pointer = pointer; element.tag=left; astack.push(element); pointer=pointer->leftchild(); element.tag=right; astack.push(element); pointer=pointer->rgihtchild(); 5.2.3 广度优先周游二叉树 从二叉树的顶层 ( 根结点 ) 开始, 自上至下逐层遍历 ; 在同一层中, 按照从左到右的顺序对结点逐一访问 例如 :ABCDEFGHI 35 36 6

广度优先周游二叉树算法 pointer = root; if (pointer) 入队 ; while ( 队非空 ) { pointer = 出队 ; Visit(pointer); if (pointer 左结点非空 ) 左结点入队 ; if (pointer 右结点非空 ) 右结点入队 ; 37 广度优先周游二叉树 void BinaryTree<T>::LevelOrder(BinaryTreeNode<T>* root) { using::queue; queue<binarytreenode<t> *> aqueue; BinaryTreeNode<T> *pointer=root; if (pointer) aqueue.push(pointer); while (!aquene.empty()) { pointer = aqueue.front(); aqueue.pop(); Visit(pointer->value()); if (pointer->leftchild()) aqueue.push(pointer->leftchild()); if (pointer->rightchild()) aqueue.push(pointer->rightchild()); 38 5.3 二叉树的存储结构 5.3.1 二叉树的链式存储结构 5.3.2 完全二叉树的顺序存储结构 5.3.1 二叉树的链式存储结构 二叉树是非线性的树形结构, 在存储器里表示树形结构的最自然方法是链接方法 在每个结点中除存储结点本身的数据外再设置两个指针字段 llink 和 rlink, 分别指向结点的左子女和右子女 当结点的某个子女为空时, 则相应的指针为空指针 结点的形式为 llink info rlink llink info parent rlink 39 40 用链式存储结构表示二叉树 用二叉链表实现二叉树的定义 private: // 二叉树结点的数据域 T info; // 二叉树结点指向左子树的指针 BinaryTreeNode<T>* leftchild; // 二叉树结点指向左子树的指针 BinaryTreeNode<T>* rightchild; 41 42 7

BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *current) { pointer = root; if ( 树非空 && current 非空 ) { a while ( 栈非空 pointer 非空 ) { if (pointer 非空 ) { if (current 是 pointer 的左结点或右结点 ) return pointer; // 找到 current 的父结点 b h 将 pointer 入栈 ; pointer = pointer->leftchild(); // 向左走 c d else { pointer= 出栈 ; e f pointer=pointer->rightchild(); // 向右走 g 返回 current 的父结点 BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *current) { using std::stack; stack<binarytreenode<t> *> astack; BinaryTreeNode<T> *pointer=root; if (root && current) { while (!astack.empty() pointer) { if (pointer) { if (current == pointer->leftchild() current == pointer->rightchild()) return pointer; astack.push(pointer); pointer=pointer->leftchild(); else { pointer=astack.top(); astack.pop(); pointer=pointer->rightchild(); 返回 current 的父结点 43 44 void BinaryTree<T>::CreateTree(const T& info, 创建二叉树 BinaryTree<T>& lefttree, BinaryTree<T>& righttree) { root=new BinaryTreeNode<T>(info,leftTree.root,rightTree.root); lefttree.root = righttree.root = NULL; lefttree 和 righttree 是两棵已有的二叉树 将原子树的根设置为 NULL 是为了避免非法访问子树 删除二叉树 void BinaryTree<T>::DeleteBinaryTree( BinaryTreeNode<T>* root) { if (root!= NULL) { // 当树不空 DeleteBinaryTree(root->left); // 删除左子树 a DeleteBinaryTree(root->right); // 删除右子树 b c delete root; d 45 46 5.3.2 完全二叉树的顺序存储结构 当需要二叉树紧凑存储, 并且在处理过程中, 二叉树结构的大小和形状不发生动态变化时, 可以采用顺序的方法存储 用顺序存储结构表示完全二叉树 按层次顺序将一棵有 n 个结点的完全二叉树的所有结点从 0 到 n-1 编号, 就得到结点的一个线性序列 用顺序法存储二叉树, 就是要把所有结 点按照一定的次序顺序存储到一片连续 的存储单元中 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6 7 8 47 48 8

完全二叉树的下标公式 完全二叉树中除最下面一层外, 各层都被结点充满了, 每一层结点个数恰是上一层结点个数的两倍 因此, 从一个结点的编号就可以推知它的父母, 左 右子女, 兄弟等结点的编号 当 2i+1<n 时, 结点 i 的左子女是结点 2i+1, 否则结点 i 没有左子女 当 2i+2<n 时, 结点 i 的右子女是结点 2i+2, 否则结点 i 没有右子女 5.4 二叉搜索树 二叉搜索树 (BST) 或者是一棵空树 ; 或者是具有下列性质的二叉树 : 对于任何一个结点, 设其值为 K, 则该结点的左子树 ( 若不空 ) 的所有结点的值都小于 K; 右子树 ( 若不空 ) 的所有结点的值都大于或等于 K; 而且它的左右子树也分别为二叉搜索树 二叉搜索树的性质 : 按照中序周游将各结点打印出来, 将得到按照由小到大的排列 49 50 二叉搜索树 50 30 80 20 40 90 32 35 85 88 中序序列 :20,30,32,35,40,50,80,85,88,90 二叉搜索树 二叉搜索树的搜索过程 : 从根结点开始, 在二叉搜索树中检索值 K 如果根结点储存的值为 K, 则检索结束 如果 K 小于根结点的值, 则只需检索左子树 如果 K 大于根结点的值, 就只检索右子树 这个过程一直持续到找到 K 或者遇上叶子结点 如果遇上叶子结点仍没有发现 K, 就不存在 51 52 二叉搜索树的插入 向二叉搜索树里插入新结点, 要保证插入后仍符合二叉搜索树的定义 插入过程为 : 用待插入结点与树根比较, 若待插入的关键值小于树根的关键值, 就进入左子树, 否则进入右子树 在子树里又与子树根比较, 如此下去, 直到将新结点插入到二叉树的叶子结点位置 二叉搜索树的插入 void BinarySearchTree<T>::InsertNode(root, newpointer) { pointer=root; while ( pointer 非空 ) { if ( newpointer->value() == pointer->value() ) return ; // 比较 else if ( newpointer->value() < pointer->value() ) { if ( pointer 左为空 ) { 插在左子树 ; return; 50 else 往左走 ; 30 80 else{ if ( pointer 右为空 ) { 20 40 90 插在右子树 ; return; 35 85 else 往右走 ; 32 88 53 54 9

二叉搜索树的插入 void BinarySearchTree<T>::InsertNode( BinaryTreeNode<T>* root, BinaryTreeNode<T>* newpointer) { BinaryTreeNode<T>* pointer=null; if (root==null) { Initialize(newpointer); return; else pointer=root; while (pointer!= NULL) { if ( newpointer->value() == pointer->value() ) return ; else if (newpointer->value() < pointer->value() ) { if ( pointer->leftchild() == NULL) { pointer->left=newpointer; return; 50 else pointer = pointer->leftchild(); 30 80 20 40 90 else{ if ( pointer->rightchild() == NULL) { pointer->right=newpointer; return; 35 85 else pointer = pointer->rightchild(); 32 88 创建二叉搜索树 对于给定的关键码集合, 为建立二叉搜索树, 可以从一个空的二叉搜索树开始, 将关键码一个个插进去 将关键码集合组织成二叉搜索树, 起到了对集合里的关键码进行排序的作用, 按中序周游二叉搜索树, 就能得到排好的关键码序列 55 56 二叉搜索树的删除 在二叉搜索树里删除结点时, 不是把以这个结点为根的子树都删除掉, 只是删除一个结点, 并且还要保持二叉搜索树的性质 设 p,p1,r 是指针变量,p 指向要删除的结点, p1 指向 p 的父结点, 删除过程分为两种情况 : 没有左子树 有左子树 没有左子树 若结点 p 没有左子树, 则用右子树的根代替被删除的结点 p 50 30 80 20 40 90 32 35 85 88 20 32 30 35 40 50 85 90 88 57 58 有左子树若 p 有左子树, 则在左子树里找中序周游的最后一个结点 r, 将 r 的右指针置成指向 p 的右子树的根, 用结点 p 的左子树的根去代替被删除的结点 p 50 30 80 20 40 90 32 35 85 88 20 32 30 35 40 80 85 90 88 5.5 堆与优先队列 最小值堆 : 最小值堆是一个关键码序列 {K 0,K 1, K n-1, 它具有如下特性 : K i K 2i+1 (i=0,1,, n/2-1) K i K 2i 十 2 例如 :(05,23,16,68,73,72,71,94) 类似可以定义最大值堆 59 60 10

堆的性质 堆是一个完全二叉树, 可以用数组表示 堆中存储的数据局部有序 父与子之间的值存在某种联系 兄弟之间没有必然联系 (05,23,16,68,73,72,71,94) 61 62 class MinHeap { private: T* heaparray; // 存放堆数据的数组 int CurrentSize; // 当前堆中元素数目 int MaxSize; // 堆所能容纳的最大元素数目 void BuildHeap(); // 建堆 public: MinHeap(const int n); virtual ~MinHeap(){delete []heaparray;; bool isleaf(int pos) const; int leftchild(int pos) const; int rightchild(int pos) const; int parent(int pos) const; bool Remove(int pos, T& node); bool Insert(const T& newnode); T& RemoveMin(); void SiftUp(int position); void SiftDown(int left); 堆的类定义 建堆过程 假设根的左 右子树都已是堆, 并且根的元素名为 R 有两种可能 : (1) R 的值小于或等于其两个子女, 此时堆已完成 ; (2) R 的值大于其某一个或全部两个子女的值, 此时 R 应与两个子女中值较小的一个交换, 结果得到一个堆, 除非 R 仍然大于其新子女的一个或全部的两个 这种情况下, 只需继续将 R 拉下来 的过程, 直至到达某一层使它小于它的子女, 或者成为叶结点 63 64 65 66 11

template<t> MinHeap<T>::MinHeap(const int n) { if (n<=0) return; CurrentSize = 0; MaxSize = n; // 初始化堆容量为 n heaparray = new T[MaxSize]; // 创建堆空间 // 此处进行堆元素的赋值工作 BuildHeap( ); 67 68 bool MinHeap<T>::isLeaf(int pos) const { return (pos>=currentsize/2)&&(pos<currentsize); ========================================== int MinHeap<T>::leftchild(int pos) const { return 2*pos+1 int MinHeap<T>::rightchild(int pos) const { return 2*pos+2; ================================= int MinHeap<T>::parent(int pos) const { return (pos-1)/2; 69 70 void MinHeap<T>::SiftDown(int position) { int i=position; // 标识父结点 int j=2*i+1; // 标识关键值较小的子结点 筛选法 建初堆 从第一个有子女的结点 heaparray[currentsize/2-1] T temp=heaparray[i]; // 保存父结点 while(j<currentsize){ // 过筛 if ((j<currentsize-1) && (heaparray[j]>heaparray[j+1])) j++; //j 指向数值较小的子结点 if(temp>heaparray[j]) { heaparray[i]=heaparray[j]; i=j; j=2*j+1; // 向下继续 //end if i else break; //end if j heaparray[i]=temp; 开始, 自底向上逐步将以各结点为根的子树调整成堆 void MinHeap<T>::BuildHeap() { // 反复调用筛选函数, for (int i=currentsize/2-1; i>=0; i--) SiftDown(i); 71 72 12

插入新元素 bool MinHeap<T>::Insert(const T& newnode){ // 向堆中插入新元素 newnode if (CurrentSize == MaxSize) // 堆空间已经满 return false; heaparray[currentsize] = new Node(); SiftUp(CurrentSize); // 向上调整 CurrentSize++; 向上筛选调整堆 void MinHeap<T>::SiftUp(int position) { // 从 position 开始调整, 使序列成为堆 int temppos = position; T temp = heaparray[temppos]; while((temppos>0)&&(heaparray[parent(temppos)]>temp)) { heaparray[temppos] = heaparray[parent(temppos)]; temppos = parent(temppos); heaparray[temppos] = temp; 73 74 移出最小值 ( 优先队列出队 ) template<t> T& MinHeap<T>::RemoveMin( ) { if(currentsize==0) { cout<<"can't Delete"; exit(1); else { swap(0,--currentsize); if (CurrentSize>1) SiftDown(0); return heapsize[currentsize]; 删除元素 bool MinHeap<T>::Remove(int pos, T& node) { if((pos<0) (pos>=currentsize)) return false; node = heaparray[pos]; heaparray[pos]=heaparray[--currentsize]; if (heaparray[parent(pos)] > heaparray[pos] ) SiftUp(pos); else SiftDown(pos); return true; 75 76 建堆效率 由于堆有logn 层深, 插入结点 删除普通元素和删除最小元素的平均时间代价和最差时间代价都是 ( logn) 建堆的时间复杂度为 (nlogn) 优先队列 优先队列是一种有用的数据结构 它是 0 个或多个元素的集合 每个元素有一个关键码值, 主要操作有查找 插入和删除 优先队列的特点 : 支持从一个集合中快速查找并移出具有最大值或最小值的元素 最小优先队列适于查找与删除最小元素 ; 最大优先队列适于查找与删除最大元素 77 78 13

优先队列的实现 采用无序线性表或有序线性表缺点 : 效率慢 采用堆是一种较好的方案 5.6 Huffman 树及其应用 要求给出一个具有 n 个外部结点的扩充二叉树 该二叉树每个外部结点 K i 有一个 w i 与之对应, 作为该外部结点的权 这个扩充二叉树的叶结点带权外部路径长度总和最小 n 1 wl i i i 0 权越大的叶结点离根越近 ; 如果某个叶的权较小, 可能就会离根较远 79 80 建立 Huffman 编码树 首先, 按照 权 将字母排为一列 然后, 拿走前两个字母 ( 权 最小的两个字母 ), 再将它们标记为 Huffman 树的树叶, 将这两个树叶标为一个分支结点的两个子女, 而该结点的权即为两树叶的权之和 将所得 权 放回序列中, 使 权 的顺序保持 重复上述步骤直至序列中只剩一个元素, 则 Huffman 树建立完毕 81 82 前缀编码 在编码集合中, 任何字符的编码都不是另外一个字符编码的前缀, 这种编码叫作前缀编码 这种前缀特性保证了代码串被反编码时, 不会有多 种可能 例如, 对于上面 8 个字符, 编码为 Z(111100), K(111101), F(11111), C(1110), U(100), D(101), L(110), E(0) 这是一种前缀编码, 对于代码 000110, 可以翻译出唯 一的字符串 EEEL 83 84 14

Huffman 编码树的应用 设 D={d 0,,d n-1, W={W 0,,W n-1 D 为需要编码的字符集合,W 为 D 中各字符出现的频率, 要对 D 里的字符进行二进制编码, 使得 : 通信编码总长最短 若 d i d j, 则 d i 的编码不可能是 d j 的编码的开始部分 ( 前缀 ) Huffman 编码树的应用 利用 Huffman 编码 : 用 d 0,d 1,,d n-1 作外部结点,W 0,W 1,,W n-1 作外部结点的权, 构造具有最小带权外部路径长度的扩充二叉树 把从每个结点引向其左子女的边标上号码 0, 把从每个结点引向其右子女的边标上号码 1 从根到每个叶子的路径上的号码连接起来就是这个叶子代表的字符的编码 85 86 各字符的二进制编码为 : d 0 :1011110 d 1 :1011111 d 2 :101110 d 3 :10110 d 4 :0100 d 5 :010l d 6 :1010 d 7 :000 d 8 : 001 d 9 :011 d 10 :100 d 11 :110 d 12 :111 出现频率越大的字符其编码越短 87 88 Huffman 编码树的应用 用 Huffman 算法构造出的扩充二叉树给出了各字符的编码, 同时也用来译码 从二叉树的根开始, 用需要译码的二进制位串中的若干个相邻位与二叉树边上标的 0,1 相匹配, 确定一条到达树叶的路径 一旦到达树叶, 则译出了一个字符, 再回到树根, 从二进制位串中的下一位开始继续译码 class HuffmanTree { private: public: HuffmanTreeNode<T>* root; Huffman 树类 void MergeTree(HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T>* parent); void DeleteTree(HuffmanTreeNode<T>* root); HuffmanTree(T weight[],int n); virtual ~HuffmanTree(){DeleteTree(root);; 89 90 15

Huffman 树的构造 HuffmanTree<T>::HuffmanTree(T weight[], int n) { MinHeap<HuffmanTreeNode<T>> heap(n); HuffmanTreeNode<T> *parent,&firstchild,&secondchild; HuffmanTreeNode<T>* NodeList=new HuffmanTreeNode<T>[n]; for(int i=0;i<n;i++){ NodeList[i].element=weight[i]; NodeList[i].parent=NodeList[i].left=NodeList[i].right=NULL; heap.insert(nodelist[i]); //end for for(i=0;i<n-1;i++) { parent=new HuffmanTreeNode<T>; firstchild=heap.removemin(); secondchild=heap.removemin(); MergeTree(firstchild,secondchild,parent); heap.insert(*parent); root=parent; delete []NodeList; 本章作业 教材 P132 4,6,13,14,16,18,19 91 92 本章上机作业 教材 P133-P134 第 1 题 :2 第 2 题 :4 93 16