数据结构C++PPT5.ppt

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

1、数据结构第5章 二叉树,2,5.1 定义及主要特性,逻辑定义 递归定义:二叉树由结点的有限集合组成，这个集合或者为空，或者由一个根结点及两棵不相交的，分别称作这个根的左子树和右子树的二叉树组成。特点：每个结点至多有二棵子树。二叉树的子树有左、右之分，且其次序不能任意颠倒。,3,基本形态,4,二叉树的相关术语,从一个结点到它的两个子结点都有边(edge)相连，这个结点称为它的子结点的父结点(parent)。如果一棵树的一串结点n1,n2,nk有如下关系:结点ni是ni+1的父结点(1ik),就把n1,n2,nk称为一条由n1至nk的路径(path)。这条路经的长度(length)是k-1(因为k

2、个结点是用k-1条边连接起来的)。如果有一条路径从结点R至结点M,那么R就称为M的祖先(ancestor),而M称为R的子孙(descendant)。,5,二叉树的相关术语,结点M的深度(depth)就是从根结点到M的路径的长度。树的高度(height)等于最深的结点的深度+1。任何深度为d的结点的层数(level)都为d。根结点深度为0，层数也为0。没有非空子树的结点称为叶结点(leaf)或终端结点。至少有一个非空子树的结点称为分支结点或内部结点(internal node)。,6,二叉树的相关术语,满二叉树 如果一颗二叉树的任何结点，或者是树叶，或者恰有两个非空子女的分支结点，则此二叉树称

3、为满二叉树。,(a)满二叉树(非完全二叉树)(b)完全二叉树(非满二叉树),7,二叉树的相关术语,完全二叉树 若一颗二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。自根结点起每一层从左至右地填充。一棵高度为d的完全二叉除了d-1层外，每一层都是满的。底层叶结点集中在左边的若干位置上。,8,完全二叉树,9,二叉树性质,1.满二叉树定理：非空满二叉树树叶数等于其分支结点数加1。证明：设二叉树结点数为n，叶结点数为m，分支结点数为b。有n（总结点数=m（叶)+b（分支）(1)每个分支，恰有两个子结点（满），故有2*b条边一颗

4、二叉树，除根结点外，每个结点都恰有一条边联接父结点，故共有n-1条边。即n-1=2*b(2)由(1)(2)得n-1=m+b-1=2*b，得出m(叶)=b（分支）+1,10,二叉树的性质,2、满二叉树定理的推论:一棵非空二叉树空子树的数目等于其结点数目加1。证明1：设二叉树T，将其所有空子树换成叶结点，把新的二叉树记为T。所有原来树T的结点现在是树T的分支结点。根据满二叉树定理，新添加的叶结点数目等于树T的结点数目加1，而每个新添加的叶结点对应树T的一棵空子树，因此树T中空子树的数目等于树T中结点数目加1。,11,二叉树的性质,证明2：根据定义，二叉树T中每个结点都有两个子结点指针（空或非空）。

5、因此一个有n个结点的二叉树有2n个子结点指针。除根结点外，共有n-1个结点，它们都是由其父结点中相应指针指引而来的，换句话说就有n-1个非空子结点指针。既然子结点指针数为2n，则其中有n+1个为空(指针)。,12,二叉树的性质,3.任何一颗二叉树，度为0的结点比度为2的结点多一个。证明：设有n个结点的二叉树的度为0、1、2的结点数分别为=n0，n1，n2，n=n0+n1+n2(公式1)设边数为e。因为除根以外，每个结点都有一条边进入，故n=e+1。由于这些边是有度为1和2的结点射出的，因此e=n1+2*n2，于是n=e+1=n1+2*n2+1（公式2）因此由公式（1）（2）得 n0+n1+n2

6、=n1+2*n2+1 即n0=n2+1,13,二叉树的性质,4.二叉树的第i层（根为第0层）最多有2i个结点5.高度为k(深度为k-1。只有一个根结点的二叉树的高度为1，深度为0)的二叉树至多有2k-1个结点6.有n个结点的完全二叉树的高度为log2n+1(深度为log2n),14,二叉树的抽象数据类型,template class BinNode public:virtual BinNode*left()const=0;virtual BinNode*right()const=0;virtual Elem,15,5.2 周游二叉树,周游：系统地访问数据结构中的结点。每个结点都正好被访问到一次

7、。方法：前序周游(preorder traversal)：访问根结点；前序周游左子树;前序周游右子树。中序周游(inorder traversal)：中序周游左子树;访问根结点;中序周游右子树。后序周游(postorder traversal)：后序周游左子树;后序周游右子树;访问根结点。,16,先序遍历,D L R,先序遍历序列：A B D C,17,中序遍历,L D R,中序遍历序列：B D A C,18,后序遍历,L R D,后序遍历序列：D B C A,19,举例,中序遍历：,后序遍历：,层次遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f

8、,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,先序遍历：,20,前序遍历算法,template void preorder(BinNode*subroot)if(subroot=NULL)return;visit(subroot);preorder(subroot-leftchild();preorder(subroot-rightchild();,21,遍历算法应用,计算二叉树的结点数：template int count(BinNode*subroot)if(subroot=NULL)return 0;/visit(subroot);return

9、 1+count(subroot-left()+count(subroot-right();,22,5.3 二叉树的实现,5.3.1 使用指针实现二叉树二叉链表(最常用)class BinNodePtr private:Elem it;BinNodePtr*lc;BinNodePtr*rc;好处：运算方便;问题：空指针太多,23,二叉树的存储,带父指针的三重链表在某些经常要回溯到父结点的应用中很有效。class BinNodePtr private:Elem it;BinNodePtr*lc;BinNodePtr*rc;BinNodePtr*father;,24,二叉树存储（区别叶和分支）,叶

10、结点和分支结点的分别实现 当叶结点和分支结点差别较大，或出于应用要求而需要区分叶结点和分支结点时(a)联合(b)类继承和虚函数,25,表达式树：联合实现方法,class VarBinNode public:Nodetype mytype;union struct VarBinNode*left;VarBinNode*right;Operator opx;intl;Operand var;,26,用不同的类实现分支和叶,class VarBinNode public:virtual bool isLeaf isLeaf()=0;class LeafNode:public VarBinNode p

11、rivate:Operand var;public:LeafNode(const Operand,27,不同类实现的分支结点,Class IntlNode:public VarBinNodeprivate:VarBinNode*left;VarBinNode*right;Operator opx;public:IntlNode(const Operator,28,5.3.2 结构性空间开销分析,根据满二叉树定理：一半的指针是空的 如果只有叶结点存储数据，分支结点为内部结构结点（如Huffman树），则取决于二叉树是否满（越满存储效率越高）对于简单的每个结点存两个指针、一个数据域 总空间(2p+

12、d)n 结构性：2pn 如果p=d，则2p/(2p+d)=2/3,29,结构性空间开销分析,去掉满二叉树叶结点中的指针则结构性开销为1/2（假设p=d）如果只在叶结点存数据，则结构性开销为2pn/(2pn+d(n+1)2/3（假设p=d）注意：区分叶结点和分支结点又需要额外的算法时间。,30,5.3.3 使用数组实现完全二叉树,完全二叉树的顺序存储ABCDEFGHIJKL按照二叉树的层次周游次序存储在一个数组中简单，省空间,31,顺序存储,非完全二叉树在置空值而转换为完全二叉树存储 CEDJFX/K/G/I/L,32,完全二叉树的下标对应关系,0,0,0,0,0,0,0,0,0,0,0,0,3

13、3,完全二叉树的下标公式,公式中r表示结点的索引，n表示二叉树结点总数。Parent(r)=(r-1)/2，当0rn时。Leftchild(r)=2r+1，当2r+1n时。Rightchild(r)=2r+2，当2r+2 n 时。Leftsibling(r)=r-1，当r为偶数且0=r=n-1。Rightsibling(r)=r+1，当r为奇数且r+1n。,34,5.4 二叉查找树,定义：二叉检索树或者为空,或者是满足下列条件的非空二叉树:(1若它的左子树非空,则左子树上所有结点的值均小于根结点的值;(2)它的右子树非空,则右子树上所有结点的值均大于或等于根结点的值;(3)左右子树本身又各是一

14、棵二叉检索树。性质:按照中序周游将各结点打印出来，将得到按照由小到大的排列。,35,BST图示,36,检索,二叉检索树的效率就在于只需检索二个子树之一。从根结点开始，在二叉检索树中检索值K。如果根结点储存的值为K，则检索结束。如果K小于根结点的值，则只需检索左子树 如果K大于根结点的值,就只检索右子树 这个过程一直持续到K被找到或者我们遇上了一个树叶。如果遇上树叶仍没有发现K，那么K就不在该二叉检索树中。,37,二叉检索树类的定义,class BST private:BinNode*root;int nodecount;void clearhelp(BinNode*);BinNode*inse

15、rthelp(BinNode*,const Elem,38,二叉检索树类的定义,public:BST()root=NULL;nodecount=0;BST()clearhelp(root);void clear()clearhelp(root);root=NULL;nodecount=0;void insert(const Elem,39,检索,template bool BST:findhelp(BinNode*subroot,const Key,40,插入,template BinNode*BST:inserthelp(BinNode*subroot,const Elem,41,BST插入

16、图示,42,删除,从二叉检索树中删除一个任意的结点R，首先必须找到R，接着将它从二叉树中删除掉。如果R是一个叶结点(没有儿子),那么只要将R的父结点指向它的指针改为NULL就可以了。如果R是一个分支结点,我们就不能简单地删除这个结点,因为这样做会破坏树的连通性。如果R只有一个儿子,就将R的父结点指向它的指针改为指向R的子结点就可以了。如果R有两个儿子,为了保持二叉检索树的性质,可以用R的中序后继结点来代替它。,43,删除子树中最小值图示,template BinNode*BST:deletemin(BinNode*subroot,BinNode*,44,删除右子树中最小值结点,45,BST R

17、emove（1）,template BinNode*BST:removehelp(BinNode*subroot,const Key,46,BST Remove（2）,else/Found it:remove it BinNode*temp;t=subroot;if(subroot-left()=NULL)subroot=subroot-right();else if(subroot-right()=NULL)subroot=subroot-left();else/Both children are non-empty subroot-setRight(deletemin(subroot-ri

18、ght(),temp);Elem te=subroot-val();subroot-setVal(temp-val();temp-setVal(te);t=temp;return subroot;,47,5.5 堆与优先队列,定义:对于一个关键码序列 K0,K1,Kn-1，如果满足KiK2i+1,KiK2i+2,(i=0,1,n/2-1),则称其为堆，而且这是最大值堆。性质:是任意一个结点的值都大于或者等于其任意一个子结点存储的值。由于根结点包含大于或等于其子结点的值，而其子结点又依次大于或等于各自子结点的值，所以根结点存储着该树所有结点中的最大值。,48,最小值堆,最小值堆(min-heap

19、)的性质是每一个结点存储的值都小于或等于其子结点存储的值。由于根结点包含小于或等于其子结点的值，而其子结点又依次小于或等于各自子结点的值，所以根结点存储了该树所有结点的最小值。,49,最大值堆的实现,template class maxheapprivate:Elem*Heap;/Pointer to the heap array int size;/Maximum size of the heap int n;/Number of elems now in heap void siftdown(int);/Put element in placepublic:maxheap(Elem*h,i

20、nt num,int max);int heapsize()const;bool isLeaf(int pos)const;int leftchild(int pos)const;int rightchild(int pos)const;int parent(int pos)const;bool insert(const Elem,50,建堆图示,51,堆的形成,不必将值一个个地插入堆中，通过交换形成堆。假设根的左、右子树都已是堆，并且根的元素名为R。能这种情况下，有两种可能：(1)R的值大于或等于其两个子女，此时堆已完成(2)R的值小于其某一个或全部两个子女的值，此时R应与两个子女中值较大的

21、一个交换，结果得到一个堆，除非R仍然小于其新子女的一个或全部的两个。这种情况下，我们只需简单地继续这种将R“拉下来来”的过程，直至到达某一个层使它大于它的子女，或者它成了叶结点。,52,Shiftdown操作,53,举例,54,Shiftdown,template void maxheap:siftdown(int pos)while(!isLeaf(pos)int j=leftchild(pos);int rc=rightchild(pos);if(rcn),55,Remove Max Value,template bool maxheap:removemax(Elem,56,建堆操作的效率

22、,57,5.6 Huffman编码树,1.固定长度编码设所有代码都等长，则表示n个不同的代码需要log2n位称为固定长度编码(a fixed-length coding scheme)。ASCII 码就是一种固定长度编码。如果每个字符的使用频率相等的话，固定长度编码是空间效率最高的方法。2.数据压缩和不等长编码频率不等的字符,58,数据压缩和不等长编码,可以利用字母的出现频率来编码，使得经常出现的字母的编码较短，反之不常出现的字母编码较长。数据压缩既能节省磁盘空间，又能提高运算速度。（外存时空权衡的规则）不等长编码是今天广泛使用的文件压缩技术的核心 Huffman 编码是最简单的文件压缩技术，

23、它给出了这种编码方法的思想。,59,5.6.1 建立Huffman编码树,对于n个字符K0，K1，Kn-1，们它的使用频率分别为w0，w1，wn-1，请给出它们的编码，使得总编码效率最高。定义一个树叶的带权路径长度(Weighted path length)为权乘以它的路径长度(即树叶的深度）。这个问题其实就是要求给出一个具有n个外部结点的扩充二叉树 该二叉树每个外部结点Ki有一个wi与之对应，作为该外部结点的权,这个扩充二叉树的叶结点带权外部路径长度总和最小（注意不管内部结点，也不用有序）。权越大的叶结点离根越近；如果某个叶的权较小，可能就会离根较远。,60,建立Huffman树的过程,首先

24、，按照“权”（例如频率）将字母排为一列。接着，拿走头两个字母（“权”最小的两个字母），再将它们标记为Huffman树的树叶，将这两个树叶标为一个分支结点的两个子女，而该结点的权即为两树叶的权之和。将所得“权”放回序列中适当位置，使“权”的顺序保持。重复上述步骤直至序列中只剩一个元素，则Huffman树建立完毕。,61,Huffman建树图示,62,Huffman建树图示,63,Huffman建树图示,64,Huffman树结点的实现,template class HuffNode/Node abstract base classpublic:virtual int weight()=0;vir

25、tual bool isLeaf()=0;virtual HuffNode*left()const=0;virtual void setLeft(HuffNode*)=0;virtual HuffNode*right()const=0;virtual void setRight(HuffNode*)=0;,65,Huffman树叶节点的实现,template/Leaf node subclassclass LeafNode:public HuffNode private:FreqPair*it;/Frequency pairpublic:LeafNode(const Elem,66,Huffm

26、an树分支结点的实现,template/Internal node subclassclass IntlNode:public HuffNode private:HuffNode*lc;/Left child HuffNode*rc;/Right child int wgt;/Subtree weightpublic:IntlNode(HuffNode*l,HuffNode*r)wgt=l-weight()+r-weight();lc=l;rc=r;int weight()return wgt;/Return frequency bool isLeaf()return false;HuffNo

27、de*left()const return lc;void setLeft(HuffNode*b)lc=(HuffNode*)b;HuffNode*right()const return rc;void setRight(HuffNode*b)rc=(HuffNode*)b;,67,元素/频率对的类声明,template class FreqPair/An element/frequency pairprivate:Elem it;/An element of some sort int freq;/Frequency for the elementpublic:FreqPair(const

28、Elem,68,Huffman树的类声明,template class HuffTree private:HuffNode*theRoot;public:HuffTree(Elem,69,Huffman树的类声明,/Compare two Huffman trees by total weighttemplate class HHCompare public:static bool lt(HuffTree*x,HuffTree*y)return x-weight()weight();static bool eq(HuffTree*x,HuffTree*y)return x-weight()=y

29、-weight();static bool gt(HuffTree*x,HuffTree*y)return x-weight()y-weight();,70,Huffman树构建函数,/Build a Huffman tree from list fltemplate HuffTree*buildHuff(SLList*,HHCompare*fl)HuffTree*temp1,*temp2,*temp3;for(fl-setStart();fl-leftLength()+fl-rightLength()1;fl-setStart()/While at least two items left

30、fl-remove(temp1);/Pull first two trees fl-remove(temp2);/off the list temp3=new HuffTree(temp1,temp2);fl-insert(temp3);/Put the new tree back on list delete temp1;/Must delete the remnants delete temp2;/of the trees we created return temp3;,71,编码结果,平均代码长度是2.56536。,72,5.6.2 Huffman编码及其用法,编码：标记Huffman

31、树中各个字母的代码。从根结点开始，分别将“0”或“1”标于树的每条边上。“0”对应于连接左子女的那条边，“1”则对应于连接右子女的边。字母的Huffman码就是从根节点到对应于该字母树叶的路径的二进制代码。把所有字母的二进制编码放入一个表中，对于字符串编码时，通过查表来完成。,73,Huffman编码及其用法,反编码：从左至右逐位判别代码串，直至确定一个字母。这可以对Huffman树用其生成代码的过程的逆过程来实现。从树的根结点开始，根据每位的值“0”或“1”决定选择左分支还是右分支，直至到达一个树叶结点。这个树叶包含的字母就是文本信息的第一个字母。然后从下一个位自根结点出发开始下一个字母的翻译。由于任何一个代码的前缀对应一个分支结点，而每个代码都对应一个字母，Huffman代码当然符合前缀特性。没有对应树的某个分支结点的编码。,74,Huffman树编码效率,字母的使用频率的确随具体情况变化。与固定长度编码相比较，有些频率模式并不节省空间；有些则能产生极大的压缩比。如果字母频率的变化范围很大，则Huffman编码是很有效的。如果所编码文本的实际字母频率与预期的相符，我们便能确定Huffman编码所节省的空间。预计平均每个字母的代码长度等于每个代码的长度（Ci）乘以其出现的频率（Pi），即,75,Huffman树编码效率,