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

第六章树和二叉树,数据结构多媒体课件,第六章树和二叉树,6.1树的定义和基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用,数据结构多媒体课件,教学重点,（1）树的基本概念和术语（2）二叉树定义和存储结构（3）二叉树的遍历次序（4）二叉树遍历算法,数据结构多媒体课件,教学难点,（1）二叉树遍历算法的设计（2）修改二叉树遍历算法（3）进行二叉树其它相关的操作（4）解决实际应用问题,数据结构多媒体课件,数据结构多媒体课件,6.1.1树的定义树(Tree)是n（n0）个结点的有限集合T，在一棵非空树中（n0）有且仅有一个称作根的结点；其余结点可分为m个（m0）互不相交的集合T1，T2Tm，其中，每一个集合本身又是一棵树,并称为根的子树。当n=0时，称为空树。,6.1树的定义和基本术语,数据结构多媒体课件,有限集合T1，T2Tm应该“互不相交”，即任意两个集合不能有相重的结点。树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整棵树的根画在最上层。树的结构参见下图6.1,数据结构多媒体课件,图6.1,数据结构多媒体课件,6.1.2基本术语,1.结点(node)：表示树中的元素，包括一个数据元素及若干指向其子树的分支结点的度（Degree）：树中每个结点具有的子树数称为该结点的度。叶子结点(leaf):度数为0的结点，也叫终端结点。分支结点：度不为0的结点，也叫非终端结点。是除叶子结点外的所有结点，根结点之外的分支结点统称为内部结点,根结点又称为开始结点。树的度：一棵树中各个结点度数的最大值,数据结构多媒体课件,2、孩子(child)和双亲(parents)：一个结点的子树的根称为该结点的孩子，相应的该节点称为孩子的双亲(parents)。兄弟(sibling)：同一双亲的孩子之间互称兄弟。祖先：从根到该结点所经分支上的所有结点都叫该结点的祖先子孙：以某结点为根的子树中的任一结点都称为该结点的子孙,数据结构多媒体课件,3、结点的层次(level):从根结点算起，根为第一层，它的孩子为第二层堂兄弟：其双亲在同一层上的节点互称为堂兄弟。深度(depth)：树中结点的最大层次称为树的深度。,数据结构多媒体课件,4、有序树若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。5、无序树若一棵树中所有子树的次序无关紧要，则称为无序树。6、森林（forest）：若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,数据结构多媒体课件,图6.2,数据结构多媒体课件,树形结构的逻辑特征,树形结构的逻辑特征可用树中结点之间的父子关系来描述：树中任一结点都可以有零个或多个直接后继结点（即儿子结点），但至多只能有一个直接前趋结点（即父亲结点）。树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。树形结构是非线性结构。,数据结构多媒体课件,6.2二叉树,6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构,数据结构多媒体课件,6.2.1二叉树的定义,1、定义：二叉树（BinaryTree）：二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的、分别称作这个根的左子树和右子树的二叉树组成。这也是一个递归定义。二叉树可以是空集，所以根可以有空的左子树或右子树，或者左、右子树皆为空。因此，二叉树有五种基本形态。二叉树不是树的特殊情况，它们是两个概念,数据结构多媒体课件,(a)空二叉树(b)仅有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树均非空的二叉树,二叉树的五种基本形态（图6.3）,数据结构多媒体课件,二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分,说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。,数据结构多媒体课件,图6.4,数据结构多媒体课件,性质1若二叉树的层数从1开始，则二叉树的第i层结点数，最多为2i-1个（i1）。,6.2.2二叉树的性质,20=1,21=2,22=4,23=8,数据结构多媒体课件,深度（高度）为k的二叉树最大结点数为2k-1（k1）。证明:最大结点个数=20+21+22+2k-1=2k-1,性质2,数据结构多媒体课件,对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设n0,n1和n2分别为二叉树中度为0,度为1和度为2的结点个数，则二叉树中总的结点个数n满足：n=n0+n1+n2再有除了根结点之外，每个结点都由一个分支射入，则分支数B与总的结点数之间的关系为：n=B+1另外，由于这些分支是由度为1或2的结点射出的，则有B=n1+2n2则由上三式得：n0=n2+1,性质3,数据结构多媒体课件,满二叉树,在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。满二叉树的第一层有一个结点（即根结点），第二层有两个结点，依此类推。每一层的结点数都是上一层结点数的二倍。所以，在满二叉树的第i层共有2i-1个结点（i1），一个深度为h的满二叉树的结点总数为2h-1。,数据结构多媒体课件,图6.5满二叉树,数据结构多媒体课件,完全二叉树,如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。例如图6.3中的满二叉树，如果缺少从第11号至第15号结点（没有图中虚框里的几个结点），就是一个完全二叉树。设完全二叉树的结点数为n，它与树的深度之间的关系为：2h-1-11，则其父结点编号为i/2。2)如果2in，则其左儿子结点编号为2i；若2in，则无左儿子结点。3)如果（2i+1）n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。,数据结构多媒体课件,I/2,i,i+1,2i,2i+1,2(i+1),2i+3,2(i+1),2i+3,i,2i,图6.6完全二叉树中结点I和i+1,(a)i和i+1结点在同一层,(b)i和i+1结点不在同一层,如图6.6所示为完全二叉树上结点及其左右孩子结点之间的关系。,2i+1,i+1,i,数据结构多媒体课件,6.2.3二叉树的存储结构1.顺序存储结构,思想:用一个一维数组来存储二叉树的各个结点C语言表示#defineMAX_TREE_SIZE100/二叉树的最大结点数typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTreebt;,数据结构多媒体课件,分析:显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。,数据结构多媒体课件,01234567891011,完全二叉树的顺序表示,1,2,3,4,5,6,7,8,9,10,11,12,顺序存储结构:,下标,数据结构多媒体课件,对应的顺序存储结构:一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组.,非完全二叉树的顺序表示:,数据结构多媒体课件,总结:,顺序存储结构适合存储完全二叉树对于非完全二叉树，采用链式存储结构更合适,数据结构多媒体课件,2.二叉链表,结点结构:通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。,数据结构多媒体课件,存储表示,typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BITree;这里的TElemType可以是任何相应的数据类型如int、float或char等。,数据结构多媒体课件,二叉链表,注意:在含有n个结点的二叉链表中有n+1个空链域。,数据结构多媒体课件,3.三叉链表,通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲结点。,rchild,parent,数据结构多媒体课件,6.3遍历二叉树和线索二叉树,6.3.1遍历二叉树6.3.2线索二叉树,数据结构多媒体课件,6.3遍历二叉树和线索二叉树6.3.1遍历二叉树,定义:二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。本节仅讨论二叉链表的遍历过程。,数据结构多媒体课件,假如以L、D、R分别表示遍历左子树,访问根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR先序（根）遍历,LDR中序（根）遍历，LRD后序（根）遍历。,由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。,数据结构多媒体课件,(1)中序（InOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：中序遍历左子树；访问根结点；中序遍历右子树。(2)先序（PreOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：访问根结点；先序遍历左子树；先序遍历右子树。,三种遍历次序以递归的形式定义：,数据结构多媒体课件,(3)后序（PostOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：后序遍历左子树；后序遍历右子树；访问根结点。,数据结构多媒体课件,Voidpreorder(BintreeT)if(T)printf(“%d”,pdata);preorder(plchild);preorder(prchild);,返回,返回,返回,返回,A,C,B,D,返回,先序序列：ABDC,数据结构多媒体课件,先序遍历:,DLR,先序序列：ABDC,数据结构多媒体课件,LDR,中序序列：BDAC,中序遍历:,数据结构多媒体课件,LRD,后序序列：DBCA,后序遍历:,数据结构多媒体课件,例如图（1）所示的二叉树表达式a+b*(c-d)-e/f若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef（1）按中序遍历,其中序序列为：a+b*c-d-e/f（2）按后序遍历,其后序序列为：abcd-*+ef/-（3）以上3个序列（1）（2）（3）恰好为表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）,*,a,/,b,-,d,c,f,e,图（1）,数据结构多媒体课件,中序遍历序列：先序遍历序列：后序遍历序列：,二叉树遍历举例,HDIBEAFCG,ABDHIECFG,HIDEBFGCA,数据结构多媒体课件,中序遍历递归算法,voidInOrder(BITreeT)if(T)InOrder(T-lchild);visit(T-data);InOrder(T-rchild);,数据结构多媒体课件,先序遍历递归算法,voidPreOrder(BITreeT)if(T)visit(T-data);PreOrder(T-lchild);PreOrder(T-rchild);,数据结构多媒体课件,后序遍历递归算法,voidPostOrder(BITreeT)if(T)PostOrder(T-lchild);PostOrder(T-rchild);visit(T-data);,数据结构多媒体课件,遍历算法的应用,二叉树的遍历算法是一个重要的应用注意:1.理解访问根结点的意义2.对具体问题需要考虑遍历的顺序,数据结构多媒体课件,1.先序创建二叉链表,StatusCreateBiTree(BITree,数据结构多媒体课件,2.输出二叉树的结点,voidPreOrder(BITreeT)if(T)printf(T-data);PreOrder(T-lchild);PreOrder(T-rchild);,数据结构多媒体课件,3.输出二叉树的叶子结点,voidPreOrder(BITreeT)if(T)if(T-lchild=NULL,数据结构多媒体课件,4.统计二叉树的叶子结点个数,intn=0;voidleafcount(BITreeT)if(T)if(T-lchild=NULL,数据结构多媒体课件,练习,3.一棵二叉权的先序、中序和后序遍历序列分别如下，请构造出该二叉树。先序：ABCDEFGHIJK中序：CBEDFAHJKIG后序：CEFDBKJIHGA,数据结构多媒体课件,练习,4.对二叉树中的结点进行按层次进行顺序（每一层自左到右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,请画出该二叉树。,数据结构多媒体课件,二叉树的非递归遍历,可利用堆栈将递归算法改写成非递归的形式。下面以中序遍历为例来具体说明。,T,-,*,c,a,b,a,*,-,c,b,Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)/if/while,数据结构多媒体课件,6.3.2线索二叉树,相关概念:在一个n结点的链式存储二叉树中，有n+1个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。线索:在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。线索二叉树:对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。,数据结构多媒体课件,在一个线索二叉树中，必须设法将线索与指向结点左、右儿子结点的指针加以区别。可给每个结点增加两个标志域，即左线索标志域LTag，右线索标志域RTag。,LTag,RTag,lchild域指示结点的左孩子,lchild域指示结点的前趋,rchild域指示结点的右孩子,rchild域指示结点的后继,数据结构多媒体课件,增加线索标志域后的结点结构为：这种结点类型和相应结点的指针类型定义如下：typedefenumPointerTagLink,Thread;typedefstructBiThrNodeElemTypedata;PointerTagLTag,RTag;/*ltag和rtag只能取值为0或1*/structBiThrNode*lchild,*rchild;BiThrNode,*BiThrTree;,数据结构多媒体课件,中序线索树,数据结构多媒体课件,中序遍历线索树,思想:先由头结点指针找到根结点，从根结点起沿左指针逐结点一直向左查找，找到左线索标志为1的结点(“最左”的结点)即为遍历中需首先访问的结点。由此结点开始，反复进行寻找后继结点的过程，并陆续访问这些结点，直至结束。,数据结构多媒体课件,中序遍历线索二叉树非递归算法,voidthinorder(BiThrTreeT)/二叉树附加了头结点,T指向头结点p=T-lchild;/p指向根结点whild(p!=T)/*空树或遍历结束时,p=T*/while(p-LTag=Link)p=p-lchild;/*从根往下找到最左的结点，即中序序列的开始结点*/visit(p-data);/访问左子树为空结点while(p-Rtag=Thread,数据结构多媒体课件,中序线索化,思想：一边中序遍历一边建立线索。若访问结点的左儿子结点为空，则建立前趋线索；若右儿子结点为空，则建立后继线索。为此附设一个指针pre始终指向刚刚访问过的结点，而用指针p指示当前正在访问的结点。pre的初始值为NULL。,数据结构多媒体课件,中序线索化算法,voidinthread(BiThrTree,数据结构多媒体课件,中序线索化算法续,if(pre!=NULL,数据结构多媒体课件,6.4树和森林,6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历,数据结构多媒体课件,6.4.1树的存储结构,1双亲表示法2.孩子表示法3孩子兄弟表示法,数据结构多媒体课件,1双亲表示法,这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置.其结点的结构如下：,数据结构多媒体课件,双亲表示法的形式说明如下：,#defineMAX100typedefstructPTNode/结点结构TElemTypedata;intparent;PTNode;typedefstruct/树结构PTNodenodesMAX;intr,n;/根的位置和结点数PTree;,数据结构多媒体课件,双亲表示法举例,特点：找双亲容易,找孩子难,i,0,1,1,2,4,4,4,5,0,-1,如何找孩子结点,数据结构多媒体课件,2.孩子表示法,这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表.,数据结构多媒体课件,类型说明,typedefstructCTNode/孩子链表结点的定义intchild;/该孩子结点在线性表中的位置structCTNode*next;/指向下一个孩子结点*ChildPtr;typedefstruct/顺序表结点的结构定义TElemTypedata;/结点的信息ChildPtrfirstChild;/孩子链表的头指针CTBox;typedefstruct/树的定义CTBoxnodesMAX;/顺序表intn,r;/结点数和根的位置CTree;,数据结构多媒体课件,特点：找孩子容易，找双亲难,数据结构多媒体课件,6,1,2,3,4,5,7,8,data,fc,parent,0,带双亲的孩子链表,数据结构多媒体课件,3.孩子兄弟表示法,这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。,数据结构多媒体课件,形式说明,typedefstructCSNodeElemTypedata;/*结点信息*/StructCSNode*firstChild,*Nextsibling;/*第一个孩子,下一个兄弟*/CSNode,*CSTree;,数据结构多媒体课件,孩子兄弟表示法（二叉树表示法）,数据结构多媒体课件,6.4.2森林与二叉树的转换,树的孩子兄弟链表结构与二叉树的二叉链表结构在物理结构上是完全相同的，只是它们的逻辑含义不同，所以树和森林与二叉树之间必然有着密切的关系。本节我们就介绍树和森林与二叉树之间的相互转换方法。,数据结构多媒体课件,数据结构多媒体课件,1、将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,数据结构多媒体课件,2、将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子,右孩子的右孩子,沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,数据结构多媒体课件,3、森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,数据结构多媒体课件,4、二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树,数据结构多媒体课件,6.4.3树与森林的遍历,1.树的遍历方法主要有以下两种：（1）先根遍历若树非空，则遍历方法为：访问根结点。从左到右，依次先根遍历根结点的每一棵子树。（2）后根遍历若树非空，则遍历方法为：从左到右，依次后根遍历根结点的每一棵子树访问根结点。,数据结构多媒体课件,树的遍历举例,如左图树先根遍历序列为ABECFHGD后根遍历序列为EBHFGCDA,数据结构多媒体课件,2.森林的遍历,森林的遍历方法主要有以下两种：(1)先序遍历若森林非空，则遍历方法为：访问森林中第一棵树的根结点。先序遍历第一棵树的根结点的子树森林。先序遍历除去第一棵树之后剩余的树构成的森林。,数据结构多媒体课件,森林的遍历举例,如上图森林先序遍历序列为ABCDEFGHIJ,数据结构多媒体课件,(2)后序遍历若森林非空，则遍历方法为：后序遍历森林中第一棵树的根结点的子树森林。访问第一棵树的根结点。后序遍历除去第一棵树之后剩余的树构成的森林。,数据结构多媒体课件,森林的遍历举例,如上图森林后序遍历序列为BCDAFEHJIG,数据结构多媒体课件,6.5赫夫曼树及其应用,6.5.1赫夫曼树(最优二叉树)6.5.2赫夫曼编码,数据结构多媒体课件,6.5.1赫夫曼树(最优二叉树),1.基本术语：路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径长度：路径上的分支数称为这两点之间的路径长度。树的路径长度：树的路径长度是从树的根到每一结点的路径长度之和，一般记作pl。,数据结构多媒体课件,pl=0+1+1+2+2+2+2=10,pl=0+1+1+2+2+2+3=11,数据结构多媒体课件,结点的权：在许多实际应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。结点的带权路径长度：从树的根结点到该结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度。,数据结构多媒体课件,树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为：其中n表示叶子结点个数，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。给定一组n个实数，以它们作为各个叶子结点的权，可构成不同的有n个叶子结点的二叉树，这些二叉树的带权路径长度wpl可能不同。,数据结构多媒体课件,不同wpl的二叉树,给定四个数7，5，2，4作为叶子结点的权，构成三种不同的二叉树。,WPL=7*2+5*2+2*2+4*2=36,数据结构多媒体课件,不同wpl的二叉树,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,数据结构多媒体课件,赫夫曼树又称为最优二叉树，它是这样定义的：设有n个权值w1，w2，wn，在这些权值为各个叶子结点的权所构成的二叉树中，带权路径长度WPL最小的二叉树叫做赫夫曼树。赫夫曼(Huffman)于1952年提出了得到这种树的算法，因此相应的算法称为赫夫曼算法。,数据结构多媒体课件,2.构造赫夫曼树,将n个权值w1，w2，wn按递增次序排列，设其顺序为w1，w2，wn，取出最小的两个w1和w2，分别作为根结点的左、右儿子结点的权组成一个二