数据结构第二部分.ppt

《数据结构第二部分.ppt》由会员分享，可在线阅读，更多相关《数据结构第二部分.ppt（260页珍藏版）》请在三一办公上搜索。

1、1,第二部分 树,树形结构式处理具有层次关系的数据元素这部分将介绍树二叉树堆,2,第五章 树,树的概念二叉树表达式树哈夫曼树与哈夫曼编码树和森林,3,树的概念,树的定义树的术语树的运算,4,树的定义,树是n(n1)个结点的有限集合T，并且满足：,(1)有一个被称之为根(root)的结点,(2)其余的结点可分为m(m0)个互不相交的集合Tl，T2，Tm，这些集合本身也是一棵树，并称它们为根结点的子树(Subree)。每棵子树同样有自己的根结点。,5,树的概念,树的定义树的术语树的运算,6,根结点、叶结点、内部节点结点的度和树的度儿子结点父亲结点兄弟结点祖先结点子孙结点结点所处层次树的高度,有序树

2、无序树森林,树的术语,7,树的概念,树的定义树的术语树的运算,8,树的常用操作,建树create()：创建一棵空树；清空clear()：删除树中的所有结点；判空IsEmpty()：判别是否为空树；找根结点root()：找出树的根结点。如果树是空树，则返回一个特殊的标记；找父结点parent(x)：找出结点x的父结点；找子结点child(x,i)：找结点x的第i个子结点；剪枝delete(x,i)：删除结点x的第i棵子树；构建一棵树MakeTree（x,T1,T2,Tn）：构建一棵以x为根结点，以T1,T2,Tn为第i棵子树的树；遍历traverse()：访问树上的每一个结点。,9,第五章 树,

3、树的概念二叉树表达式树哈夫曼树与哈夫曼编码树和森林,10,二叉树,二叉树的概念二叉树的性质二叉树的基本运算二叉树的遍历二叉树的实现二叉树类二叉树遍历的非递归实现,11,二叉树的定义,二叉树（Binary Tree）是结点的有限集合，它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又都是二叉树。,注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换一棵二叉树的左右子树后得到的是另一棵二叉树。,12,二叉树的基本形态,(a)空二叉树,(b)根和空的左右子树,(c)根和左右子树,(d)根和左子树,(e)根和右子树,13,结点总数为3 的所有

4、二叉树的不同形状,14,一棵高度为k并具有2k1个结点的二叉树称为满二叉树。一棵二叉树中任意一层的结点个数都达到了最大值,满二叉树,15,满二叉树实例,不是满二叉树,16,完全二叉树,在满二叉树的最底层自右至左依次(注意：不能跳过任何一个结点)去掉若干个结点得到的二叉树也被称之为完全二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。完全二叉树的特点是：（1）所有的叶结点都出现在最低的两层上。（2）对任一结点，如果其右子树的高度为k，则其左子树的高度为k或k1。,17,完全二叉树,非完全二叉树,18,二叉树,二叉树的概念二叉树的性质二叉树的基本运算二叉树的遍历二叉树的实现二叉树类二

5、叉树遍历的非递归实现,19,二叉树的性质1,一棵非空二叉树的第 i 层上最多有2i-1个结点（i1）。,1层：结点个数 21-1=1个2层：结点个数 22-1=2 个3层：结点个数 23-1=4 个,20,证明：当i=1时，只有一个根结点，2i-1=20=1,命题成立。假定对于所有的j，1jk,命题成立。即第j层上至多有2j-1个结点。由归纳假设可知，第j=k层上至多有2k-1个结点。若要使得第k+1层上结点数为最多，那么，第k层上 的每个结点都必须有二个儿子结点。因此，第k+1层上结点数最多为为第k层上最多结点数 的二倍，即：22k-12k+1-12k。所以，命题成立。,21,二叉树的性质2

6、,一棵高度为k的二叉树，最多具有2k1个结点。,证明：这棵二叉树中的每一层的结点个数必须最多。根据性质1，第i层的结点数最多为等于2i-1，因此结点个数 N 最多为：,22,对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0n21 成立。,二叉树的性质3,23,证明：设n为二叉树的结点总数，n1为二叉树中度数为 1的结点数。二叉树中所有结点均小于或等于2，所以有：n n0 n1 n2 再看二叉树中的树枝(父结点和儿子结点之间的 线段)总数。在二叉树中，除根结点外，其余结点都有唯一 的一个树枝进入本结点。,性质3证明,24,设B为二叉树中的树枝数，那么有下式成立：B n

7、1 这些树枝都是由度为1和度为2的结点发出的，一个度为1的结点发出一个树枝，一个度为2的结点发出两个树枝，所以有：B n12n2 因此，n0n21,25,二叉树的性质4,具有n个结点的完全二叉树的高度 k=log2n+1,证明 根据完全二叉树的定义和性质2可知，高度为k的 完全二叉树的第一层到第k-1层具有最多的结点个 数，总数为 2k-1-1个，第k层至少具有一个结点，至多有2k-1个结点。因此，2k-1 1 n 2k-1 即 2k-1 n 2k 对不等式取对数，有 k-1 log2n k 由于k是整数，所以有：k=log2n 1,26,二叉树的性质5,如果对一棵有n个结点的完全二叉树中的结

8、点按层自上而下（从第1层到第 log2n+1层），每一层按自左至右依次编号。若设根结点的编号为1。则对任一编号为i的结点（1in),有：（1）如果i1，则该结点是二叉树的根结点；如果i1，则其父亲结点的编号为i/2。（2）如果2i n，则编号为i的结点为叶子结点，没有儿子；否则，其左儿子的编号为2i。（3）如果2i+1 n，则编号为i的结点无右儿子；否则，其右儿子的编号为2i+1。,27,28,二叉树,二叉树的概念二叉树的性质二叉树的基本运算二叉树的遍历二叉树的实现二叉树类二叉树遍历的非递归实现,29,二叉树常用操作,建树create()：创建一棵空的二叉树；清空clear()：删除二叉树中的

9、所有结点；判空IsEmpty()：判别二叉树是否为空树；找根结点root()：找出二叉树的根结点。找父结点parent(x)：找出结点x的父结点；找左孩子lchild(x)：找结点x的左孩子结点；找右孩子rchild(x)：找结点x的右孩子结点；删除左子树delLeft(x)：删除结点x的左子树；删除右子树delRight(x)：删除结点x的右子树；构建一棵树MakeTree（x,TL,TR）：构建一棵以x为根结点，以TL，TR为左右子树的二叉树；遍历traverse()：访问二叉树上的每一个结点。,30,二叉树,二叉树的概念二叉树的性质二叉树的基本运算二叉树的遍历二叉树的实现二叉树类二叉树遍

10、历的非递归实现,31,二叉树的遍历,二叉树的遍历讨论的是如何访问到树上的每一个结点在线性表中，我们可以沿着后继链访问到所有结点。而二叉树是有分叉的，因此在分叉处必须确定下一个要访问的节点：是根结点、左结点还是右结点根据不同的选择，有三种遍历的方法：前序、中序和后序,32,前序遍历,如果二叉树为空，则操作为空否则访问根结点前序遍历左子树前序遍历右子树,33,中序遍历,如果二叉树为空，则操作为空否则中序遍历左子树访问根结点中序遍历右子树,34,后序遍历,如果二叉树为空，则操作为空否则后序遍历左子树后序遍历右子树访问根结点,35,前序：A、L、B、E、C、D、W、X,中序：B、L、E、A、C、W、X

11、、D,后序：B、E、L、X、W、D、C、A,36,前序 中序 唯一确定一棵二叉树,前序:A、B、D、E、F、C 中序:D、B、E、F、A、C,前序:B、D、E、F 中序:D、B、E、F,前序:E、F 中序:E、F,37,同理，由二叉树的后序序列和中序序列同样可以唯一地确定一棵二叉树 但是，已知二叉树的前序遍历序列和后序遍历序列却无法确定一棵二叉树。比如：已知一棵二叉树的前序遍历序列为A、B，后序遍历序列为B、A，我们虽然可以很容易地得知结点A为根结点，但是无法确定结点B是结点A的左儿子还是右儿子，因为B无论是结点A的右儿子还是左儿子都是符合已知条件的。,38,二叉树,二叉树的概念二叉树的性质二

12、叉树的基本运算二叉树的遍历二叉树的实现二叉树类二叉树遍历的非递归实现,39,二叉树的实现,顺序实现链接实现,40,完全二叉树的顺序存储,根据编号性质，可以省略左右孩子字段,41,普通二叉树的顺序存储,D,B,A,H,I,将普通的树修补成完全二叉树,42,右单支树的实例,43,顺序实现的特点,存储空间的浪费。一般只用于一些特殊的场合，如静态的并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。,44,二叉树的实现,顺序实现链接实现,45,链接存储结构,标准形式：（二叉链表）,广义标准形式：（三叉链表）,46,标准形式的实例,47,广义标准形式的实例,48,二叉树基本运算的实现,由于二叉树是一个

13、递归的结构，因此二叉树中的许多运算的实现都是基于递归函数。create()：将指向根结点的指针设为空指针就可以了，即root=NULL。isEmpty()：只需要判别root即可。如果root等于空指针，返回true，否则，返回false。root()：返回root指向的结点的数据部分。如果二叉树是空树，则返回一个特殊的标记。,49,clear(),从递归的观点看，一棵二叉树由三部分组成：根结点、左子树、右子树。删除一棵二叉树就是删除这三个部分。根结点的删除很简单，只要回收根结点的空间，把指向根结点的指针设为空指针。如何删除左子树和右子树呢？记住左子树也是一棵二叉树，右子树也是一棵二叉树，左右

14、子树的删除和整棵树的删除过程是一样的。,50,if（左子树非空）递归删除左子树；if（右子树非空）递归删除右子树；delete root指向的结点；root=NULL；,51,parent(x)：在二叉链表的实现中一般不实现这个操作lchild(x)：返回结点x的left值rchild(x)：返回结点x的right值delLeft(x)：对左子树调用clear函数删除左子树，然后将结点x的left置为NULL。delRight(x)：对右子树调用clear函数删除右子树，然后将结点x的right置为NULL。makeTree（x,TL,TR）：为x申请一个结点，让它的left指向TL的根结点，

15、right指向TR的根结点。,52,二叉树的遍历,前序：访问根结点；if（左子树非空）前序遍历左子树；if（右子树非空）前序遍历右子树；其他两种遍历只要调整一下次序即可。,53,二叉树,二叉树的概念二叉树的性质二叉树的基本运算二叉树的遍历二叉树的实现二叉树类二叉树遍历的非递归实现,54,二叉树类,由于二叉树的顺序实现仅用于一些特殊的场合。大多数情况下，二叉树都是用二叉链表实现，所以仅介绍用二叉链表实现的二叉树类。,55,二叉树类的设计,标准的链接存储由两个类组成：结点类和树类。和线性表的实现类似，这个结点类是树类专用的，因此可作为树类的私有内嵌类。,56,结点类Node的设计,存储和处理树上每

16、一个结点的类。数据成员包括：结点的数据及左右孩子的指针。结点的操作包括：构造和析构,57,二叉树类的设计,树的存储：存储指向根结点的指针树的操作：树的标准操作增加了一个建树的函数,58,递归函数的设计,对于二叉树类的用户来说，他并不需要知道这些操作时用递归函数实现的。对用户来说，调用这些函数并不需要参数但递归函数必须有一个控制递归终止的参数设计时，我们将用户需要的函数原型作为公有的成员函数。每个公有成员函数对应一个私有的、带递归参数的成员函数。公有函数调用私有函数完成相应的功能。,59,二叉树类的定义,template class BinaryTree private:struct Node

17、Node*left,*right;/结点的左、右儿子的地址 Type data;/结点的数据信息 Node():left(NULL),right(NULL)Node(Type item,Node*L=NULL,Node*R=NULL):data(item),left(L),right(R)Node();Node*root;/二叉树的根结点。,60,public:BinaryTree():root(NULL)/构造空二叉树BinaryTree(const Type,61,void makeTree(const Type,62,bool isEmpty()const return root=NUL

18、L;void clear()if(root!=NULL)clear(root);root=NULL;int size()const return size(root);int height()const return height(root);void preOrder()const；void postOrder()const；void midOrder()const；void createTree(Type flag);,63,private:void clear(Node*t)；int height(Node*t)const；int size(Node*t)const；void preOr

19、der(Node*t)const；void postOrder(Node*t)const；void midOrder(Node*t)const；;,64,求规模操作的实现,用递归的观点来看，二叉树是由根结点和左右子树构成。因此，树的规模应该为：左子树的规模+右子树的规模+1（根）,65,size(),int size()const return size(root);int size(Node*t)const if(t=NULL)return 0;return 1+size(t-left)+size(t-right);,66,求高度操作的实现,用递归的观点来看，二叉树是由根结点和左右子树构成。

20、因此，树的高度应该为：1max（左子树高度，右子树高度）,67,height(),int height()const return height(root);int height(Node*t)const if(t=NULL)return 0;else int lt=height(t-left),rt=height(t-right);return 1+(lt rt)?lt:rt);,68,三种遍历的实现,树的遍历本身就是用递归形式描述的，因此用递归函数实现是很自然的,69,preOrder(),void preOrder()const if(root!=NULL)cout data left)

21、;preOrder(t-right);,70,midOrder(),void midOrder()const if(root!=NULL)cout left);cout data right);,71,postOrder(),void postOrder()const if(root!=NULL)cout left);postOrder(t-right);cout data;,72,树的删除的实现,树的删除可以用递归的方法来实现。先递归删除左右子树，再删除根结点本身,73,clear(),void clear()if(root!=NULL)clear(root);root=NULL;void

22、clear(Node*t)if(t-left!=NULL)clear(t-left);if(t-right!=NULL)clear(t-right);delete t;,74,创建一棵树,创建过程：先输入根结点的值，创建根节点对已添加到树上的每个结点，依次输入它的两个儿子的值。如果没有儿子，则输入一个特定值实现工具：使用一个队列，将新加入到树中的结点放入队列依次出队。对每个出队的元素输入它的儿子,75,队列的变化,76,createTree,template void BinaryTree:createTree(Type flag)linkQueue que;Node*tmp;Type x,l

23、data,rdata;/创建树，输入flag表示空 cout x;root=new Node(x);que.enQueue(root);,77,while(!que.isEmpty()tmp=que.deQueue();cout data ldata rdata;if(ldata!=flag)que.enQueue(tmp-left=new Node(ldata);if(rdata!=flag)que.enQueue(tmp-right=new Node(rdata);cout create completed!n;,78,二叉树类的应用,创建一棵由整型值组成的二叉树求高度求规模按前序、中序和

24、后序遍历归并两棵树,79,int main()BinaryTree tree,tree1(M),tree2;tree.createTree();cout 高度为：tree.height()endl;cout 规模为：tree.size()endl;tree.PreOrder();tree.MidOrder();tree.PostOrder();,80,tree2.makeTree(Y,tree,tree1);cout endl;cout 高度为：tree2.height()endl;cout 规模为：tree2.size()endl;tree2.PreOrder();tree2.MidOrde

25、r();tree2.PostOrder();return 0;,81,执行实例,输入根结点：A输入A的两个儿子(表示空结点)：LC输入L的两个儿子(表示空结点)：BE输入C的两个儿子(表示空结点)：D输入B的两个儿子(表示空结点)：输入E的两个儿子(表示空结点)：输入D的两个儿子(表示空结点)：W输入W的两个儿子(表示空结点)：X输入X的两个儿子(表示空结点)：,82,高度为：5规模为：8前序遍历：A L B E C D W X中序遍历：B L E A C W X D后序遍历：B E L X W D C A高度为：6规模为：10前序遍历：Y A L B E C D W X M中序遍历：B L

26、E A C W X D Y M后序遍历：B E L X W D C A M Y,83,二叉树,二叉树的概念二叉树的性质二叉树的基本运算二叉树的遍历二叉树的实现二叉树类二叉树遍历的非递归实现,84,二叉树遍历的非递归实现,递归是程序设计中强有力的工具。递归程序结构清晰、明了、美观，递归程序的弱点：它的时间、空间的效率比较低。所以在实际使用中，我们常常希望使用它的非递归版本二叉树的遍历也是如此。尽管二叉树遍历的递归函数非常简洁，但有时我们还是希望使用速度更快的非递归函数。,85,二叉树遍历的非递归实现,前序遍历中序遍历后序遍历,86,前序遍历的非递归实现,前序遍历第一个被访问的结点是根结点，然后访

27、问左子树，最后访问右子树。可以设置一个栈，保存将要访问的树的树根。开始时，把二叉树的根结点存入栈中。然后重复以下过程，直到栈为空：从栈中取出一个结点，输出根结点的值；然后把右子树，左子树放入栈中,87,前序遍历的过程,输出：ALBECDWX,88,template void BinaryTree:preOrder()const linkStack s;Node*current;cout data;if(current-right!=NULL)s.push(current-right);if(current-left!=NULL)s.push(current-left);,89,二叉树遍历的非递

28、归实现,前序遍历中序遍历后序遍历,90,中序遍历的非递归实现,采用一个栈存放要遍历的树的树根中序遍历中，先要遍历左子树，接下去才能访问根结点，因此，当根结点出栈时，我们不能访问它，而要访问它的左子树，此时要把树根结点暂存一下。存哪里？由于左子树访问完后还要访问根结点，因此仍可以把它存在栈中，接着左子树也进栈。此时执行出栈操作，出栈的是左子树。左子树问结束后，再次出栈的是根结点，此时根结点可被访问。根结点访问后，访问右子树，则将右子树进栈。,91,栈元素的设计,在中序遍历中根结点要进栈两次。当要遍历一棵树时，将根结点进栈。根结点第一次出栈时，它不能被访问，必须重新进栈，并将左子树也进栈，表示接下

29、去要访问的是左子树。根结点第二次出栈时，才能被访问，并将右子树进栈，表示右子树可以访问了。在中序遍历时不仅要记住需要访问哪一棵树，而且还必须记住根结点是在第几次进栈。,92,中序遍历的过程,输出：,B,L,E,A,C,W,X,D,93,StNode类的定义,struct StNode Node*node;int TimesPop;StNode(Node*N=NULL):node(N),TimesPop(0);,94,中序遍历的非递归实现,template void BinaryTree:midOrder()const linkStack s;StNode current(root);cout

30、中序遍历:;s.push(current);,95,while(!s.isEmpty()current=s.pop();if(+current.TimesPop=2)cout data;if(current.node-right!=NULL)s.push(StNode(current.node-right);else s.push(current);if(current.node-left!=NULL)s.push(StNode(current.node-left);,96,二叉树遍历的非递归实现,前序遍历中序遍历后序遍历,97,后序遍历的非递归实现,将中序遍历的非递归实现的思想进一步延伸，可

31、以得到后序遍历的非递归实现。当以后序遍历一棵二叉树时，先将树根进栈，表示要遍历这棵树。根结点第一次出栈时，根结点不能访问，应该访问左子树。于是，根结点重新入栈，并将左子树也入栈。根结点第二次出栈时，根结点还是不能访问，要先访问右子树。于是，根结点再次入栈，右子树也入栈。当根结点第三次出栈时，表示右子树遍历结束，此时，根结点才能被访问。,98,后序遍历的过程,输出：,B,E,L,99,输出：,B,L,E,X,W,D,C,A,100,后序遍历的非递归实现,template void BinaryTree:postOrder()const linkStack s;StNode current(roo

32、t);cout 后序遍历:;s.push(current);,101,while(!s.isEmpty()current=s.pop();if(+current.TimesPop=3)cout data;continue;s.push(current);if(current.TimesPop=1)if(current.node-left!=NULL)s.push(StNode(current.node-left);else if(current.node-right!=NULL)s.push(StNode(current.node-right);,102,第五章 树,树的概念二叉树表达式树哈夫

33、曼树与哈夫曼编码树和森林,103,表达式树,算术表达式可以表示为一棵二叉树，如:(4-2)*(10+(4+6)/2)+2对这棵树后序遍历可 得到结果设计一个类，利用表达式树计算由 四则运算组成的表达式,104,树的构建过程,3*4+5*7*9+8 构建左节点3,3,*4+5*7*9+8 构建根节点*,4+5*7*9+8 构建右节点4,+5*7*9+8 构建根节点+，原树作为左子树,5*7*9+8 构建右节点5,105,*7*9+8 下移到右节点，构建根节点*，原来的右节点作为它的左节点,7*9+8 构建右节点7,*9+8 创建根*，原树作为左子树,106,+8 上移到根。创建根+，原树作为左子

34、树,8 8作为左节点,9+8 9作为右子树,107,构建过程总结,顺序扫描中缀表达式当扫描到的是运算数：先检查当前的表达式树是否存在。如果不存在，则表示扫描到的是第一个运算数，将它作为树根。如果树存在，则将此运算数作为前一运算符的右孩子。如果扫描到的是+或-：将它作为根结点，原来的树作为它的左子树。,108,构建过程总结 续,如果扫描到的是*或/：则与根结点比较。如果根结点也是*或/，则根结点应该先执行，于是将当前运算符作为根结点，原来的树作为左子树。如果根结点是+或-，则当前运算符应该先运算，于是将它作为右子树的根，原来的右子树作为它的左子树。在遇到运算数时，如何知道它前面的运算符是谁？这只

35、需要判别根结点有没有右孩子。如果没有右孩子，则运算数是根结点的右运算数，否则就是根结点右孩子的右运算数。,109,构建过程（括号的处理）,(4+5)*(8+9)+10 遇到括号，将括号内的子表达式构建一棵子树 作为整个表达式的一个运算数,*(8+9)+10*作为根节点，括号内的子树作为左子树,(8+9)+10括号内的子表达式构建一棵子树作为整棵树的右子树,+10+作为根节点，原树作为左子树，10作为右子树,110,表达式树类的设计,数据成员：指向树根节点的指针公有成员函数：构造函数：调用create从表达式构建一棵树result：计算表达式的结果，用后序遍历过程私有成员函数：Create带有递

36、归参数的result函数getToken：create函数所用的子函数，用于从表达式中获取一个语法单位,111,结点的设计,在表达式树中，每个叶子结点保存的是一个运算数，每个非叶结点保存的是一个运算符。结点的数据部分应该包括两个部分：结点的类型和值。,112,calc类的定义,class calc enum Type DATA,ADD,SUB,MULTI,DIV,OPAREN,CPAREN,EOL;struct node Type type;int data;node*lchild,*rchild;node(Type t,int d=0,node*lc=NULL,node*rc=NULL)ty

37、pe=t;data=d;lchild=lc;rchild=rc;node*root;,113,public:calc(char*s)root=create(s);int result()if(root=NULL)return 0;return result(root);private：node*create(char*,114,私有create函数的实现,calc:node*calc:create(char*,115,case CPAREN:case EOL:return root;case ADD:case SUB:if(root=NULL)root=new node(returnType,

38、0,p);else root=new node(returnType,0,root);break;case MULTI:case DIV:if(root=NULL)root=new node(returnType,0,p);else if(root-type=MULTI|root-type=DIV)root=new node(returnType,0,root);else root-rchild=new node(returnType,0,root-rchild);return root;,116,getToken,calc:Type calc:getToken(char*,117,if(*s

39、=0)return EOL;type=*s;+s;switch(type)case+:return ADD;case-:return SUB;case*:return MULTI;case/:return DIV;case(:return OPAREN;case):return CPAREN;default:return EOL;,118,私有的result函数的实现,int calc:result(calc:node*t)int num1,num2;if(t-type=DATA)return t-data;num1=result(t-lchild);num2=result(t-rchild)

40、;switch(t-type)case ADD:t-data=num1+num2;break;case SUB:t-data=num1-num2;break;case MULTI:t-data=num1*num2;break;case DIV:t-data=num1/num2;return t-data;,119,Calc类的应用,int main()calc exp(2*3+(1*2*3+6*6)*(2+3)/5+2/2);cout exp.result()endl;return 0;,120,Calc类的特点,使用时和基于栈实现的calc类完全一样缺点没有考虑表达式不正确的情况没有考虑乘方

41、运算,121,第五章 树,树的概念二叉树表达式树哈夫曼树与哈夫曼编码树和森林,122,字符的机内表示,在计算机中每个字符是用一个编码表示大多数编码系统都采用等长编码，如ASCII编码例如在某段文本中用到了下列字符，括号中是它们出现的频率：a(10),e(15),i(12),s(3),t(4),空格(13),换行(1)。如采用定长编码，7个不同的字符至少要用3位编码。,123,总存储量：3*（10+15+12+3+4+13+1）=3*58=174 bit,124,这个编码可以对应成如下的完全二叉树，左枝为0，右枝为1,125,很显然，将换行上移一层可以减少存储量,不等长编码可以减少存储量！,12

42、6,前缀编码,字符只放在叶结点中 字符编码可以有不同的长度由于字符只放在叶结点中，所以每个字符的编码都不可能是其他字符编码的前缀前缀编码可被惟一解码,127,哈夫曼树,哈夫曼树是一棵最小代价的二叉树，在这棵树上，所有的字符都包含在叶结点上。要使得整棵树的代价最小，显然权值大的叶子应当尽量靠近树根，权值小的叶子可以适当离树根远一些。,128,总共用了146bit,哈夫曼编码,129,哈夫曼算法,1、给定一个具有n个权值 w1,w2,wn 的结点的集合 F=T1,T2,Tn 2、初始时，设集合 A=F。3、执行 i=1 至 n-1 的循环，在每次循环时执行以下操作从当前集合中选取权值最小、次最小的

43、两个结点，以这两个结点作为内部结点 bi 的左右儿子，bi 的权值为其左右儿子权值之和。在集合中去除这两个权值最小、次最小的结点，并将内部结点bI 加入其中。这样，在集合A中，结点个数便减少了一个。这样，在经过了n-1 次循环之后，集合A中只剩下了一个结点，这个结点就是根结点。,130,a(10),e(15),i(12),s(3),t(4),空格(13),换行(1)。,131,132,133,哈夫曼编码的生成,每个字符的编码是根节点到该字符的路径左枝为0，右枝为1,134,哈夫曼树类的实现,为了便于找出一组符号的哈夫曼编码，我们可以定义一个哈夫曼树类。哈夫曼树类的对象可以接受一组符号以及对应的

44、权值，并告知每个符号对应的哈夫曼编码。因此，哈夫曼树类应该有两个公有的成员函数：构造函数：接受一组待编码的符号以及它们的权值，构造一棵哈夫曼树。GetCode函数根据保存的哈夫曼树为每个叶结点生成哈夫曼编码。,135,哈夫曼树的存储,在哈夫曼树中，每个要编码的元素是一个叶结点，其它结点都是度数为2的节点一旦给定了要编码的元素个数，由n0n21可知哈夫曼树的大小为2n-1哈夫曼树可以用一个大小为2n的数组来存储。0节点不用，根存放在节点1。叶结点依次放在n+1到2n的位置每个数组元素保存的信息：结点的数据、权值和父结点和左右孩子的位置,136,137,13,12,11,10,9,8,7,6,5,

45、4,3,2,1,0,13,11,7,12,8,3,右,10,6,5,9,4,2,左,6,3,5,6,3,2,4,5,4,2,1,1,父,1,13,4,3,12,15,10,4,8,18,25,33,58,权,nl,sp,t,s,i,e,a,值,生成过程,138,编码的产生,生成a的代码：结点4的右孩子（1），结点4是结点2的左孩子（01），结点2是结点1的左孩子（001）,对每个结点，从叶子往根推进，是左枝加0，是右枝加1,139,哈夫曼树类,存储设计结点的表示：结点的数据、权值和父结点和左右孩子的位置哈夫曼树的存储：一个结点数组以及一个整型数据成员，保存数组的大小。操作构建一棵哈夫曼树：构造

46、函数实现。给出节点数据数组，权值数组和数据个数获取树上节点的哈夫曼编码返回一个数组，数组的元素由数据和编码两部分组成的,140,template class hfTreeprivate:struct Node Type data;/结点值 int weight;/结点的权值 int parent,left,right;Node*elem;int length;,141,public:struct hfCode Type data;string code;hfTree(const Type*x,const int*w,int size);void getCode(hfCode result);h

47、fTree()delete elem;,142,构造函数,template hfTree:hfTree(const Type*v,const int*w,int size)const int MAX_INT=32767;int min1,min2;/最小树、次最小树的权值 int x,y;/最小树、次最小树的下标/置初值 length=2*size;elem=new Nodelength;for(int i=size;i length;+i)elemi.weight=wi-size;elemi.data=vi-size;elemi.parent=elemi.left=elemi.right=0

48、;,143,/构造新的二叉树 for(i=size-1;i 0;-i)min1=min2=MAX_INT;x=y=0;for(int j=i+1;j length;+j)if(elemj.parent=0)if(elemj.weight min1)min2=min1;min1=elemj.weight;x=y;y=j;else if(elemj.weight min2)min2=elemj.weight;x=j;elemi.weight=min1+min2;elemi.left=x;elemi.right=y;elemi.parent=0;elemx.parent=i;elemy.parent

49、=i;,144,getCode的伪代码,getCode(hfCode result)for(int i=size;i length;+i)resulti-size.data=elemi.data;resulti-size.code=;p=elemi.parent;s=i;while(p不等于0)if(p的左孩子是=s)resulti-size.code 前添加0;else resulti-size.code 前添1;移到上一层；,145,getCode代码,template void hfTree:getCode(hfCode result)int size=length/2;int p,s;

50、/s是追溯过程中正在处理的结点，p是s的父结点下标 for(int i=size;i length;+i)resulti-size.data=elemi.data;resulti-size.code=;p=elemi.parent;s=i;while(p)if(elemp.left=s)resulti-size.code=0+resulti-size.code;else resulti-size.code=1+resulti-size.code;s=p;p=elemp.parent;,146,哈夫曼类的使用,为下列符号集生成哈夫曼编码：a(10),e(15),i(12),s(3),t(4),d