前面我们学习的线性数据结构完美版资料.ppt

前面我们学习的线性数据结构，每个前面我们学习的线性数据结构，每个元素都有唯一的前驱（第一个除外）和后元素都有唯一的前驱（第一个除外）和后继（最后一个除外），但是在现实应用中，继（最后一个除外），但是在现实应用中，一些问题的数据元素之间的关系就不这样一些问题的数据元素之间的关系就不这样简单，例如元素有多个前驱、多个后继。简单，例如元素有多个前驱、多个后继。本章学习一种非线性数据结构一树，数本章学习一种非线性数据结构一树，数据元素之间是一种层次关系，元素有且只据元素之间是一种层次关系，元素有且只有一个前驱，但可以有多个后继。有一个前驱，但可以有多个后继。第六章第六章树和二叉树树和二叉树树的概念和基本术语二叉树 二叉树遍历线索二叉树树与森林霍夫曼树 第六章第六章树和二叉树树和二叉树6.1树的概念和基本术语树的概念和基本术语树的定义树的定义树是由树是由n(n 0)个结点的有限集合。如个结点的有限集合。如果果n=0，称为空树；如果，称为空树；如果n0，则，则有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的的结点，它只有直接后继，但没有直接前驱；结点，它只有直接后继，但没有直接前驱；当当n1，除根以外的其它结点划分为除根以外的其它结点划分为m(m0)个互不相交的有限集个互不相交的有限集T1,T2,Tm，其中每个集合本身又是一棵树，并且称其中每个集合本身又是一棵树，并且称为根的子树为根的子树(SubTree)。ACGBDEFKLHMIJ例如例如A只有根结点的树只有根结点的树有有13个结点的树个结点的树其中其中:A是根是根,其余结点分成三个互不相交的子集，其余结点分成三个互不相交的子集，T1=B,E,F,K,L；T2=C,G；T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子树，且本身也是一棵树的子树，且本身也是一棵树树的基本术语树的基本术语树的结点树的结点：包含一个数据元素及若干指向子树的：包含一个数据元素及若干指向子树的分支；分支；孩子结点孩子结点：结点的子树的根称为该结点的孩子：结点的子树的根称为该结点的孩子双亲结点双亲结点：B结点是结点是A结点的孩子，则结点的孩子，则A结点是结点是B结点的双亲；结点的双亲；兄弟结点兄弟结点：同一双亲的孩子：同一双亲的孩子结点；结点；堂兄结点堂兄结点：双亲在同一层的：双亲在同一层的结点互为堂兄弟。结点互为堂兄弟。结点层结点层：根结点的层定义为：根结点的层定义为1；根的孩子为第二层结点，；根的孩子为第二层结点，依此类推；依此类推；ACGBDEFKLHMIJ 树的高度树的高度：树中结点的最大层次：树中结点的最大层次.结点的度结点的度：结点子树的个数：结点子树的个数树的度树的度：树内各结点的度的最大值。树内各结点的度的最大值。叶子结点叶子结点：也叫终端结点，是度为：也叫终端结点，是度为0的结点；的结点；分枝结点分枝结点：度不为：度不为0的结点；的结点；有序树有序树：子树有序的树，（子树不能互换）如：子树有序的树，（子树不能互换）如：家族树；家族树；无序树无序树：不考虑子树的顺序；：不考虑子树的顺序；ACGBDEFKLHMIJ任何一棵非空树是一个二元组Tree=（root，F）其中：root 被称为根结点，F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBEFKLCGDHIJMF路径：路径：树中的树中的k 个结点个结点n1,n2，nk，满，满足足ni 是是ni+1 的双亲，的双亲，n1到到nk有一条路径有一条路径路径长度：路径长度：分支数路径上结点个数一分支数路径上结点个数一1 根没有双亲，叶子没有孩子；根没有双亲，叶子没有孩子；vi是是vj的双亲，则的双亲，则L(vi)=L(vj)-1;堂兄弟的双亲是兄弟关系吗？堂兄弟的双亲是兄弟关系吗？有序树和无序树的区别；有序树和无序树的区别；注意注意ACGBDEFKLHMIJ对比树型结构和线性结构的结构特点对比树型结构和线性结构的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)树的常见表示方法树的常见表示方法1.直观表示法直观表示法：用圆圈表示结点，元素写在：用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系圆圈中，连线表示元素之间的关系.根在上，根在上，叶子在下（即树向下生长）叶子在下（即树向下生长）2、集合表示法：、集合表示法：根据树的集合定义，写出集合划分。根据树的集合定义，写出集合划分。3、文氏图表示法：、文氏图表示法：集合表示的一种直观表示，用图表示集合。集合表示的一种直观表示，用图表示集合。4、目录表示法：、目录表示法：将一棵树描述为一本书，书将一棵树描述为一本书，书-章章-节节-小小节节5、广义表表示法：、广义表表示法：将一棵树描述为一个广义表，子树就对应子将一棵树描述为一个广义表，子树就对应子表。表。人们最常用的是第一种，但是不适合计算机！人们最常用的是第一种，但是不适合计算机！树的基本操作树的基本操作InitTree（T）；）；操作结果：构造空树操作结果：构造空树T。DestroyTree（T）；）；初始条件：树初始条件：树T存在。存在。操作结果：销毁树操作结果：销毁树T。CreateTree（T，definition）初始条件：初始条件：definition给出树给出树T的定义。的定义。操作结果：按操作结果：按definition构造树构造树T。ClearTree（T）；）；初始条件：树初始条件：树T存在。存在。操作结果：将树操作结果：将树T清为空树。清为空树。TreeEmpty（T）初始条件：树初始条件：树T存在。存在。操操作作结结果果：若若T为为空空树树，则则返返回回ture，否否则则false。TreeDepth（T）初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的深度。的深度。Root（T）初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的根。的根。Value（T,Cur_e）初初始始条条件件：树树T存存在在，cure是是T中中某某个结点。个结点。操作结果：返回操作结果：返回cure的值。的值。Assign（T，cur_e，value）初始条件：树初始条件：树T存在，存在，cure是是T中某个结点。中某个结点。操作结果：结点操作结果：结点cur_e赋值赋值为为value。Parent（T，cure）初始条件：树初始条件：树T存在，存在，cure是是T中某个结点。中某个结点。操操作作结结果果：若若cure是是T的的非非根根结结点点，则则返返回回它的双亲，否则函数值为它的双亲，否则函数值为“空空”。Rightsibling（T，cure）初始条件：树初始条件：树T存在，存在，cure是是T中某个结点中某个结点操操作作结结果果：若若cure有有右右兄兄弟弟，则则返返回回它它的的右右兄弟，否则函数值为兄弟，否则函数值为“空空”。InsertChild（T，p，i，c）；）；初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip所所指结点的度指结点的度1，非空树，非空树c与与T不相交。不相交。操作结果：插入操作结果：插入c为为T中中p指结点的第指结点的第i棵子树。棵子树。DeleteChild（T，p，i）；）；初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip指指结点的度。结点的度。操作结果：删除操作结果：删除T中中p所指结点的第所指结点的第i棵子树。棵子树。TraverseTree（T，visit（）；（）；初始条件：树初始条件：树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：按某种次序对操作结果：按某种次序对T的每个结点调用函数的每个结点调用函数visit()一次且至多一次一次且至多一次.一旦一旦visit（）失败，则操作失败（）失败，则操作失败LeftChild（T，cure）初始条件：树初始条件：树T存在，存在，cure是是T中某个结点。中某个结点。操作结果：若操作结果：若cure是是T的非叶子结点，则返回它的的非叶子结点，则返回它的最左孩子，否则返回最左孩子，否则返回“空空”。6.2 6.2 二叉树二叉树一一 二叉树的概念二叉树的概念二二 二叉树的性质二叉树的性质三三 二叉树的存储结构二叉树的存储结构定义定义:二叉树或为空树空树；或是由一个根根结点结点加上两棵两棵分别称为左子树左子树和右子树的、互不相交的互不相交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树6.2二叉树二叉树(BinaryTree)特点特点:每个结点至多只每个结点至多只有两棵子树（二叉树中有两棵子树（二叉树中不存在度大于不存在度大于2的结点）的结点）二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树应用举例应用举例例例可以用二叉树表示表达式可以用二叉树表示表达式 e e d d c c b b f f a a +*/-a+b*(c-d)-e/f a+b*(c-d)-e/f性质性质1在二叉树的第在二叉树的第i 层上至多有层上至多有2i 1个结点。个结点。(i 1)证明用归纳法证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2i-1=20=1。假设对所有假设对所有j，ij 1，命题成立，即第，命题成立，即第j层层上至多有上至多有2j-1个结点。个结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有2i 2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在，故在第第i层上的最大结点数为第层上的最大结点数为第i-1层上的最大结层上的最大结点数的点数的2倍，即倍，即2*2i 2=2i-1。性质性质性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k-1个结点个结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的的二叉树的最大结点数为最大结点数为 20+21+2k-1=2k-1定义2 完全二叉树(Complete Binary Tree)则总编码长度为(2+7+4+5)*2=36.中序遍历序列：D,B,G,E,A,C,F/T指向头结点，头结点的左链lchild指向根结点，D E F Int n,r;/结点数和根的位置；CTBox nodesMAX_TREE_SIZE;证明：由性质1可见，深度为k的二叉树的最大结点数为2）若有右孩子，则有孩子结点编号为2i+1；TreeData data;孩子结点：结点的子树的根称为该结点的孩子E 3 -1 -1比等长编码的情形要短。F 3 -1 -1初始条件：树T存在。树的后根遍历可以借助对应二叉树性质性质3对任何一棵二叉树对任何一棵二叉树T,如果其叶如果其叶结点数为结点数为n0,度为度为2的结点数为的结点数为n2,则则n0n21.证明：若度为证明：若度为1的结点有的结点有n1个，总结点个个，总结点个数为数为n，总边数为，总边数为e，则根据二叉树的定，则根据二叉树的定义，义，n=n0+n1+n2e=2n2+n1=n-1因此，有因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1定义定义1满二叉树满二叉树(FullBinaryTree)一棵深度为一棵深度为k且有且有2k-1个结点的二叉树个结点的二叉树称为满二叉树。称为满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二叉树非完全二叉树定义定义2完全二叉树完全二叉树(CompleteBinaryTree)若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除第层。除第h层外，其它各层层外，其它各层(0 h-1)的结点数都达到最大的结点数都达到最大个数，第个数，第h层层从右向左从右向左连续缺若干结点，这就连续缺若干结点，这就是完全二叉树。是完全二叉树。621754389 10 11 12完全二叉树完全二叉树a+b*(c-d)-e/fD 1 4 5若二叉树非空（1）中序遍历左子树（2）访问根结点或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。孩子结点：结点的子树的根称为该结点的孩子常见的二叉树结点结构如下所示：树后根遍历 EFBCGDA操作结果：若cure有右兄弟，则返回它的右兄弟，否则函数值为“空”。性质2 深度为 k 的二叉树至多有 2 k-1个结点(k 1)。总编码长度正好等于霍夫初始条件：树T存在。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。二叉树由根、左子树、右子树三部分组成取对数 h1 rchild,Visit);/InOrderTraverse性质性质4 具有具有n(n 0)个结点的完全二叉树个结点的完全二叉树的深度为的深度为 log2(n)1证明：证明：设完全二叉树的深度为设完全二叉树的深度为h，则根据性，则根据性质质2和完全二叉树的定义有和完全二叉树的定义有2h1-1n 2h-1或或2h1 n2h取对数取对数h10,则则i的双亲为的双亲为(i-1)/2 n若若2*i+1n,则则i的左子女为的左子女为2*i+1，若若2*i+2data)；PreOrderTraverse(T-lchild,Visit);PreOrderTraverse(T-rchild,Visit);/PreOrderTraverse最简单的最简单的Visit函数是：函数是：StatusPrintElement(TElemTypee)/输出元素输出元素e的值的值printf(e);returnOK;2中序遍历递归算法中序遍历递归算法voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，visit()是访问结点的是访问结点的/数。本算法中序遍历以为根结点指针的二叉树，数。本算法中序遍历以为根结点指针的二叉树，/对每个数据元素调用函数对每个数据元素调用函数Visit()if(T)/若二叉树为空，结束返回若二叉树为空，结束返回/若二叉树不为空，遍历左子树，访问根结点，若二叉树不为空，遍历左子树，访问根结点，/遍历右子树遍历右子树InOrderTraverse(T-lchild,Visit);Visit(T-data)；InOrderTraverse(T-rchild,Visit);/InOrderTraverse3后序遍历递归算法后序遍历递归算法voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，visit()是访问结点是访问结点的的/函数。本算法中序遍历以为根结点指针的二叉函数。本算法中序遍历以为根结点指针的二叉/树，对每个数据元素调用函数树，对每个数据元素调用函数Visit()if(T)/若二叉树为空，结束返回若二叉树为空，结束返回/若二叉树不为空，遍历左子树，遍历右子树，若二叉树不为空，遍历左子树，遍历右子树，/访问根结点访问根结点PostOrderTraverse(T-lchild,Visit);PostOrderTraverse(T-rchild,Visit);Visit(T-data)；/PostOrderTraverse例例:已知一棵二叉树的中根序列和先根序列分别为已知一棵二叉树的中根序列和先根序列分别为ABCDEFGHIJK和和EBADCFHGIKJ，试画出这棵二叉树。，试画出这棵二叉树。4.中序遍历二叉树中序遍历二叉树(非递归算法非递归算法)用栈实现用栈实现baabcdeadaaab入栈入栈b退栈退栈访问访问d入栈入栈d退栈退栈访问访问e 退栈退栈访问访问ecc栈空栈空a退栈退栈访问访问c e入栈入栈c 退栈退栈访问访问 voidInOrder(BinTreeT)stackS;InitStack(&S);/递归工作栈递归工作栈BinTreeNode*p=T;/初始化初始化while(p!=NULL|!StackEmpty(&S)if(p!=NULL)Push(&S,p);p=p-leftChild;elsePop(&S,p);/退栈退栈printf(p-data);/访问根访问根p=p-rightChild;/if/whilereturnok;abcde1线索二叉树线索二叉树遍历是二叉树最基本最常用的操作。遍历是二叉树最基本最常用的操作。21）对二叉树所有结点做某种处理可在遍历过）对二叉树所有结点做某种处理可在遍历过程中实现程中实现;32）查找二叉树某个结点，可通过遍历实现；）查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：与线性表相比，对二叉树的遍历存在如下问题：1）遍历算法要复杂的多，费时的多；）遍历算法要复杂的多，费时的多；2）为检索或查找二叉树中某结点在某种遍历下的）为检索或查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继，必须从根开始遍历，直到找到该结点及后继；后继；如果能将二叉树线性化，就可以减化遍历算法，如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。提高遍历速度。5.4线索二叉树线索二叉树(ThreadedBinaryTree)如何将二叉树线性化？如何将二叉树线性化？以中序遍历为例，我们看到通过遍历以中序遍历为例，我们看到通过遍历可以得到二叉树结点的中序序列。若能可以得到二叉树结点的中序序列。若能将中序序列中每个结点前趋、后继信息将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二根据所保存的结点前趋、后继信息对二叉树进行遍历。叉树进行遍历。加上结点前趋后继信息（线索）的二叉树加上结点前趋后继信息（线索）的二叉树称为称为线索二叉树线索二叉树中序遍历序列：中序遍历序列：D,B,H,E,A,F,C,GD,B,H,E,A,F,C,G在中序序列中，在中序序列中，D D的后继是的后继是B B，H H的前趋是的前趋是B B，后继是，后继是EE加上结点前趋后继信息（结索）的二叉树称为加上结点前趋后继信息（结索）的二叉树称为线索二叉树线索二叉树 A A G G H H E E D D C C B B F F线索二叉树孩子指针孩子指针前趋指针前趋指针后继指针后继指针2线索链表线索链表线索二叉树的存贮方法：线索二叉树的存贮方法：1）为每个结点增加二个标志域。为每个结点增加二个标志域。缺点：要点用较多的内存空间。缺点：要点用较多的内存空间。有有n个结点的二叉链表，有个结点的二叉链表，有n+1个空指针域个空指针域,故故可利用这些的空指针域存放结点的前趋和后继指针，可利用这些的空指针域存放结点的前趋和后继指针，以这种结点的构成二叉链表称为线索链表以这种结点的构成二叉链表称为线索链表T T D D A A B B C C F F H H E E G G 对线索链表中结点的约定：对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，在二叉链表的结点中增加两个标志域，并作如下规定：并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则则LchildLchild域的指针指向其左子树，域的指针指向其左子树，且左标志域的值为且左标志域的值为“指针指针 Link”Link”；否则，否则，LchildLchild域的指针指向其域的指针指向其“前驱前驱”，且左标志的值为且左标志的值为“线索线索 Thread”Thread”。若该结点的右子树不空，若该结点的右子树不空，则则rchildrchild域的指针指向其右子树，域的指针指向其右子树，且右标志域的值为且右标志域的值为“指针指针 Link”Link”；否则，否则，rchildrchild域的指针指向其域的指针指向其“后继后继”，且右标志的值为且右标志的值为“线索线索 Thread”Thread”。Ltag=0,lchild为左子女指针为左子女指针Ltag=1,lchild为前驱线索为前驱线索Rtag=0,rchild为右子女指针为右子女指针Rtag=1,rchild为后继指针为后继指针结点结构结点结构lchildlchildrchildrchilddatadataLtagRtag线索链表的类型说明线索链表的类型说明typedefenumlink,threadPointerTag;/link=0,thread=1typedefstructBiThrNodeTElemTypedata;StructBiThrNode*lchild,*rchild;/左右指针域左右指针域PointerTagLtag,Rtag;/左右标志域，左右标志域，标志域为标志域为0时表示左右指针域存储的是左右时表示左右指针域存储的是左右孩子的指针，标志域为孩子的指针，标志域为1时表示左右指针域时表示左右指针域存储的是前趋后继结点的指针存储的是前趋后继结点的指针BiThrNode，*BiThrTreeF F1 11 1E E0 01 1G G1 10 0D D0 01 1A A0 00 0B B0 00 0H H1 11 1C C0 00 0线索链表图示线索链表图示线索二叉树 A A G G H H E E D D C C B B F F孩子指针孩子指针前趋指针前趋指针后继指针后继指针中序遍历序列：中序遍历序列：D,B,H,E,A,F,C,G为简化线索链表的遍历算法，仿照线性链表，为线为简化线索链表的遍历算法，仿照线性链表，为线索链表加上索链表加上一头结点一头结点.约定：约定：F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0H H1 11 1C C0 00 00 01 1头结点头结点头结点的头结点的lchildlchild域：存放线索链表的根结点指针域：存放线索链表的根结点指针头结点的头结点的rchildrchild域域:中序序列最后一个结点指针中序序列最后一个结点指针中序序列第一结点中序序列第一结点lchildlchild域指向头结点域指向头结点;中序序列最后一个结点的中序序列最后一个结点的rchildrchild域指向头结点域指向头结点;如图标出的中序二叉树结点的顺序，可看出如图标出的中序二叉树结点的顺序，可看出1）中序序列的第一结点，是二叉树的最左下结点；）中序序列的第一结点，是二叉树的最左下结点；2）若）若p所指结点的右孩子域为线索，则所指结点的右孩子域为线索，则p的右孩子结点即的右孩子结点即为后继结点；为后继结点；3）若）若p所指结点的右孩子域为孩子指针，则所指结点的右孩子域为孩子指针，则p的后继结点的后继结点为其右子树的最左下结点；为其右子树的最左下结点；F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0H H1 11 1C C0 00 00 01 1头结点中序遍历序列：D,B,H,E,A,F,C,G3线索二叉树的遍历线索二叉树的遍历在二叉树上加上结点前趋、后继线索后，可利用在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历。线索对二叉树进行遍历。基本步骤：基本步骤：1）p=T-lchild;p指向线索链表的根结点；指向线索链表的根结点；2）若线索链表非空，循环：若线索链表非空，循环：（a）循环，顺着）循环，顺着p左孩子指针找到最左下结点；访问左孩子指针找到最左下结点；访问之之（b）若）若p所指结点的右孩子域为线索，所指结点的右孩子域为线索，p的右孩子结点的右孩子结点即为后继结点循环：即为后继结点循环：p=p-rchild；并访问并访问p所指结点；所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）（在此循环中，顺着后继线索访问二叉树中的结点）（c）一旦线索一旦线索“中断中断”，p所指结点的右孩子域为右孩所指结点的右孩子域为右孩子指针，子指针，p=p-rchild，使，使p指向右孩子结点；指向右孩子结点；3）返回返回OK；结束；结束线索链表的遍历算法线索链表的遍历算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)/T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，指向根结点，/中序遍历二叉线索树中序遍历二叉线索树T T算法，对每个数据元素调用函数算法，对每个数据元素调用函数VisitVisit。P=T-lchild;/p指向根结点指向根结点While(p!=T)/空树或遍历结束时，空树或遍历结束时，p=Tp=TWhile(p-Ltag=Link)p=p-lchild;/找到最左下结点；访问之找到最左下结点；访问之Visit(p-data)while(p-Rtag=Thread&p-rchild!=T)/若若p所指结点的右孩子域为线索且不是最后一个结点所指结点的右孩子域为线索且不是最后一个结点p=p-rchild;Visit(p-data);/访问后继结点访问后继结点p=p-rchild;returnOK;/InOrderTraverse_Thrq树的存储结构树的存储结构在树中，每个结点即可能有在树中，每个结点即可能有孩子也可能有双亲，所以既可以通过保存每孩子也可能有双亲，所以既可以通过保存每个结点的孩子结点位置来表示结点之间的结个结点的孩子结点位置来表示结点之间的结构关系，也可以通过保存每个结点的双亲结构关系，也可以通过保存每个结点的双亲结点位置来表示结点之间的结构关系。点位置来表示结点之间的结构关系。1.1.双亲表示：双亲表示：通过保存每个结点的双亲结点通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。的位置，表示树中结点之间的结构关系。以一组连续空间存储树的结点，同时在以一组连续空间存储树的结点，同时在结结点中附设一个指针，存放双亲结点在链表中点中附设一个指针，存放双亲结点在链表中的位置。的位置。树与森林树与森林ABCDEFGdataparentABCDEFG-10001130123456*便于涉及双亲的操作；便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。求结点的孩子时需要遍历整棵树。特点特点:用双亲表示实现的树定义用双亲表示实现的树定义#defineMaxSize/最大结点个数最大结点个数typedefcharTreeData;/结点数据结点数据typedefstruct/树结点定义树结点定义TreeDatadata;intparent;/双亲位置域双亲位置域TreeNode;typedefTreeNodeTreeMaxSize;/树树2 2、孩子表示法、孩子表示法 孩子表示法：通过保存每个结点的孩子孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关结点的位置，表示树中结点之间的结构关系。系。方法一方法一:顺序顺序 存储存储#defineMAX_TREE_SIZE100typedefstructPTNodeTElemTypedata;intchild1;/第第1个孩子位置域个孩子位置域intchild2;/第第2个孩子位置域个孩子位置域.intchildd;/第第d个孩子位置域个孩子位置域PTNode;typedefstructPTNodenodesMAX_TREE_SIZE;intn;/结点数结点数PTree;孩子表示法举例孩子表示法举例RADEFCBGKH0123456789数组下标数组下标:*便于涉及孩子的操作；求双亲不方便；便于涉及孩子的操作；求双亲不方便；*采用同构的结点，空间浪费。采用同构的结点，空间浪费。R1A4B0C6D0E0F7G0H0K023500000000089000000方法二:链式存储：对树的每个结点用线性链表存贮它的孩子结点树的孩子链表类型定义树的孩子链表类型定义typedefstructCTNode/孩子结点孩子结点intchild;structCTNode*next;*ChildPtr;typedefstructTElemTypedata;ChildPtrfirstchild;/孩子链表头指针孩子链表头指针CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;Intn,r;/结点数和根的位置；结点数和根的位置；CTree;孩子链表存储表示举例孩子链表存储表示举例RADEFCBGKH0123456789数组下标数组下标:*便于涉及孩子的操作；便于涉及孩子的操作；*求结点的双亲时不方便。求结点的双亲时不方便。RAB/CD/E/FG/H/K/123/45/6/789/T.nodes;T.n=10;T.r=0;结点结构结点结构 datafirstChildnextSibling3 孩子兄弟表示法孩子兄弟表示法(二叉链表示法二叉链表示法)孩子兄弟表示法用二叉链表作为树的存贮结构typedefstructCSNodeELemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;类型定义类型定义:RADEFCBGKHR ADE C HF GBK孩子兄弟表示法示例：孩子兄弟表示法示例：树与二叉树的转换树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。作中介，可导出树与二叉树之间的转换。树与二叉树转换方法树与二叉树转换方法树树根根结点结点X X的第一个孩子的第一个孩子结点结点X X紧邻的右兄弟紧邻的右兄弟二叉树二叉树根根结点结点X X的左孩子的左孩子结点结点X X的右孩子的右孩子特点：一棵树转换成二叉树后，根结点没有右孩子。特点：一棵树转换成二叉树后，根结点没有右孩子。I IA AC CB BD DH HG GF FE E此二叉链表既是树此二叉链表既是树(a)(a)的孩子的孩子兄弟表示又是二兄弟表示又是二叉树叉树(b)(b)的二叉链表的二叉链表由此可将由此可将树与二叉树树与二叉树对应起来对应起来A AI IH HD DG GF FC CE EB BF FI IA AB BD DH HG GC CE E森林森林森林：树的集合森林：树的集合将森林中树的根看成兄弟，可用树将森林中树的根看成兄弟，可用树孩子兄弟表孩子兄弟表示法存储森林；用示法存储森林；用树与二叉树的转换方法，进行树与二叉树的转换方法，进行森森林与二叉树转换；可林与二叉树转换；可用树的遍历方法对森林进行遍用树的遍历方法对森林进行遍历；历；J J O O P P N N M M L L K KI IA AC CB BD DH HG GF FE E包含两棵树的森林包含两棵树的森林如如果果F=T1,T2,Tm是是森森林林,则则可可按按如如下下规规则转换成一棵二叉树则转换成一棵二叉树B=(root,LB,RB)。(1)若若F为空，即为空，即m=0,则则B为空树；为空树；(2)若若F非非空空，则则B的的根根root即即为为森森林林中中第第一一棵树的根棵树的根ROOT(T1)；B的的左左子子树树LB是是从从T1中中根根结结点点的的子子树树森森林林F1=T11,T12,T1m1转换而成的二叉树转换而成的二叉树;其其右右子子对对RB是是从从森森林林F=T2,T3,Tm 转换而成的二叉树转换而成的二叉树.T1T2T3AFHB C DGIJEK3 棵树的森林T1T2T3AFBCDEGHIKJ各棵树的二叉树表示ABCEDHIKJFG森林的二叉树表示q森林与二叉树的转换森林与二叉树的转换二叉树转换成森林二叉树转换成森林如如果果B=(root,LB,RB)是是一一棵棵二二叉叉树树,则则可可按按如下规则转换成森林如下规则转换成森林F=T1,T2,Tm：(1)若若B为空，则为空，则F为空；为空；(2)若若B非非空空，则则F中中第第一一棵棵树树T1的的根根ROOT(T1)即为二叉树即为二叉树B的根的根root；T1中中的的根根结结点点的的子子树树森森林林F1是是由由B的的左左子子树树LB转换而成的森林转换而成的森林;F中中 除除 T1之之 外外 其其 余余 树树 组组 成成 的的 森森 林林F=T2,T3,，Tm是是由由B的的右右子子树树RB转转换换而成的森林。而成的森林。n当树非空时当树非空时u 访问根结点访问根结点u 依次先根遍历根的各棵依次先根遍历根的各棵 子树子树n树先根遍历树先根遍历 ABEFCDGn对应二叉树前序遍历对应二叉树前序遍历 ABEFCDGn树的先根遍历结果与其对应二叉树树的先根遍历结果与其对应二叉树 表示的表示的前序遍历前序遍历结果相同结果相同n树的先根遍历可以借助对应二叉树树的先根遍历可以借助对应二叉树 的前序遍历算法实现的前序遍历算法实现ABCEDGF树的树的先根次序先根次序遍遍历历q树的遍树的遍历历A AC CB BD DG GF FE E树的后根次序遍历树的后根次序遍历:n当树非空时当树非空时u依次后根遍历根的各棵依次后根遍历根的各棵 子树子树u访问根结点访问根结点n树后根遍历树后根遍历 EFBCGDAn对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAn树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树 表示的表示的中序遍历中序遍历结果相同结果相同n树的后根遍历可以借助对应二叉树树的后根遍历可以借助对应二叉树的中序遍历算法实现的中序遍历算法实现A AC CB BD DG GF FE EABCEDGF森林的两种遍历方法：森林的两种遍历方法：一、先序遍历森林：一、先序遍历森林：若森林非空，则若森林非空，则（1）访问森林中第一棵树的根结点；）访问森林中第一棵树的根结点；（2）先序遍历第一棵树的根结点的子树森林；）先序遍历第一棵树的根结点的子树森林；（3）先序遍历除去第一棵树之后的森林。）先序遍历除去第一棵树之后的森林。二、中序遍历森林：二、中序遍历森林：若森林非空，则若森林非空，则（1）中序遍历第一棵树的根结点的子树森林；）中序遍历第一棵树的根结点的子树森林；（2）访问森林中第一棵树的根结点；）访问森林中第一棵树的根结点；（3）中序遍历除去第一棵树之后的森林。）中序遍历除去第一棵树之后的森林。霍夫曼树霍夫曼树(Huffman Tree)在二叉树中，一个结点到另一个结点之间在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的的分支构成这两个结点之间的路径路径。在路径上的分支数目被称为在路径上的分支数目被称为路径长度路径长度。树的带权树的带权 路径长度路径长度是树的各叶结点所带的权值是树的各叶结点所带的权值 wi 与该结点到根的路径长度与该结点到根的路径长度 li 的乘积的和。的乘积的和。用公式可表示为：用公式可表示为：WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=35222444555777带权路径带权路径长度达到最小长度达到最小霍夫曼树霍夫曼树假假设设有有n n个个权权值值1 1,2 2,n n，试试构构造造一一棵棵有有n n个个叶叶子子结结点点的的二二叉叉树树,每每个个叶子结点带权为叶子结点带权为i i,则其中：则其中：带权路径长度带权路径长度WPLWPL最小的二叉树称做最小的二叉树称做 最优二叉树最优二叉树 或赫夫曼树或赫夫曼树.n在霍夫曼树中，权值大的结点离根最近。在霍夫曼树中，权值大的结点离根最近。构造赫夫曼树的算法思想构造赫夫曼树的算法思想 (1)(1)根根据据给给定定的的n n个个权权值值ww1 1,w,w2 2,