沈俊 第6章 树和森林.pptVIP

第六章 树和森林 上海大学计算机学院 沈 俊 树的概念 例如：对于一段电文：AADDBCAAABDDCADAAADDCDDBAACCA。其字符集合为：{A、B、C、D}，各个字符出现的频率(次数)是 W＝{12、3、5、9}。若给每个字符以等长编码：A(00)、B(10)、C(01)、D(11)。则电文代码的长度为：(12+3+5+9)*2=58。 若按各个字符出现的频率不同而给予不等长编码，可望减少电文代码的长度。因各字符出现的频率为{12/29、3/29、5/29、9/29}，化成整数为{12、3、5、9}，以它们为各叶结点上的权值，建立哈夫曼树，如图6-23所示，得哈夫曼编码为：A(0)、B(100)、C(101)、D(11)。它的总代码长度：12*1+(3+5)*2+9*3=54，正好等于哈夫曼树的带权路径长度WPL，显然比等长编码的代码长度要短。哈夫曼编码是一种前缀编码，解码时不会混淆。 3．构造哈夫曼树和哈夫曼编码的算法 哈夫曼树的类定义： const int MaxSize=20 //设定字符数目的最大值 template class Type class HuaffmanTree; template class Type class HuaffmanTreeNode { friend class HuaffmanTree; private: Type data; //数据元素 HuaffmanTreeNode Type *leftChild, *rightChild, *parent; //指向左右孩子及双亲的指针 }; 中序线索二叉树 : 下面以中序线索二义树为例，讨论线索二叉树的建立、线索二叉树的遍历以及在线索二叉树中查找前驱结点、查找后继结点、插入结点和删除结点等操作的实现算法。 1．建立中序线索二叉树 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历的过程中检查当前结点的左、右指针域是否为空。如果为空，将它们改为指向前驱结点或后继结点的线索。另外，在对一棵二叉树加线索时，必须首先申请一个头结点，并使头结点的leftchild指向二叉树的根结点。对二叉树线索化后，还须建立最后一个结点到头结点的线索；并使头结点的rightchild指向第一个结点。 template class Type void ThreadBinTreeType :: InThread ( ThreadBinTreeNodeType *r, ThreadBinTreeNodeType *pre ) { //利用中序遍历线索化以r为根的二叉树，pre为中序序历中第一个结点的前驱 if ( r != NULL ) { InThread ( r→GetLeftChild( ), pre ); //中序线索化r的左子树 if ( r→GetLeftChild( ) == NULL ) { r→SetLeftChild( pre ); r→leftTag = 1; } //建立前驱线索 if ( pre→GetRightChild( ) == NULL ) { pre→SetRightChild( r ); pre→rightTag = 1; } //建立后继线索 pre = r; InThread ( r→GetRightChild( ), pre ); //中序线索化r的右子树 } } template class Type void ThreadBinTreeType:: CreateInThread ( ) { //建立中序线索二叉树 ThreadBinTreeNodeType *pre; root = new ThreadBinTreeNodeType; //建立头结点 root→leftTag= 1; root→rightTag = 1; if ( this == NULL ) { root→SetLeftChild( root ); root→SetRightChild( root );} //二叉树为空树 else { current = = this; root→SetLeftChild( this ); root→leftThread = 0; pre = root; InThread ( current, pre ); //中序线索化 pre→SetRightChild( root ); //最后一个结