数据结构之树和二叉树(.ppt

第六章树和二叉树,6.1树的类型定义,6.2二叉树的类型定义,6.3二叉树的存储结构,6.4二叉树的遍历,6.5线索二叉树,6.6树和森林的表示方法,6.7树和森林的遍历,6.8哈夫曼树与哈夫曼编码,6.1树的类型定义,数据对象D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系R：,基本操作：,查找类,插入类,删除类,Root(T)/求树的根结点,查找类：,Value(T,cur_e)/求当前结点的元素值,Parent(T,cur_e)/求当前结点的双亲结点,LeftChild(T,cur_e)/求当前结点的最左孩子,RightSibling(T,cur_e)/求当前结点的右兄弟,TreeEmpty(T)/判定树是否为空树,TreeDepth(T)/求树的深度,TraverseTree(T,Visit()/遍历,InitTree(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(,ClearBiTree(,二叉树的重要特性,性质1：在二叉树的第i层上至多有2i-1个结点。(i1),用归纳法证明：归纳基：归纳假设：归纳证明：,i=1层时，只有一个根结点：2i-1=20=1；,假设对所有的j，1ji，命题成立；,由归纳假设知：第I-1层上至多有2i-2个结点。又因为二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。,性质2：深度为k的二叉树上至多有2k-1个结点（k1）。,证明：证明用求等比数列前k项和的公式,基于上一条性质，深度为k的二叉树上的结点数至多为20+21+2k-1=2k-1。,性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。,证明：,设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n0*0+n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。,两类特殊形态的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,性质4：具有n个结点的完全二叉树的深度为log2n+1。,证明：,设完全二叉树的深度为k，则由性质2和完全二叉树的定义知：深度为k-1的二叉树应该是一棵满二叉树，故结点数为2k-1-1；深度为k的完全二叉树当为满二叉树时结点数最多为2k1。所以得2k-1-1n2k12k-1nn，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。,1、完全二叉树第3层有2个叶子，则该二叉树有多少个结点？分析：第3层最多有23-1=4个结点。完全二叉树只有3层，则前2层为满二叉树，结点数为22-1=3个结点，故总结点数=3+2=5；完全二叉树含有4层，则前3层为满二叉树，结点数为23-1=7个结点。又第3层上结点数为4，由题知其中两个为叶子，则其它（4-2）=2个结点应为内部结点。由完全二叉树的定义知：这两个结点中有一个结点的度可以为1或2，而其它结点的度必为2。综上：总结点数=7+1+（2-1）*2=10或总结点数=7+2*2=11。,练习：,作业,已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点中有（m-1）个结点的度为2，其余度为1。含n个结点的完全三叉树的高度为多少？完全二叉树第7层有10个叶子，问该二叉树共有多少个结点？,6.3二叉树的存储结构,二、二叉树的链式存储表示,一、二叉树的顺序存储表示,（适合存储完全二叉树）即用一组地址连续的存储单元集资从上至下，从左至右存储完全二叉树上的结点元素。也就是说，将完全二叉树上编号为i的结点存放在数组下标为（i-1)的分量中。若要存储一棵一般的二叉树，结点的存放应与完全二叉树上的结点对照，存储在数组的相应分量中。用“0”表示不存在该结点。可能会浪费很多存储空间，单支树就是一个极端情况。,一、二叉树的顺序存储表示,完全二叉树的数组表示一般二叉树的数组表示,数组表示,#defineMAX_TREE_SIZE100/二叉树的最大结点数typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTreebt;,C语言描述,A,D,E,B,C,F,root,lchilddatarchild,结点结构,1.二叉链表,二、二叉树的顺序存储表示,typedefstructBiTNode/结点结构TElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;,lchilddatarchild,结点结构:,C语言描述:,A,D,E,B,C,F,root,2三叉链表,parentlchilddatarchild,结点结构,typedefstructTriTNode/结点结构structTriTNode*parent;/双亲指针structTriTNode*lchild,;/左孩子指针TElemTypedata;structTriTNode*rchild;/右孩子指针TriTNode,*TriTree;,parentlchilddatarchild,结点结构:,C语言的类型描述如下:,二叉树链表表示的示例,6.4二叉树的遍历,一、遍历的概念,二、先左后右的遍历算法,三、算法的递归描述,四、遍历算法的应用举例,按照某种顺序不重复地访问二叉树中的所有结点。此处的访问可以是输出、修改等操作，根据实际需要而定。使得每个结点均被访问一次，而且仅被访问一次。,“访问”的含义可以很广，如：输出结点的信息。,一、遍历的概念,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,对“二叉树”而言，可以有两条搜索路径：,1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；,二、先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。遍历结果-+a*b-cd/ef,先（根）序的遍历算法：,voidPreorder(BiTreeT)if(T)/如果树不为空visit(T-data);/输出根结点Preorder(T-lchild);/先序遍历左子树Preorder(T-rchild);/先序遍历右子树,先序,若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。遍历结果a+b*c-d-e/f,中（根）序的遍历算法：,voidInorder(BiTreeT)if(T)/如果树不为空Inorder(T-lchild);/先序遍历左子树visit(T-data);/输出根结点Inorder(T-rchild);/先序遍历右子树,中序,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,后（根）序的遍历算法：,遍历结果abcd-*+ef/-,voidPastorder(BiTreeT)if(T)/如果树不为空Pastorder(T-lchild);/先序遍历左子树visit(T-data);/输出根结点Pastorder(T-rchild);/先序遍历右子树,后序,二、遍历算法的应用举例,1、统计二叉树中叶子结点的个数(先序遍历),2、求二叉树的深度(后序遍历),3、建立二叉树的存储结构,4、求二叉树的结点个数,1、统计二叉树中叶子结点的个数,算法基本思想:,分别求出左子树、右子树的叶子数，然后相加。,voidCountLeaf(BiTreeT)if(!T)return0;elseif(!T-lchild)/if/CountLeaf,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,intDepth(BiTreeT)/返回二叉树的深度if(!T)return0;elsedl=Depth(T-lchild);dr=Depth(T-rchild);dep=1+(dldr?dl:dr);returndep;,3建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法,以字符串的形式:根左子树右子树,定义一棵二叉树,例如:,A,B,C,D,以空白字符“”表示,A(B(,C(,),D(,),空树,只含一个根结点的二叉树,A,以字符串“A”表示,以下列字符串表示,statusCreateBiTree(BiTree/CreateBiTree,ABCD,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,4、求二叉树的结点个数,IntNodeCount(BiTreeT)if(!T)return0;elsenl=NodeCount(T-lchild);nr=NodeCount(T-rchild);returnnl+nr+1;,仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,主要思想：先序序列中第一个为“根”，标出之；在中序序列中标出“根”，并分出左、右子树；在先序序列中标出左、右子树；分别对左、右子树重复以上步骤。,abcdefg,cbdaegf,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,由二叉树的后序和中序序列建树,二叉树的后序序列,二叉树的中序序列,主要思想：后序序列中第一个为“根”，标出之；在中序序列中标出“根”，并分出左、右子树；在后序序列中标出左、右子树；分别对左、右子树重复以上步骤。,由二叉树的后序和先序序列能否建树？,二叉树的后序序列,二叉树的先序序列,左子树,右子树,根,结论：不能唯一确定二叉树！,例：先序：AB后序：BA,练习：先序：ABDEGCFH中序：DBGEAFHC中序：DBGEAFHC后序：DGEBHFCA,画出二叉树，并写出后序序列。,画出二叉树，并写出先序序列。,证明：在含有n个结点的二叉树中，含有n+1个空指针。,Proof:设二叉树中度为0、1、2的结点数分别为n0,n1,n2，即n=n0+n1+n2由于二叉树中的空指针数=2n0+n1+0=n0+n0+n1由性质3知：n0=n2+1所以空指针数=n2+1+n0+n1=n+1证毕。,6.5线索二叉树,何谓线索二叉树？线索链表的遍历算法如何建立线索链表？,一、何谓线索二叉树？,是要借助含有n个结点的二叉树中(n+1)个空指针域，作为线索，直接指向遍历序列中“前驱”或“后继”结点。,A,B,C,D,E,F,G,H,K,例如:,先序序列:ABCDEFGHK,中序序列:BDCAHGKFE,后序序列:DCBHKGFEA,指向该线性序列中的“前驱”和“后继”的指针，称作“线索”,与其相应的二叉树，称作“线索二叉树”,包含“线索”的存储结构，称作“线索链表”,ABCDEFGHK,D,C,B,E,1、对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域，并作如下规定：,若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link=0”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索Thread=1”。,若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link=0”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread=1”。,如此定义的二叉树的存储结构称作“线索链表”。,typedefstructBiThrNodTElemTypedata;structBiThrNode*lchild,*rchild;/左右指针PointerThrLTag,RTag;/左右标志BiThrNode,*BiThrTree;,2、线索链表的类型描述：,typedefenumLink,ThreadPointerThr;/Link=0:指针，Thread=1:线索,二、线索链表的遍历算法:,for(p=firstNode(T);p;p=Succ(p)Visit(p);,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,例如:对中序线索化链表的遍历算法,中序遍历的第一个结点？,在中序线索化链表中结点的后继？,左子树上处于“最左下”（没有左子树）的结点。,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,voidInOrder(BiThrTreeT,void(*Visit)(TElemTypee)p=T-lchild;/p指向根结点while(p!=T)/空树或遍历结束时，p=Twhile(p-LTag=Link)p=p-lchild;/第一个结点while(p-RTag=Thread/p进至其右子树根/InOrder,三、如何建立线索链表？,A,B,D,E,G,C,F,H,中序遍历序列：DBEGAFHC,NULL,NULL,方法：在遍历过程中修改空指针或先写出遍历序列，标出空指针，对照再画出线索。,6.6树和森林的表示方法,树的三种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟）存储表示法,一、双亲表示法:,1、定义：用一组地址连续的空间存储树的结点，同时在每个结点中附设一个指示器指示双亲结点在链表中的位置。（即：保存结点信息和双亲的下标）,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G5,r=0n=7,dataparent,2、特点：求双亲简便，求孩子麻烦。,typedefstructPTNodeElemTypedata;intparent;/双亲位置域PTNode;,dataparent,#defineMAX_TREE_SIZE100,结点结构:,3、C语言的类型描述:,typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根结点的位置和结点个数PTree;,树结构:,二、孩子链表表示法:,1、定义：把每个结点的孩子结点链成单链表。2、特点：求孩子方便，求双亲麻烦。,A,B,C,D,E,F,G,0A1B2C3D4E5F6G,r=0n=7,datafirstchild,123,45,6,孩子链表表示法,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G5,r=0n=7,dataparentfirstchild,123,45,6,-1000224,3、可能把孩子链表表示法和双亲表示法结合起来。,typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;,孩子结点结构:,childnext,4、C语言的类型描述:,typedefstructElemTypedata;ChildPtrfirstchild;/孩子链的头指针CTBox;,双亲结点结构,datafirstchild,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置CTree;,树结构:,三、树的二叉链表(孩子-兄弟）存储表示法,1、定义：链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。2、结点结构：,A,B,C,D,E,F,G,ABCEDFG,root,ABCEDFG,typedefstructCSNodeTElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,3、C语言的类型描述:,结点结构:,firstchilddatanextsibling,四、树和二叉树的转换,1、转换规则树的根树的第一个孩子右兄弟,二叉树的根,左孩子,右孩子,注：由树转换得到的二叉树的右子树永远为空！,五、森林和二叉树的转换,1、规则：森林中第一棵树的根变成二叉树的根森林中其它树的根当成第一棵树的根的兄弟把森林中每棵树都转化成相应的二叉树,注：由森林转换得到的二叉树的右子树可能不为空！,A,B,C,D,E,F,G,H,I,A,B,C,D,E,F,G,H,I,6.7树和森林的遍历,一、树的遍历,二、森林的遍历,ABCDEFGHIJK,一、树的遍历把树看成两部分：1。树的根2。根的子树森林,1,2,树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先访问根结点，然后依次先根遍历各棵子树。,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,1、2,2、1,ABCDEFGHIJK,先根遍历时顶点的访问次序：,ABEFCDGHIJK,后根遍历时顶点的访问次序：,EFBCIJKHGDA,层次遍历时顶点的访问次序：,ABCDEFGHIJK,BCDEFGHIJK,森林中第一棵树的根结点；,森林中第一棵树的子树森林；,森林中其它树构成的森林。,森林由三部分构成：,二、森林的遍历,1,2,3,1.先序遍历,若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行先序遍历。(1、2、3),BCDEFGHIJK,1,2,3,先序遍历序列：,BEFCDGHIJK,中序遍历,若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行中序遍历。(2、1、3),BCDEFGHIJK,1,2,3,中序遍历序列：,EFBCIJKHGD,6.8哈夫曼树与哈夫曼编码,几个预备概念最优树的定义如何构造最优树前缀编码,几个概念,路径：树中一个结点到另一个结点所经过的分支。路径长度：路径上的分支数目。树的路径长度：从根到每一个结点的路径长度之和。（完全二叉树是路径长度最短的二叉树）,A,B,C,D,一、最优树的定义,结点的带权路径长度定义为：结点的权值乘以该结点的路径长度。,结点的路径长度定义为：从根结点到该结点的路径上分支的数目。,树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)。,在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优二叉树”。,例如：,2,79,7,5,4,9,2,WPL(T)=72+52+23+43+92=60,WPL(T)=74+94+53+42+21=89,5,4,用给定的n个权值构造n棵以各权值为根的二叉树。,二、如何构造最优树(哈夫曼树）,(1),(赫夫曼算法)以二叉树为例：,问题：根据给定的n个权值w1,w2,wn，构造一棵以这些权值为叶子的哈夫曼树？,选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并且这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；并删去这两棵二叉树，同时加入刚新生成的二叉树；,(2),(3),重复第(2)步，直至生成一棵树为止。,9,例如:已知权值W=5,6,2,9,7,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码码的前缀。,三、前缀编码,利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即：使所传电文的总长度最短。,有八种字符：abcdefgh，其在通信联络中出现的概率分别为：0.050.290.070.080.140.230.030.11,试设计哈夫曼遍码。设权w=(5,29,7,8,14,23,3,11)n=8构造过程：,5,29,7,8,14,23,3,11,5,3,8,7,8,15,11,19,14,29,23,42,