第六章树与森林.ppt

第六章 树与森林,学习要点：,树的递归定义和森林的基本概念。 树与森林的存储结构。 树与森林的遍历算法 树、森林与二叉树的相互转换。,2,§6.1 树及其相关概念,6.1.1 树的基本概念 1、树的基本概念,3,树（Tree）是一个由n（n0）个结点构成的有限集合T。 当n=0时，称T为“空树”。 当n0时，T中诸元素满足下述条件： 有且仅有一个特定数据元素没有前驱，称其为T的根结点。 除根结点外其余数据元素，又可分为m（0mn）个互不相交的有限集合：T1，T2，Tm，每一个集合Ti（0im）又是一棵树，称为根的子树。,6.1.1 树的基本概念,1、树的基本概念2 树的特性：,4,空树是树的一个特例； 一棵非空树，至少有一个根结点，只有根结点的树为最小树； 在有多个结点的树里，除根结点外，其余结点分属若干个子树，各子树间互不相交； 除根结点外，树中其他结点有且只有一个前驱结点，但可以有零个或多个后继结点。,6.1.1 树的基本概念,1、树的基本概念3 有序树与无序树 如果树T中各子树从左至右按照一定此序排列，不得互换，则称T是有序树（order tree），否则为无序树（unorder tree）。由此可知，二叉树是一种特殊的有序树，但不是一般树的特例。 森林 n（n0）棵互不相交的树的集合，称为森林（forest）。,5,6.1.1 树的基本概念2,2、树的表示方法 树形表示法,6, 文氏图表示法, 凹入表示法, 括弧表示法 （A（B（D）（E（I）（J）（F）（C（G）（H）,6.1.2 结点及其基本概念,1、结点 结点的度：结点拥有的子树数目，即该结点的后继结点的个数 结点的深度（层次）：结点位于树的层次数 树的度：一棵树中各结点度的最大值 树的深度：一棵树中各结点深度的最大值 结点间路径：从树中一个结点到另一个结点之间的分支 路径长度：一条路径上边即连接两个结点的线段的个数称为该路径的长度,7,6.1.2 结点及其基本概念2,8,2、结点分类 （1）根结点：树T中没有前驱的结点称为T的根结点 叶结点：树T中没有后继的点称为T的叶结点 内部结点：树T中既有前驱又有后继的结点称为T的内部结点 （2）分支结点：树T中度数不等于0的结点为T的分支结点 非分支结点：树T中度数等于0的结点称为T的非分支结点,6.1.2 结点及其基本概念3,9,3、结点间关系描述 子结点：树T中一个结点N的所有直接后继，都被称作是该结点N的子结点 父结点：树T中把一个结点称作是它所有后继结点的父结点 兄弟结点：在树T中，具有相同双亲的结点，互称为是兄弟结点 堂兄弟结点：在树T中，双亲在同一层的那些结点，互称为是堂兄弟结点 子孙结点：一个结点的子树中的所有结点，都被称作是该结点的子孙结点 祖先结点：从根结点到某个结点的路径上的所有分支结点，称为该结点的祖先结点,§6.2 树的存储结构,6.2.1 父结点表示法存储 将树中结点按照“由上到下”和“由左到右”的顺序做成一个结点序列，将该序列存放在一维数组Tr当中。Tr中每个元素（结点）都有一个Data域和一个Parent域，其中Data域存放结点数据，而Parent域存放结点的父结点在数组中下标。,10,6.2.2 子结点表示法存储,考虑通过设立结点的Children域来存储树结构信息。当使用链式结构来实现树存储时，就需要将每个结点的孩子信息都存放在存储结点中。此时存储结点除建立Data域外，还需按照树的度m对每个结点构建m个指针域。,11,6.2.2 子结点表示法存储2,1、子结点链表存储法,12, 将树T中结点按照层序进行排序。 为树T中每个结点都设置一个单链表，该链表由该结点的所有子结点按照层序进行链接。这样的链表也称为子结点链表。 将每个结点子结点链表的表头指针按照树T结点的层序集中起来组成数组Tr。,6.2.2 子结点表示法存储3,2、子结点顺序表存储法,13, 将树T的结点按照层序进行排序，组成数组Tr。 对Tr中每个数组元素开辟Data域和m个子结点域：Child1，Child2，Childm，这些子结点域分别记录每个结点的子结点信息。 将数组Tr进行存储。,6.2.3 左子/右兄弟结点表示法存储,结点由Data域（存放数据信息）、Lch域（存放该结点第一个子结点即左子结点信息）和RS域（存放该结点第一个兄弟结点即右兄弟结点信息）组成。,14,6.2.3 左子/右兄弟结点表示法存储2,可以分别按照顺序或链表方式进行进行存储。,15,§6.3 树的遍历,6.3.1 层次遍历 1、层次遍历概念,16,两个步骤： 按照树的“层”的顺序进行访问，即“从上到下”。 访问到达每一层后，再依次访问该层的每个结点，即“从左到右”。 两个基本点： 采用子结点表示法的存储结构记录树中结点。 基于队列的结点存储 当进入一个结点后，需要将该结点所有子结点信息记录下来以便必要时能够使用。由于先达到结点的子结点，将来会得到首先访问，所以需要采用队列方式记录结点的子结点信息以保证它们能够依照进入队列的先后顺序得到访问。,例子：,以层次遍历方式访问如图所示的二叉树。,17,解： A-B-C-D-E-F-G-H-I-J-K,6.3.1 层次遍历2,2、层次遍历算法,18,2、层次遍历算法2,算法6-1 树的层次遍历算法,19,00 Level_Tr(treenode tr, int m,int root) 01 02 queue Qs; int k; 03 Qs_front=0; /* 队首、队尾指针初始化 */ 04 Qs_rear=0; 05 Qs.dataQs_rear = root; /* 让根结点下标进队列 */ 06 Qs_rear + ; 07 while (Qs_front = Qs_rear) /* 队列非空 */ 08 09 k = QsQs_front ; /* 取队首元素赋值给k */ 10 Qs_front+ ; /* 队首元素出队 */ 11 printf (“%c“,trk.Data); /* 访问该结点 */ 12 for (i=1; i=m; i+) /* 让该结点的孩子结点进队列 */ 13 if (trk.Childi != NULL) 14 15 QsQs_rear = trk.Childi; 16 Qs_rear + ; 17 18 19 ,已知一棵树T的度为m，采用基于顺序表的子结点表示法存储。对T进行层次遍历以获得层次遍历序列。,6.3.2 先序遍历,过程： （1）若T为空，遍历结束； （2）若T非空，先访问T根结点，然后从左到右依次先序遍历访问根结点的每棵子树。,20,例子：以先序遍历方式访问如图所示的二叉树。,解： A-B-E-F-K-G-C-H-D-I-J,6.3.2 先序遍历2,算法6-2 树的先序遍历递归算法 已知树T的度为m，采用基于顺序表的子结点表示法存储，在此基础上先序遍历，输出先序遍历序列。,21,00 Pre_Tr (treenode tr, int m,int root) 01 02 int k; 03 k = root; 04 if (k!= NULL) 05 06 printf (“%c“, trk.Data); /* 访问结点 */ 07 for (i=1; i=m; i+) /* 依次先序遍历结点的各子树 */ 08 Pre_Tr (tr,m,i); 09 10 ,6.3.3 后序遍历,过程： （1）若T为空，则遍历结束； （2）若T非空，则从左到右依次后序遍历根结点的各子树，然后访问根结点。,22,例子：以后序遍历方式访问如图所示的二叉树。,解： E-K-F-G-B-H-C-I-J-D-A,6.3.3 后序遍历2,算法6-3 树的后序遍历递归算法 已知树T的度为m，采用基于顺序表的子结点表示法存储，在此基础上实施后序遍历，输出结果。,23,00 Post_Tr(treenode tr, int m,int root) 01 02 int k; 03 k = root; 04 if (k != NULL) 05 06 for (i=1; i=m; i+) /* 依次后序遍历结点的各子树 */ 07 Post_Tr(tr,m,i); 08 printf (“%c“, trk.Data); /* 访问结点 */ 09 10 ,§6.4 森林,森林：若干棵树组成的集合 1、森林的先序遍历 若森林为空，遍历结束； 若森林非空，从左往右依次先序遍历森林中的每棵树，对结点的访问顺序，即是对森林先序遍历的结点序列。,24,例子：以先序遍历方式访问如图所示的森林。,解： E-K-F-G-B-H-C-I-J-D-A,§6.4 森林2,1、森林的后序遍历 若森林为空，则遍历结束； 若森林非空，则从左往右依次后序遍历森林中的每棵树，对结点的访问顺序，即是对森林后序遍历的结点序列。,25,例子：以后序遍历方式访问如图所示的森林。,解： B-A-E-F-G-D-C-I-K-L-M-J-H,§6.5 树与二叉树的转换,6.5.1 树转换为二叉树,26, 确定根结点。原树的根结点即为转换后二叉树的根结点。 处理根结点。这里涉及根结点的左孩子及其左孩子的所有右子孙。将树中根结点的第一个孩子转换为二叉树根结点的左孩子，该左孩子在树中的所有兄弟依次转换为二叉树中该结点的右孩子及右子孙。 对新画的每个结点依次处理。处理方法如同步骤2，将树中对应结点的第一个孩子转换为该结点的左孩子，该左孩子在树中的所有兄弟依次转换为二叉树中该结点的右孩子及右子孙。 反复执行步骤3，直到所有结点均处理完毕。,6.5.1 树转换为二叉树2,一个树转换为二叉树的例子：,27,转换,6.5.1 树转换为二叉树3,由树转换过来的二叉树特点： 二叉树根结点无右孩子，只有左子树。 除了根结点外，其余结点的左孩子为原树结构结点的第一个孩子，右孩子及右子孙依次为原树结构结点的兄弟。,28,§6.5 树与二叉树的转换2,6.5.2 二叉树还原为树,29, 确定根结点。二叉树的根结点即为原树的根结点。 处理根结点。将二叉树中根结点的左孩子确定为原树结构的第一个孩子，该左孩子在二叉树中右孩子及右子孙依次还原为树结构中的兄弟，即其双亲的其余孩子。 对新画的每个结点依次处理。处理方法如同步骤2。 反复执行步骤3，直到所有结点均处理完毕。,6.5.2 二叉树还原为树2,一个二叉树还原为树的例子：,30,还原,§6.5 树与二叉树的转换3,6.5.3 森林与二叉树的转换,31,确定根结点。将森林中第一棵树的根结点确定为二叉树的根结点。由于森林中的其他树的根结点视为第一棵树根结点的兄弟，所以其他树的根结点依次为二叉树的右孩子及右子孙。 对森林中的每棵树分别转换即可，方法与树转换为二叉树的方法一致。,6.5.3 森林与二叉树的转换2,将根结点的右孩子和右子孙的连线去掉，变成若干个独立的二叉树，再分别采用二叉树还原为树的方法进行还原即可。,32,本章小结,本章基本内容,