严蔚敏数据结构 (11).ppt

第6章树和二叉树（Tree&BinaryTree）6.5Huffman树及其应用树的带权路径长度如何计算？一、Huffman树（最优二叉树）1.构造Huffman树的基本思想：2.构造Huffman树的步骤（即Huffman算法）：step1：对权值进行合并、删除与替换
——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权二、Huffman编码本节重点：如何编程实现Huffman编码？Huffman编码举例对应的哈夫曼编码：另一种表示
：自己上机练习说明：设字符集为26个英文字母，其出现频度如下表所示。typedefstruct{
unsignedintweight；//权值分量（可放大取整）
unsignedintparent，lchild，rchild；//双亲和孩子分量
}HTNode，*HuffmanTree；//用动态数组存储Huffman树
typedefchar**HuffmanCode；//动态数组存储Huffman编码表Huffman编码的实现：sizeof()可以对变量或变量类型运算,sizeof(char*)是一个char型指针的空间大小,如定义char*p,那么sizeof(p)就是结果,和sizeof(char*)等价。附：二叉树若干典型算法（习题）4例2.如何按层次输出二叉树中所有结点？
算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，此时绝不能用递归算法。
技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈(迭代方式)。可直接用while语句和push/pop操作。参见教材P130-131程序。VoidABC(Bitreep,intl,int&h)
{ifp≠NILthen
{l=l+1;
ifl>hthenh=l;
ABC(p->Lchild,l,h);
ABC(p->Rchild,l,h);
}
}intBTreeDepth(Btree*BT)//*BT为二叉树某结点的指针
{intleftdep,rightdep;//设左右两个深度/层次计数器
if(BT==NULL)return(0);//当前结点指针为空则立即返回
else
{leftdep=BTreeDepth(BT->left);//遍历当前结点左子树
rightdep=BTreeDepth(BT->right);//遍历当前结点右子树
if(leftdep>rightdep)return(leftdep+1);//从叶子起计数
elsereturn(rightdep+1);
}
}//BTreeDepthvoidLayerOrder(BitreeT)//层序遍历二叉树
{InitQueue(Q);//建一个空队（初始化队列）
EnQueue(Q,T);//将一个结点插入队尾的函数
while(!QueueEmpty(Q))
{DeQueue(Q,&p);//队首结点出队(送入p)
visit(p);
if(p->lchild)EnQueue(Q,p->lchild);//p的左孩子入队
if(p->rchild)EnQueue(Q,p->rchild);//p的右孩子入队
}
}//LayerOrder附3：判别给定二叉树是否为完全二叉树严题集6.49④StatusInOrderTrav(BiTreeT,Status(*Visit)(TElemTypee))
{//此处Visit意思是对元素e的一种操作
InitStack（S）；p=T;//初始化栈
while(p||!StackEmpty(S))//树不空或栈不空则开始遍历
{if(p){Push(S,p);p=p->lchild;}//根指针进栈，遍历左子树
else{
Pop(S,p)；//根指针退栈
if(!Visit(p->data))returnERROR;//访问根结点
p=p->rchild;//遍历右子树
}//else
}//while
returnOK;
}//InOrderTrav本章小结