数据结构课件(树和二叉树).ppt

数据结构,第六章树和二叉树2020年5月8日星期五,6.1树的类型定义,数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:（1）在D中存在唯一的称为根的数据元素root,（2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作：查找：Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);TreeEmpty(T);TreeDepth(T);TraverseTree(T,Visit();,6.1树的类型定义,插入：InitTree(,6.1树的类型定义,和线性结构的比较,A(B(E(K,L),F),C(G),D(H(M),I,J)嵌套括号表示法,树的表示方法：,基本术语,结点:数据元素+若干指向子树的分支。结点的度:分支的个数。树的度:树中所有结点的度的最大值。叶子结点:度为零的结点。分支结点:度大于零的结点；路径和路径长度。孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点。边：双亲节点x到子结点y的有序对(x，y)。结点的层次:假设根结点的层次为1，第i层的结点的子树根结点的层次为i+1。规定根的层数为0。树的深度：树中叶子结点所在的最大层次。森林：是m（m0）棵互不相交的树的集合任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林。,6.2二叉树的类型定义,二叉树的定义,定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。与树的关系：这也是一个递归定义。区别：二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。,二叉树的5种基本形态,二叉树的主要基本操作：,查找：Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();插入：InitBiTree(,性质1：在二叉树的第i层上至多有2i-1个结点(i=1)。证明：采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20=1,命题成立。现在假定第i1层上命题成立，则第i1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i1层上最大结点数的二倍，即22i-22i-1。命题得到证明。,二叉树的重要特性：,性质2：深度为k的二叉树至多有2k1个结点（k=1).证明：深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数2i-1（第i层上的最大结点数）,二叉树的重要特性：,二叉树的重要特性：,性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：Nn0n1n2（1）再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：NB1。由于这些分支都是由度为1和2的结点射出的，所以有：Bn1+2*n2NB1n12n21（2)由式（1）和（2）得到：n0+n1+n2=n1+2*n2+1n0n21,两种特殊形态的二叉树：一棵深度为k且由2k-1个结点的二叉树称为满二叉树。如果深度为k、由n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。完全二叉树的特点是：（1）所有的叶结点都出现在第k层或k1层。（2）对任一结点，如果其右子树的最大层次为h，则其左子树的最大层次为h或h1。,满二叉树和完全二叉树,性质4：具有n个结点的完全二叉树的深度为log2n1。符号x表示不大于x的最大整数。证明：假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1或2k-1=n2k取对数得到：k1n，则结点i无右孩子；否则，其右孩子是结点2i1。证明：略！,完全二叉树的特点:,6.3二叉树的存储结构,1.顺序存储结构,它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：#definemax-tree-size100Typedeftelemtypesqbitreemax-tree-size;Sqbitreebt从树根起，自上层至下层，每层自左至右的给所有结点编号。,完全二叉树,表示该处没有元素存在仅仅为了好理解,一般二叉树,1.顺序存储结构,缺点：有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！,1.顺序存储结构,（2）二叉链表法,TypedefstructBiTNodeTelemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;,2）二叉链表法,二叉树的二叉链表存储表示,StatusCreateBiTree(BiTree*T)/*创建一棵二叉树*/scanf(,6.3二叉树的存储结构,链式存储结构的算法：,三叉链表法,TypedefstructTBiTNodeTelemTypedata;structTBiTNode*lchild,*rchild,*parent;BiTNode,*BiTree;,三叉链表法,二叉树的三叉链表存储表示,6.4二叉树的遍历,一、问题的提出,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义可以很广，如：输出结点的信息等。对“二叉树”而言，可以有三条搜索路径：1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。,6.4二叉树的遍历,二、先左后右的遍历算法,先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。中（根）序的遍历算法：若二叉树为空树,则空操作；否则,（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后（根）序的遍历算法：若二叉树为空树,则空操作;否则,（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,6.4二叉树的遍历,示例,先序：/-ab+cd中序：a-b/c+d后序：ab-cd+/,先序：-a+/bcd中序：a-b/c+d后序：abc/d+-,先序：+-a/bcd中序：a-b/c+d后序：abc/-d+,分别称为表达式的前缀表示法、中缀表示法和后缀表示法（逆波兰表示法）。,6.4二叉树的遍历,三、算法的递归描述,voidPreorder(BiTreeT,void(*visit)(TElemType/遍历右子树,voidInOrderTraverse(BiTreeT,void(*visit)(TElemType/访问结点,四、先序遍历算法的非递归描述,先序遍历的非递归算法。t指向根，p为指针，指向当前结点。使用一个堆栈s（），top为栈指针1ift=NULL2then输出这是一棵空树3elsep=t，top=04DO5whilep！=NULL6输出data（p）;7top+;8iftopn9then调用栈满10elsestop=p，p=lchild（p）11iftop！=012p=stop;top-;p=rchild（p）13while(top=07top+;8iftopn9then调用栈满10elsestop=p，p=lchild（p）11iftop！=012p=stop;top-;p=rchild（p）13while(top=0p=Lchild(p)8iftop!=09thenp=stop,top-10输出data(p)11pn)6then调用栈满7elsestop=p;p=Lchild(p)8iftop!=09thenp=stop,top-10输出data(p)11plchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;,五、遍历算法的应用举例,3、复制二叉树(后序遍历),/生成一个二叉树的结点BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(1);T-data=item;T-lchild=lptr；T-rchild=rptr;returnT;,五、遍历算法的应用举例,3、复制二叉树(后序遍历),BiTNode*CopyTree(BiTNode*T)if(!T)returnNULL;if(T-lchild)newlptr=CopyTree(T-lchild);elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);elsenewrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr);returnnewnode;,6.5线索二叉树,一、何谓线索二叉树？,遍历二叉树是按一定的规则将二叉树中结点排列成一个线性序列；这实际上是把一个非线性结构进行线性化的操作。以二叉链表作为存储结构时，对于某个结点只能找到其左右孩子，而不能直接得到结点在任一序列中的前驱或后继。要想得到只能通过遍历的动态过程才行。怎样保存遍历过程中得到的信息呢？（1增加两个指针（2利用结构中的空链域，并设立标志。即采用如下的形式：,6.5线索二叉树,何谓线索二叉树？,指向该线性序列中的“前驱”和“后继”的指针，称作“线索”。包含“线索”的存储结构，称作“线索链表”；与其相应的二叉树，称作“线索二叉树”。对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域ltag的值为0；否则，lchild域的指针指向其“前驱”，且左标志ltag的值为1。若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域rtag的值为0；否则，rchild域的指针指向其“后继”，且右标志rtag的值为1。,6.5线索二叉树,6.5线索二叉树,线索链表的结构描述：,typedefenumLink,ThreadPointerThr;/Link=0:指针，Thread=1:线索typedefstructBiThrNodeTElemTypedata;structBiThrNode*lchild,*rchild;/左右指针PointerThrLTag,RTag;/左右标志BiThrNode,*BiThrTree;,6.5线索二叉树,找结点的后继,线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。下面以中序为例看看如何在线索二叉树中找结点的后继。（1树中所有叶子结点和只有左子树的右指针均为线索，直接指示了结点的后继；（2其他非终端结点的右链均为指针，无法得到后继的信息。然而根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。（3反之，在中序线索树中找结点前驱的规律是：若左标志是1，则左链为线索，指示其前驱；否则，遍历该结点的左子树时最后访问的结点（左子树中最右下的结点为其前驱)。,6.5线索二叉树,找结点的后继,在后序线索树中找结点x的后继较复杂，可分三种情况：（1若结点x是二叉树的根,则其后继为空;（2若结点x是其双亲的右孩子或是左孩子且其双亲没有右子树,则其后继即为双亲结点。（3若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历出的第一个结点。由此可见，在后序线索化树上找后继时需知道结点的双亲，因此需要使用三叉链表。可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度也是O(n)，但常数因子小，且不需要设栈，因此若在某程序中需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。,6.5线索二叉树,二、线索链表的遍历算法:,for(p=firstNode(T);p;p=Succ(p)Visit(p);中序线索化链表的遍历算法:中序遍历的第一个结点？在中序线索化链表中结点的后继？,6.5线索二叉树,二、线索链表的遍历算法:,StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)/T指向头结点，头结点的左链lchild指向根结点，头结点的右链rchild，指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树，对每个数据元素调用函数Visit。p=T-lchild;/p指向根结点while(p!=T)/空树或遍历结束时，p=Twhile(p-LTag=Link)p=p-lchild;if(!Visit(p-data)returnERROR;/访问其左子树为空的结点while(p-RTag=Thread/InOrderTraverse_Thr,6.5线索二叉树,三、如何建立线索链表？,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,6.5线索二叉树,三、如何建立线索链表？,StatusInOrderThreading(BiThrTree/InOrderThreading,voidInThreading(BiThrTreep)if(p)InThreading(p-lchild);/左子树线索化if(!p-lchild)p-LTag=Thread;p-lchild=pre;/建前驱线索if(!pre-rchild)pre-RTag=Thread;pre-rchild=p;/建后继线索pre=p;/保持pre指向p的前驱InThreading(p-rchild);/右子树线索化/InThreading,6.6树和森林,一、树的三种存储结构1.双亲表示法:,在这种表示中，容易找到父结点及其所有的祖先；也能找到结点的子女和兄弟（虽然比较麻烦）。但它没有表示出结点之间的左右次序，所以无法求树中某个指定结点的最左子结点和右兄弟结点等基本运算。,一、树的三种存储结构,1.双亲表示法:用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：#defineMAX_TREE_SIZE100结点结构:typedefstructPTNode/*树中结点结构*/Elemdata;/*结点中的元素*/intparent;/双亲位置域PTNode;树结构:typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根结点的位置和结点个数PTree,一、树的三种存储结构,2.孩子链表表示法:,一、树的三种存储结构,2、孩子链表表示法:,结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示，子表中的元素按从左到右的次序存放。结构类型如下：,双亲结点结构typedefstructElemdata;ChildPtrfirstchild;/孩子链的头指针CTBox;,树结构:typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置CTree;,孩子结点结构:typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;,一、树的三种存储结构,带双亲的孩子链表表示法:,一、树的三种存储结构,3、树的二叉链表(孩子-兄弟）存储表示法,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,二、树、树林与二叉树的转换,1、树、树林转换为二叉树,由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。从二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。这样，若把森林中第二棵树的根结点看成是第一棵树的兄弟，则可以导出森林和二叉树之间的对应关系。,二、树、树林与二叉树的转换,树转换为二叉树,转换规则：步骤：1.将同父亲的兄弟结点连接；2.对每一个非叶结点只保留第一个孩子链，删除其他孩子的链；3.将树向左旋转450。,树转换为二叉树,事例,树转换为二叉树,事例,2、森林转换成二叉树,转换规则：,如果FT1,T2,Tm是森林，则可按如下规则转换成一棵二叉树Broot,LB,RB。（1）若F为空，则B为空树；（2）若F非空，则B的根root为森林中第一棵树的根Root(T1)，B的左子树LB是从T1中根结点的子树森林F1T11,T12,T1m1转换而成的二叉树；其右子树RB是从森林FT2,T3,Tm转换而成的二叉树。,2、森林转换成二叉树,3、二叉树转换为树,转换规则：,1.对有左子树的所有结点与其左孩子的右链上的所有结点进行连接；2.删除以前所有的旧右链。,4、二叉树转换成森林,转换规则：,如果Broot,LB,RB是一棵二叉树，则可按如下规则转换成森林FT1,T2,Tm（1）若B为空，则F为空树；（2）若B非空，则为森林中第一棵树的根Root（T1）即为B的根root，T1中根结点的子树森林F1T11,T12,T1m1是有B的左子树LB转换而来的森林；F中除T1之外的其余树组成的森林FT2,T3,Tm是由B的右子树转换而成的。,二叉树转换成森林,示例,若树T为空,返回；否则访问T的根结点；依次先根次序遍历各子树T1、T2Tm；右图遍历结果为：ABDEHIJCFG,三、树和森林的遍历,(1)先根次序遍历的规则：,若树T为空，返回；否则依次后根次序遍历各子树T1、T2Tm；访问根结点。右图遍历结果为：DHIJEBFGCA,树的遍历,(2)后根次序遍历的规则：,若树T为空，返回；否则访问根结点；若第1,i(i1）层结点已被访问，则从左到右依次访问i+1层结点；右图遍历结果为：ABCDEFGHIJ,树的遍历,(3)广度优先遍历(层次序遍历)：,若森林F为空,返回；否则访问F的第一棵树的根结点；先根次序遍历第一棵树的子树森林；先根次序遍历其它树组成的森林。遍历结果：ABCDEFGHIJ,森林的遍历,(1)先根次序遍历的规则：,若森林F为空，返回；否则中根次序遍历第一棵树的子树森林；访问F的第一棵树的根结点。中根次序遍历其它树组成的森林；遍历结果：BCDAFEHJIG,森林的遍历,(2)中根次序遍历的规则：,若森林F为空，返回；否则依次遍历各棵树的根结点；依次遍历各棵树根结点的所有子女；依次遍历这些子女结点的子女结点。遍历结果：AEGBCDFHIJ,森林的遍历,(3)广度优先遍历(层次序遍历)：,6.7哈夫曼树与哈夫曼编码,一、最优树的定义,结点的路径长度：从根结点到该结点的路径上分支的数目。树的路径长度：树中每个结点的路径长度之和。树的带权路径长度：树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)。在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”,例如下面的程序：if(a60)p=“bad”;elseif(a70)p=“pass”;elseif(a80)p=“general”;elseif(a90)p=“good”;elsep=“excellent”;,二、如何构造最优树,哈夫曼最早研究出一个带有一般规律的算法:以二叉树为例:(1)根据给定的n个权值w1,w2,wn，构造n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；(2)在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(3)从F中删去这两棵树，同时加入刚生成的新树;(4)重复(2)和(3)两步，直至F中只含一棵树为止。,二、如何构造最优树,三.赫夫曼编码,在远程通讯中，要将待传字符转换成由二进制的字符串：设要传送的字符为：ABACCDA若编码为：A00B01C10D-11,若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。,三.赫夫曼编码,在远程通讯中，要将待传字符转换成由二进制的字符串：设要传送的字符为：ABACCDA若编码为：A0B00C1D-01,关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。,三.赫夫曼编码,设要传送的字符为：ABACCDA若编码为：A0B110C10D-111,采用二叉树设计二进制前缀编码,三.赫夫曼编码,译码过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。,三.哈夫曼编码,在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。我们可以利用二叉树来设计二进制的前缀编码。约定左分支表示字符0，右分支便是字符1，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码也是前缀编码。证明：假设某一个叶子x结点的编码是另一个叶子结点y编码的前缀，说明从根结点到叶子结点y中间需经过结点x，从而说明x有左或右子树，这与x是叶子结点矛盾。那么现在求最短的二进制编码实际上就是构造哈夫曼树的过程，由此得到的二进制编码，称哈夫曼编码。,三.哈夫曼编码,由于哈夫曼树中没有度为1的结点(这类树又称严格的(strict)(或正则的)二叉树)；则一棵有n个叶子结点的赫夫曼树共有2n-1个结点（因n2=n0-1)，可以存储在一个大小为2n-1的一维数组中。如何选定结构类型？（1）编码需要从叶子到根（2）译码需要从根到叶子求Huffman编码：由叶子根，若：（1）从左分支下去，则分支为“0”；（2）从右分支下去，则分支为“1”。,举例,例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。W（权）=2，4，2，3，3，叶子结点个数n=5,构造的Huffman树,设计示例：,例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。由Huffman树得Huffman编码为：,出现频率越大的字符，其Huffman编码越短。,TBACS000110110111,6.8哈夫曼树与哈夫曼编码,赫夫曼编码的实现,Typedefstructunsingnedintweight;(赫夫曼树结点结构权)unsingnedintparent,lchild,rchild;(双亲，左右孩子）HTNode,*HuffmaTree;（动态分配数组存储赫夫曼树）Typedefchar*HuffmaCode;（动态分配数组存储赫夫曼编码表）,构造赫夫曼树和求赫夫曼编码的算法如下：,VoidHuffmaCoding(HuffmaTree(下面是求编码）,构造赫夫曼树和求赫夫曼编码的算法如下：,HC=(HuffmanCode)malloc(n+1)*sizeof(char*);（分配头指针向量）Cd=(char*)malloc(n*sizeof(char);（分配求编码空间）Cdn-1=“0”;（编码结束符）For(i=1;i=n;+i)（逐个符号求编码）start=n1;（编码结束符位置）for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)（从叶子结点开始向根）if(HTf.lchild=c)cd-start=“0”;elsecd-start=“1”;HCi=(char*)malloc(nstart)*size(char);（为第i个字符编码分配空间）stcpy(HCi,（释放空间）/HuffanCoding,98017,1015034,1119089,12290510,13420611,14580212,1510001314,本章小结,1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.要熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态。4.理解二叉树线索化的实质，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。6.学会编写实现树的各种操作的算法。7.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,voidmain()int；while(1)printf(请选择操作码:n);printf(0:结束,1:进栈,2:退栈,3:显示:c=);scanf(%d,Thankyou!,