(6)--lecture6数据结构数据结构.ppt

1第第6章章 二叉树和树二叉树和树 前面的章前面的章节节主要主要讨论讨论的是的是线线性性结结构，二叉构，二叉树树和和树树属属于非于非线线性的性的结结构。遍构。遍历历非非线线性性结结构比构比线线性性结结构要麻构要麻烦烦。二叉二叉树树及及树树的遍的遍历历技技术术是本章各种算法的核心，而是本章各种算法的核心，而且大多是以且大多是以递归递归的形式表的形式表现现的，的，阅读阅读和和编编写写递归递归算法算法是学是学习习本章的本章的难难点。点。讲讲授本章授本章课课程大程大约约需需8 8课时课时。2v 树结构的特点及基本构的特点及基本术语v 6.1 二叉二叉树v 6.2 二叉二叉树树的的遍遍历v 6.3 树和森林和森林v 6.4 树的的应用用3树结构的特点及基本术语树结构的特点及基本术语4线性结构树型结构第一个数据元素 (无前驱)根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)对比比树型型结构构和和线性性结构构的的结构特点构特点5结点点:数据元素+若干指向子树的分支结点的度点的度:分支的个数树的度的度:树中所有结点的度的最大值叶子叶子结点点:度为零的结点分支分支结点点:度大于零的结点DHIJM基本基本术语6(从根到结点的)路径路径：孩子孩子结点、双双亲结点兄弟兄弟结点、堂兄弟祖先祖先结点、子子孙结点 由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL结点的点的层次次:假设根结点的层次为1 1,第l 层的结点的子树根结点的层次为l+1 1树的深度：的深度：树中叶子结点所在的最大层次76.1 二叉树二叉树一、二叉一、二叉树的定的定义和基本和基本术语二、二叉二、二叉树的几个基本性的几个基本性质三、二叉三、二叉树的存的存储结构构8一、二叉树的定义和基本术语一、二叉树的定义和基本术语9 二叉二叉树的定的定义 二叉树是n（n0）个元素的有限集，它或为空空树，或是由一个根根结点点加上两棵两棵分别称为左左子子树和右子树的、互不交的互不交的二叉二叉树组成。根结点左子树右子树ABCDEFGHKLB10二叉二叉树可以表可以表现出出五种基本形五种基本形态：空空树N只含根只含根结点点右子右子树为空空树NL左子左子树为空空树NR左右子左右子树均不均不为空空树NLR11 二叉二叉树的基本操作：的基本操作：v 查 找找 类 的的 操操 作作v 插插 入入 类 的的 操操 作作v 删 除除 类 的的 操操 作作12 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);InOrderTraverse(T);PostOrderTraverse(T);LevelOrderTraverse(T);查找找类的操作：的操作：13 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入插入类的操作：的操作：14ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删除除类的操作：的操作：15二、二叉二、二叉树的几个基本性的几个基本性质16v 性性质 1：在二叉在二叉树的第的第 i 层上至多有上至多有2i-1 个个结点点(i1)。用用归纳法法证明明：归纳基基：归纳假假设：归纳证明：明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。17v 性性质 2：深度深度为 k 的二叉的二叉树上至多含上至多含 2k-1 个个结点（点（k1）。）。证明：明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。18v 性性质 3：对任何一棵二叉任何一棵二叉树，若它含有，若它含有n0 个叶子个叶子结点、点、n2 个度个度为 2 的的结点，点，则必存在关系式：必存在关系式：n0=n2+1。证明：明：设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。19两两类特殊特殊的二叉的二叉树：满二叉二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉完全二叉树：树中所含的 n 个结点和满二叉树中编号号为 1 至至 n 的的结点点一一对应。abcdefghij12345678910111213141520v 性性质 4：具有具有 n 个个结点的完全二叉点的完全二叉树的的深度为 log2n +1。证明：明：设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。22三、二叉树的存储结构三、二叉树的存储结构u 二叉二叉树顺序存序存储表示表示u 二叉二叉树链式存式存储表示表示23#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;u 二叉二叉树顺序存序存储表示表示24例如例如:A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEF140132625u 二叉二叉树链式存式存储表示表示1.二叉二叉链表表2三叉三叉链表表3线索索链表表26ADEBCF root结点点结构构:1.二叉二叉链表表lchild data rchild27typedef struct BiTNode /结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点点结构构:C 语言的言的类型描述如下型描述如下:28rootADEBCF 2三叉三叉链表表parent lchild data rchild结点点结构构:29 typedef struct TriTNode /结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针 struct TriTNode *parent;/双亲指针 TriTNode,*TriTree;parent lchild data rchild结点点结构构:C 语言的言的类型描述如下型描述如下:30（请见后面的线索二叉索二叉树）3线索索链表表316.2 二叉树遍历二叉树遍历一、一、问题的提出的提出二、遍二、遍历算法描述算法描述三、遍三、遍历算法算法应用用举例例四、四、线索二叉索二叉树32 顺着某一条搜索路径巡巡访二叉树中的结点，使得每个结点均被均被访问一次一次，而且仅被被访问一次一次。一、一、问题的提出的提出 “访问”的含义可以很广，如：输出结点的数据、判断结构信息等。33 “遍遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个每个结点有两个后点有两个后继，则存在如何遍存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。34 对“二叉树”而言，可以有三条搜索路径：1先上后下先上后下的按层次遍历的按层次遍历；2先左先左（子树）（子树）后右后右（子树）的遍历（子树）的遍历；3先右先右（子树）（子树）后左后左（子树）的遍历（子树）的遍历。35先左后右的遍先左后右的遍历算法算法先先（根）序的遍（根）序的遍历算法算法中中（根）序的遍（根）序的遍历算法算法后后（根）序的遍（根）序的遍历算法算法36若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍先（根）序的遍历算法：算法：A AB BC CD DF FGGE EHH37若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍中（根）序的遍历算法：算法：A AB BC CD DF FGGE EHH38若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍后（根）序的遍历算法：算法：A AB BC CD DF FGGE EHH39ABCDEFGHA先序遍历：ABCDEFGHB D C E G H FB中序遍历：D A G E H C FD后序遍历：B G H E F C A二叉树遍历的输出顺序示例演示40NULLNULLNULLNULLNULLNULLNULLNULLNULLABCDEFGH先序遍历：中序遍历：后序遍历：ABDB D C E G H FD A G E H C FB G H E F C A二叉树遍历过程的示例演示41二、遍二、遍历算法描述算法描述u 先序（前序）遍历二叉树的递归算法u 中序遍历二叉树的递归算法u 后序遍历二叉树的递归算法42先序遍先序遍历二叉二叉树的的递归算法算法void preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点 preorder(T-lchild,visit);/遍历左子树 preorder(T-rchild,visit);/遍历右子树 43void inorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树 if(T)inorder(T-lchild,visit);/遍历左子树 visit(T-data);/访问结点 inorder(T-rchild,visit);/遍历右子树 中序遍中序遍历二叉二叉树的的递归算法算法44void postorder(BiTree T,void(*visit)(TElemType&e)/后序遍历二叉树 if(T)postorder(T-lchild,visit);/遍历左子树 postorder(T-rchild,visit);/遍历右子树 visit(T-data);/访问结点 后序遍后序遍历二叉二叉树的的递归算法算法中序遍中序遍历算法的非算法的非递归描述描述void Inorder_I(BiTree T,void(*visit)(TelemType&e)Stack*S;t=GoFarLeft(T,S);/找到最左下的结点 while(t)visit(t-data);if(t-rchild)else if(!StackEmpty(S)t=Pop(S);/退栈 else t=NULL;/栈空表明遍历结束 /while/Inorder_I t=GoFarLeft(t-rchild,S);BiTNode*GoFarLeft(BiTree T,Stack*S)if(!T)return NULL;while(T-lchild)Push(S,T);T=T-lchild;return T;48三、遍三、遍历算法算法应用用举例例1、统计二叉树中叶子结点的个数 (先序遍历)2、求二叉树的深度(后序遍历)3、复制二叉树(后序遍历)4、建立二叉树的存储结构491、统计二叉二叉树中叶子中叶子结点的个数点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍需在遍历算法中增添一个算法中增添一个“计数数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，若是叶子，则计数器增数器增1。50void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);/if/CountLeaf512.求二叉求二叉树的深度的深度(后序遍后序遍历)算法基本思想算法基本思想:从二叉树深度的定义可知，二叉二叉树的深度的深度应为其左、右子其左、右子树深度的最大深度的最大值加加1。由此，需先分需先分别求得左、右子求得左、右子树的深度，的深度，算法中“访问结点”的操作为：求得左、右子求得左、右子树深度深度的最大的最大值，然后加，然后加 1。首先分析二叉二叉树的深度的深度和它的左左、右子右子树深度深度之间的关系。52int Depth(BiTree T)/返回二叉树的深度 if(!T)depthval=0;else depthLeft =Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;533、复制二叉、复制二叉树(后序遍后序遍历)核心操作：生成一个根结点,并链接 左右子树根元素根元素T根元素根元素NEWT递归操作：完成左右子树的复制54BiTNode*CopyTree(BiTNode*T)if(!T)return NULL;if(T-lchild)newlptr=CopyTree(T-lchild);/复制左子树 else newlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/复制右子树 else newrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);return newT;/CopyTree55BiTNode*GetTreeNode(TElemType item,BiTNode*lptr,BiTNode*rptr)if(!(T=new BiTNode)exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;return T;生成一个二叉生成一个二叉树的的结点的操作算法：点的操作算法：(其数据域为item,左指针域为lptr,右指针域为rptr)56ABCDEFGHK D C H K G F E A例如：下列二叉例如：下列二叉树的复制的复制过程如下：程如下：B newTT574、建立二叉树的存储结构、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法。以下建立以二叉链表表示的存储结构。从输入的字符串建立二叉树由前序前序和中序中序的序列建立二叉树58 以字符串的形式以字符串的形式 根根 左子左子树 右子右子树定定义一棵二叉一棵二叉树例如例如:ABCD以空白字符“”表示A(B(,C(,),D(,)空树只含一个根结点的二叉树A以字符串“A ”表示以下列字符串表示59void CreateBiTree(BiTree&T)cinch;if(ch=)T=NULL;else if(!(T=new BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 /CreateBiTree60A B C D A BCD上页算法执行过程举例如下：ATBCD61 仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉由二叉树的先序和中序序列建的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列 左子左子树左子左子树 右子右子树右子右子树根根根根62a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列中序序列63preinopsps+n-1isis+n-1prepskps+1k-isps+1+(k-is)k+1n-(k-is)-1子树序列下标位置的确定64void CrtBT(BiTree&T,char pre,char ino,int ps,int is,int n)/已知preps.ps+n-1为二叉树的先序序列，/insis.is+n-1为二叉树的中序序列，/本算法由此两个序列构造二叉链表 if(n=0)T=NULL;else k=Search(ino,preps);/在中序序列中查询 if(k=-1)T=NULL;else /递归程序段 /CrtBT 65T=new BiTNode;T-data=preps;if(k=is)T-Lchild=NULL;else CrtBT(T-Lchild,pre,ino,ps+1,is,k-is);if(k=is+n-1)T-Rchild=NULL;else CrtBT(T-Rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);递归语句程序段：66四、线索二叉树四、线索二叉树一、何一、何谓线索二叉索二叉树？二、二、线索索链表的遍表的遍历算法算法三、如何建立三、如何建立线索索链表？表？67一、何谓线索二叉树？一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列，例如:先序先序序列:A B D E G H C F I J中序中序序列:D B G E H A C I J F后序后序序列:D G H E B J I F C A68 遍历引起的思考：遍历二叉树把非线性结构以序列的形式加以“线性化”了，那么u 所得序列信息可否长期利用？u 信息保持可否尽量少占用额外的存储空间？u 是否能否形成一般化的方法？处理办法：在遍历时，串联起前驱、后继的关系链，以备后期的再利用。69 指向该线性序列中的“前驱”和“后继”的指针指针，称作“线索线索”D B G E H A C I J F 以中序为例,看结点H的前驱线索和后继线索ABCFDGEH IJ的前驱线索H的后继线索H70 与其相应的二叉树，称作“线索线索二叉树二叉树”包含“线索”的存储结构，称作“线索链表线索链表”按“序”来讲，可分成：“先序线索二叉树线索二叉树”、“中序线索线索二叉树二叉树”和“后序线索二叉树线索二叉树”71typedef struct BiThrNode TElemType data;struct BiThrNode*lchild,rchild;struct BiThrNode*pred,succ;/前驱、后继线索 BiThrNode,*BiThrTree;线索二叉索二叉树的的类型定型定义：72HABCDEGHFIJT中序线索化二叉树示例73DBGEHACIJF线索关系表现为双向循环链表查找前驱和后继变得异常容易74 遍历带有线索的二叉树，既无需重新递归遍历，也无需栈的协助，只进行相当“线性性结构构”的寻访即可，而且可正反双向进行。二、二、线索索链表的遍表的遍历算法算法:75void InOrder(BiThrTree H,void(*visit)(BiTree)/H为指向中序线索链表中头结点的指针 p=H-succ;while(p!=H)visit(p);p=p-succ;76更好的办法？充分利用现有节点中的空余指针线索二叉树（利用多余指针）线索二叉树（利用多余指针）v提出问题提出问题w在在n 个结点的二叉树中总共有个结点的二叉树中总共有2*n个链接，但有个链接，但有(n+1)个个为空链接为空链接有人提出一个利用这有人提出一个利用这些空链接的方法。些空链接的方法。将这些空链接用指向将这些空链接用指向树中其他结点的指针树中其他结点的指针代替，这些指针被称代替，这些指针被称为为线索线索。12345678910111213141577线索二叉树线索二叉树bacdefghi12345678978对线索索链表表中中结点的点的约定：定：在二叉链表的结点中增加两个增加两个标志域志域，并作如下规定：若若该结点的左子点的左子树不空不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针 Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread”。若若该结点的右子点的右子树不空不空，则rchild域的指针指向其右子树，且右标志域的值为“指针 Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”。如此定如此定义的二叉的二叉树的存的存储结构称作构称作“线索索链表表”typedef struct BiThrNod TElemType data;struct BiThrNode *lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;线索链表的类型描述：typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索二、二、线索索链表的遍表的遍历算法算法:for(p=firstNode(T);p;p=Succ(p)Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如例如:对中序中序线索化索化链表的遍表的遍历算法算法 中序遍历的第一个结点中序遍历的第一个结点？在中序线索化链表中结点的后继在中序线索化链表中结点的后继？左子树上处于“最左下最左下”（没有左子树）的结点若若无右子树，则为后后继线索索所指结点否否则为对其右子右子树进行中序遍遍历时访问的第一个第一个结点点void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType e)p=T-lchild;/p指向根结点 while(p!=T)/空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;/第一个结点 if(!visit(p-data)return ERROR;/访问其左子树为空的节点 while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;/p进至其右子树根 /InOrderTraverse_Thr 在中序遍在中序遍历过程中修改程中修改结点的点的左、右指左、右指针域，以保存当前域，以保存当前访问结点的点的“前前驱”和和“后后继”信息。遍信息。遍历过程中，附程中，附设指指针pre,并始并始终保持指保持指针pre指向当前指向当前访问的、指的、指针p所指所指结点的前点的前驱。三、如何建立三、如何建立线索索链表？表？线索二叉树线索二叉树v两个悬挂的线索两个悬挂的线索w结点H的leftChild二叉树的头结点w结点G的rightChild二叉树的头结点v解决悬挂的线索解决悬挂的线索w为所有的线索二叉树为所有的线索二叉树设置一个头结点，原来的二叉树的头设置一个头结点，原来的二叉树的头结点结点为该新头结点的为该新头结点的左子树左子树。w一棵带一棵带头结点头结点的空二叉树如下：的空二叉树如下：w下图展示了线索二叉树在内存中的表示下图展示了线索二叉树在内存中的表示leftThreadleftChildDatarightChildrightThreadtruefalse86线索二叉树线索二叉树v内存表示内存表示rootleftThreadleftChildDatarightChildrightThreadtruefalse87void InThreading(BiThrTree p)if(p)/对以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);/右子树线索化 /if/InThreadingStatus InOrderThreading(BiThrTree&Thrt,BiThrTree T)/构建中序线索链表 if(!(Thrt=new BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;/添加头结点 return OK;/InOrderThreading if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点 pre-RTag=Thread;Thrt-rchild=pre;916.3 树和森林树和森林一、一、树和森林的定和森林的定义二、二、树和森林的存和森林的存储结构构三、三、树和森林的遍和森林的遍历92一、树和森林的定义一、树和森林的定义93 树的定的定义：树是n（n0）个元素的有限集D，若D为空集，则为空树。否则：(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不 相交的有限集T1,T2,Tm，其中每一棵 子集本身又是一棵符合本定义的树，称为 根root的子树。94树的基本操作：的基本操作：v 查 找找 类 的的 操操 作作v 插插 入入 类 的的 操操 作作v 删 除除 类 的的 操操 作作95Root(T)/求树的根结点 查找找类的操作：的操作：Value(T,cur_e)/求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树 TreeDepth(T)/求树的深度TraverseTree(T)/遍历96InitTree(&T)/初始化置空树 插入插入类的操作：的操作：CreateTree(&T,definition)/按定义构造树Assign(T,cur_e,value)/给当前结点赋值InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树97 ClearTree(&T)/将树清空 删除除类的操作：的操作：DestroyTree(&T)/销毁树的结构DeleteChild(&T,&p,i)/删除结点p的第i棵子树98ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根根例如例如:99()有确定的根；()树根和子树根之间为有向关系。有向有向树：有序有序树：子树之间存在确定的次序关系。无序无序树：子树之间不存在确定的次序关系。100任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootCGDHIJMFBEFKL101二、二、树和森林的存和森林的存储结构构1.双亲表示法2.孩子链表表示法3.树的二叉链表(孩子-兄弟）存储表示法102ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent1.双双亲表示法表示法:103 typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;data parent#define MAX_TREE_SIZE 100结点点结构构:C语言的言的类型描述型描述:104typedef struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;树结构构:105r=0n=7 data firstchild0 A -11 B 02 C 03 D 04 E 25 F 26 G 564 5 1 2 32.孩子孩子链表表示法表表示法:ABCDEFG106typedef struct CTNode int child;struct CTNode*next;*ChildPtr;孩子孩子结点点结构构:child nextC语言的言的类型描述型描述:107 typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;双双亲结点点结构构 data firstchild108typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;树结构构:109 AB C E D F G 3.树的二叉的二叉链表表(孩子孩子-兄弟）存兄弟）存储表示法表示法ABCDEFGrootABCDEFG110typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;C语言的言的类型描述型描述:结点点结构构:firstchild data nextsibling111 森林和二叉森林和二叉树的的对应关系关系设森林森林 F=(T1,T2,Tn);T1=(root，t11,t12,t1m);二叉二叉树 B=(LBT,Node(root),RBT);112由森林由森林转换成二叉成二叉树的转换规则为:若 F=，则 B=；否则，由 ROOT(T1)对应得到 Node(root)；由(t11,t12,t1m)对应得到 LBT；由(T2,T3,Tn)对应得到 RBT。113由二叉由二叉树转换为森林森林的转换规则为：若 B=，则 F=；否则，由 Node(root)对应得到 ROOT(T1)；由LBT 对应得到(t11,t12,，t1m)；由RBT 对应得到(T2,T3,Tn)。114 由此，树的各种操作均可对应二叉树的操作来完成。应当注意的是，当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。左是孩子，右是兄弟。115三、树和森林的遍历三、树和森林的遍历1.树的遍的遍历2.森林的遍森林的遍历3.树的遍的遍历的的应用用1161.树的遍的遍历(可有三条搜索路径可有三条搜索路径):按按层次遍次遍历:先根先根(次序次序)遍遍历:后根后根(次序次序)遍遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。117 A B C DE F G H I J K 先根遍先根遍历时顶点的访问次序：A B E F C D G H I J K 后根遍后根遍历时顶点的访问次序：E F B C I J K H G D A 层次遍次遍历时顶点的访问次序：A B C D E F G H I J K1182森林中第一棵树的子树森林；1森林中第一棵树的根结点；B C DE F G H I J K3森林中其它树构成的森林。森林由三部分构成：2.森林的遍森林的遍历119 先序遍先序遍历 即：依次从左至右依次从左至右对森林中的每一棵树进行先根遍先根遍历。若森林不空，则访问森林中第一棵树的根结点；先序遍先序遍历森林中第一棵树的子树森林；先序遍先序遍历森林中(除第一棵树之外)其 余树构成的森林。120中序遍中序遍历 若森林不空，则中序遍中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍中序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树进行后根遍后根遍历。121 树的遍的遍历和二叉和二叉树遍遍历的的对应关系？关系？先根遍先根遍历后根遍后根遍历树二叉二叉树森林森林先序遍先序遍历先序遍先序遍历中序遍中序遍历中序遍中序遍历122(设树的存储结构为孩子兄弟链表)typedef struct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;v 求求树的深度的深度v 输出出树中所有从根到叶子的路径中所有从根到叶子的路径v 建建树的存的存储结构构3.树的遍的遍历的的应用用123int TreeDepth(CSTree T)if(!T)return 0;else h1=TreeDepth(T-firstchild);h2=TreeDepth(T-nextsibling);/TreeDepthreturn(max(h1+1,h2);v 求求树的深度的算法：的深度的算法：124ABCDABCD求树深算法的理解(max(h1+1,h2)的图解 125v 输出出树中所有从根到叶子的路径的算法中所有从根到叶子的路径的算法:例如：对左图所示的树，其输出结果应为：A B EA B FA CA D G H IA D G H JA D G H K A B C DE F G H I J K126void AllPath(Bitree T,Stack&S)if(T)Push(S,T-data);if(!T-Lchild&!T-Rchild)PrintStack(S);else AllPath(T-Lchild,S);AllPath(T-Rchild,S);Pop(S);/if(T)/AllPath/输出二叉树上从根到所有叶子结点的路径127ABCDEFGHABA-B-D-FDF GA-B-D-GCEHA-C-E-H输出二叉树上从根到所有叶子结点的路径演示128 A B C DE F G H I J KA B EA B FA CA D G H IA D G H JA D G H K输出树中所有从根到叶子的路径如何判定叶子？如何判定叶子？129void OutPath(Bitree T,Stack&S)while(!T)Push(S,T-data);if(!T-firstchild)Printstack(s);else OutPath(T-firstchild,s);Pop(S);T=T-nextsibling;/while/OutPath/输出森林中所有从根到叶的路径130v 建建树的存的存储结构的算法构的算法:和二叉树类似，不同的定义相应有不同的算法。假设以二元组(F，C)的形式自上而下自上而下、自左而右自左而右依次输入树的各边，建立树的孩子孩子-兄弟兄弟链表表。131ABCDEFG例如例如:对下列所示树的输入序列应为:(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)(E,G)ABCD(#,A)(A,B)(A,C)(A,D)(C,E)算法中需要一个队列列保存已建好的结点的指指针。132void CreatTree(CSTree&T)T=NULL;for(scanf(&fa,&ch);ch!=#;scanf(&fa,&ch);)p=GetTreeNode(ch);/创建结点EnQueue(Q,p);/指针入队列if(fa=#)T=p;/所建为根结点 else /非根结点的情况 /for/CreateTree 133GetHead(Q,s);/取队列头元素(指针值)while(s-data!=fa)/查询双亲结点 DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;r=p;/链接第一个孩子结点else r-nextsibling=p;r=p;/链接其它孩子结点 非根结点的情况的代码段：134 6.4 树的树的应用应用 一、堆排序的一、堆排序的实现二、二叉排序二、二叉排序树三、赫夫曼三、赫夫曼树及其及其应用用135三、赫夫曼树及其应用三、赫夫曼树