数据结构——树与森林

第六章树与森林学习要点：树的递归定义和森林的基本概念。树与森林的存储结构。树与森林的遍历算法树、森林与二叉树的相互转换。2§6.1树及其相关概念6.1.1树的基本概念1、树的基本概念3树（Tree）是一个由n（n≥0）个结点构成的有限集合T。①当n=0时，称T为“空树”。②当n≠0时，T中诸元素满足下述条件：●有且仅有一个特定数据元素没有前驱，称其为T的根结点。●除根结点外其余数据元素，又可分为m（0≤mn）个互不相交的有限集合：T1，T2，…，Tm，每一个集合Ti（0≤i≤m）又是一棵树，称为根的子树。6.1.1树的基本概念1、树的基本概念2树的特性：4LMKAFBCGDEJIHΦLACGA空树是树的一个特例；一棵非空树，至少有一个根结点，只有根结点的树为最小树；在有多个结点的树里，除根结点外，其余结点分属若干个子树，各子树间互不相交；除根结点外，树中其他结点有且只有一个前驱结点，但可以有零个或多个后继结点。6.1.1树的基本概念1、树的基本概念3有序树与无序树如果树T中各子树从左至右按照一定此序排列，不得互换，则称T是有序树（ordertree），否则为无序树（unordertree）。由此可知，二叉树是一种特殊的有序树，但不是一般树的特例。森林n（n≥0）棵互不相交的树的集合，称为森林（forest）。56.1.1树的基本概念22、树的表示方法①树形表示法6②文氏图表示法③凹入表示法④括弧表示法（A（B（D）（E（I）（J））（F））（C（G）（H）））GAEBCDHFJIEDHFJIGCBAGCBADEFHIJ6.1.2结点及其基本概念1、结点结点的度：结点拥有的子树数目，即该结点的后继结点的个数结点的深度（层次）：结点位于树的层次数树的度：一棵树中各结点度的最大值树的深度：一棵树中各结点深度的最大值结点间路径：从树中一个结点到另一个结点之间的分支路径长度：一条路径上边即连接两个结点的线段的个数称为该路径的长度76.1.2结点及其基本概念282、结点分类（1）根结点：树T中没有前驱的结点称为T的根结点叶结点：树T中没有后继的点称为T的叶结点内部结点：树T中既有前驱又有后继的结点称为T的内部结点（2）分支结点：树T中度数不等于0的结点为T的分支结点非分支结点：树T中度数等于0的结点称为T的非分支结点6.1.2结点及其基本概念393、结点间关系描述子结点：树T中一个结点N的所有直接后继，都被称作是该结点N的子结点父结点：树T中把一个结点称作是它所有后继结点的父结点兄弟结点：在树T中，具有相同双亲的结点，互称为是兄弟结点堂兄弟结点：在树T中，双亲在同一层的那些结点，互称为是堂兄弟结点子孙结点：一个结点的子树中的所有结点，都被称作是该结点的子孙结点祖先结点：从根结点到某个结点的路径上的所有分支结点，称为该结点的祖先结点§6.2树的存储结构6.2.1父结点表示法存储将树中结点按照“由上到下”和“由左到右”的顺序做成一个结点序列，将该序列存放在一维数组Tr当中。Tr中每个元素（结点）都有一个Data域和一个Parent域，其中Data域存放结点数据，而Parent域存放结点的父结点在数组中下标。10DataParentTr[i]：数据域双亲下标KIHGAFBCDEJ下标012345678910DataABCDEFGHIJKParent-10001133666root6.2.2子结点表示法存储考虑通过设立结点的Children域来存储树结构信息。当使用链式结构来实现树存储时，就需要将每个结点的孩子信息都存放在存储结点中。此时存储结点除建立Data域外，还需按照树的度m对每个结点构建m个指针域。11DataChP1数据域指向第1个孩子ChP2指向第2个孩子……ChPm指向第m个孩子这种子结点链式存储效率低下，通常不直接采用上述方法。6.2.2子结点表示法存储1、子结点链表存储法12①将树T中结点按照层序进行排序。②为树T中每个结点都设置一个单链表，该链表由该结点的所有子结点按照层序进行链接。这样的链表也称为子结点链表。③将每个结点子结点链表的表头指针按照树T结点的层序集中起来组成数组Tr。KIHGAFBCDEJ（a）ChnNext孩子号指向下一孩子下标DataFChild0A1B2C^3D4E^5F^6G7H^8I^9J^10K^数组TrChnNext123^45^67^8910^（b）root6.2.2子结点表示法存储22、子结点顺序表存储法13①将树T的结点按照层序进行排序，组成数组Tr。②对Tr中每个数组元素开辟Data域和m个子结点域：Child[1]，Child[2]，…，Child[m]，这些子结点域分别记录每个结点的子结点信息。③将数组Tr进行存储。KIHGAFBCDEJroot下标DataChr[1]Chr[2]Chr[3]0A1231B45-12C-1-1-13D67-14E-1-1-15F-1-1-16G89107H-1-1-18I-1-1-19J-1-1-110K-1-1-16.2.3左子/右兄弟结点表示法存储结点由Data域（存放数据信息）、Lch域（存放该结点第一个子结点即左子结点信息）和RS域（存放该结点第一个兄弟结点即右兄弟结点信息）组成。14（a）DataLCH数据域第一个孩子下标RS下一个兄弟下标6.2.3左子/右兄弟结点表示法存储2可以分别按照顺序或链表方式进行进行存储。15KIHGAFBCDEJ下标DataLchRS0A1-11B422C-133D6-14E-155F-1-16G877H-1-18I-199J-11010K-1-1（b）（c）A^B^CD^^F^^E^H^G^I^J^K^DataLCHRS§6.3树的遍历6.3.1层次遍历1、层次遍历概念16两个步骤：①按照树的“层”的顺序进行访问，即“从上到下”。②访问到达每一层后，再依次访问该层的每个结点，即“从左到右”。两个基本点：①采用子结点表示法的存储结构记录树中结点。②基于队列的结点存储当进入一个结点后，需要将该结点所有子结点信息记录下来以便必要时能够使用。由于先达到结点的子结点，将来会得到首先访问，所以需要采用队列方式记录结点的子结点信息以保证它们能够依照进入队列的先后顺序得到访问。例子：以层次遍历方式访问如图所示的二叉树。17解：A-B-C-D-E-F-G-H-I-J-KABCDEFGHIJK6.3.1层次遍历22、层次遍历算法18步骤当前出队结点当前访问结点当前进队结点当前队列内容初始——AA1AAB，C，DB，C，D2BBE，F，GC，D，E，F，G3CCHD，E，F，G，H4DDI，JE，F，G，H，I，J5EE—F，G，H，I，J6FFKG，H，I，J，K7GG—H，I，J，K8HH—I，J，K9II—J，K10JJ—K11KK—空2、层次遍历算法2算法6-1树的层次遍历算法1900Level_Tr(treenodetr[],intm,introot)01{02QueueQs;intk;03Qs.front=0;/*队首、队尾指针初始化*/04Qs.rear=0;05Qs.data[Qs.rear]=root;/*让根结点下标进队列*/06Qs.rear++;已知一棵树T的度为m，采用基于顺序表的子结点表示法存储。对T进行层次遍历以获得层次遍历序列。2、层次遍历算法2算法6-1树的层次遍历算法2007while(Qs.front!=Qs.rear)/*队列非空*/08{09k=Qs[Qs.front];/*取队首元素赋值给k*/10Qs.front++;/*队首元素出队*/11printf(%c,tr[k].Data);/*访问该结点*/12for(i=1;i=m;i++)/*让该结点的孩子结点进队列*/13if(tr[k].Child[i]!=NULL)14{15Qs[Qs.rear]=tr[k].Child[i];16Qs.rear++;17}18}19}6.3.2先序遍历过程：（1）若T为空，遍历结束；（2）若T非空，先访问T根结点，然后从左到右依次先序遍历访问根结点的每棵子树。21ABDFGKCHDIJ例子：以先序遍历方式访问如图所示的二叉树。解：A-B-E-F-K-G-C-H-D-I-J6.3.2先序遍历2算法6-2树的先序遍历递归算法已知树T的度为m，采用基于顺序表的子结点表示法存储，在此基础上先序遍历，输出先序遍历序列。2200Pre_Tr(treenodetr[],intm,introot)01{02intk;03k=root;04if(k!=NULL)05{06printf(%c,tr[k].Data);/*访问结点*/07for(i=1;i=m;i++)/*依次先序遍历结点的各子树*/08Pre_Tr(tr[],m,i);09}10}6.3.3后序遍历过程：（1）若T为空，则遍历结束；（2）若T非空，则从左到右依次后序遍历根结点的各子树，然后访问根结点。23例子：以后序遍历方式访问如图所示的二叉树。解：E-K-F-G-B-H-C-I-J-D-AABCDEFGHIJK6.3.3后序遍历2算法6-3树的后序遍历递归算法已知树T的度为m，采用基于顺序表的子结点表示法存储，在此基础上实施后序遍历，输出结果。2400Post_Tr(treenodetr[],intm,introot)01{02intk;03k=root;04if(k!=NULL)05{06for(i=1;i=m;i++)/*依次后序遍历结点的各子树*/07Post_Tr(tr[],m,i);08printf(%c,tr[k].Data);/*访问结点*/09}10}§6.4森林森林：若干棵树组成的集合1、森林的先序遍历若森林为空，遍历结束；若森林非空，从左往右依次先序遍历森林中的每棵树，对结点的访问顺序，即是对森林先序遍历的结点序列。25例子：以先序遍历方式访问如图所示的森林。解：E-K-F-G-B-H-C-I-J-D-AABCDEFGHIJKLM§6.4森林21、森林的后序遍历若森林为空，则遍历结束；若森林非空，则从左往右依次后序遍历森林中的每棵树，对结点的访问顺序，即是对森林后序遍历的结点序列。26例子：以后序遍历方式访问如图所示的森林。解：B-A-E-F-G-D-C-I-K-L-M-J-HABCDEFGJKLMHI§6.5树与二叉树的转换6.5.1树转换为二叉树27①确定根结点。原树的根结点即为转换后二叉树的根结点。②处理根结点。这里涉及根结点的左孩子及其左孩子的所有右子孙。将树中根结点的第一个孩子转换为二叉树根结点的左孩子，该左孩子在树中的所有兄弟依次转换为二叉树中该结点的右孩子及右子孙。③对新画的每个结点依次处理。处理方法如同步骤2，将树中对应结点的第一个孩子转换为该结点的左孩子，该左孩子在树中的所有兄弟依次转换为二叉树中该结点的右孩子及右子孙。④反复执行步骤3，直到所有结点均处理完毕。6.5.1树转换为二叉树2一个树转换为二叉树的例子：28AFBCGDEHAABCDAFBEDCGAFBEHDCG转换6.5.1树转换为二叉树3由树转换过来的二叉树特点：二叉树根结点无右孩子，只有左子树。除了根结点外，其余结点的左孩子为原树结构结点的第一个孩子，右孩子及右子孙依次为原树结构结点的兄弟。29§6.5树与二叉树的转换26.5.2二叉树还原为树30①确定根结点。二叉树的根结点即为原树的根结点。②处理根结点。将二叉树中根结点的左孩子确定为原树结构的第一个孩子，该左孩子在二叉树中右孩子及右子孙依次还原为树结构中的兄弟，即其双亲的其余孩子。③对新画的每个结点依次处理。处理方法如同步骤2。④反复执行步骤3，直到所有结点均处理完毕。6.5.2二叉树还原为树2一个二叉树还原为树的例子：31还原ABFECDHGAABECABGECDHFABECDHF§6.5树与二叉树的转换36.5.3森林与二叉树的转换32ABEDCFIHGJAEGABEDCFIHGJ①确定根结点。将森林中第一棵树的根结点确定为二