第5章 树和二叉树(3)PPT演示课件

第5章树和二叉树,1,第5章树和二叉树,5.1树的概念和基本操作5.2二叉树5.3树和森林5.4哈夫曼树及其应用5.5应用举例,2,5.3.1树的存储5.3.2树、森林与二叉树的转换5.3.3树和森林的遍历,5.3树和森林,3,1.双亲表示法以一组连续空间存储树的结点,并在每个结点中附设一个指示器指示其双亲结点在链表中的位置.如图6-3(a)是一棵树,(b)是这棵树的双亲表示存储结构.#defineMAXNODEtypedefstruct/结点结构定义elemtypedata;/数据域intparent;/双亲位置域NodeType;NodeTypetMAXNODE;/结点数组,5.3.1树的存储(3种),4,图5-13树及树的双亲表示示意图,(a)树T,5,特点：双亲表示存储结构利用了每个结点(根结点除外)只有惟一双亲的性质,所以找结点的双亲的操作方便.但求结点的孩子时确需要遍历整个结构.,6,2.孩子链表表示法,序号Datafirstchild,图5-14树的孩子链表表示示意图,下图为图5-13(a)中树的孩子链表表示示意图.,7,即把每个结点的孩子排列成一个单链表,则n个结点就有n个孩子链表(叶子结点的孩子链表为空);n个头指针又组成一个顺序表.#defineMAXNODEtypedefstructChildNode/孩子链表结点结构定义intchildcode;/孩子结点位置structChildNode*nextchild;/指向下一个孩子结点;typedefstruct/孩子链表头结点结构定义elemtypedata;/数据域structChildNodefirstchild;/指向第一个孩子结点NODEType;NodeTypetMAXNODE;/结点数组,8,孩子表示法的特点:是便于查找树中某结点的孩子,但是查找某结点的双亲则操作不便.,9,3.孩子兄弟表示法又称为二叉树(或二叉链表)表示法,即以二叉链表作为树的存储结构，链表中结点结构如下:,firstchilddatanextsibling,数据域,第一个孩子域,下一个兄弟域,孩子兄弟表示法的二叉链表存储结构的最大优点是结点的结构统一,同二叉树表示,易于实现找结点等操作.,图5-15树的孩子兄弟表示法中的结点结构,10,孩子兄弟表示法中二叉表结构定义如下:typedefstructTreeNode/孩子链表结点结构定义elemtypedata;/结点数据域StructTreeNode*son,*next;/指向第一个孩子结点;指向该结点的下一个兄弟结点NodeType;,11,图5-16树T的孩子兄表示存储结构,12,5.3.2树、森林与二叉树的转换,一、树与二叉树的转换1、树转换为二叉树可按以下步骤进行:(1)加线:在兄弟结点之间加连线.(2)抹线:抹掉除最左孩子之外该结点与其余孩子结点之间的连线.(3)旋转:将添加的水平连线及原有连线以树根结点为轴心顺时针旋转45度.,13,转换后的二叉树有以下特点:(1)该二叉树的根结点只有左子树没有右子树.(2)该二叉树中各结点的左孩子是它原来最左的孩子,右孩子是它在原树中的下一个兄弟.,14,(a)树,(b)加线后,图5-17树转换为二叉树的操作过程,15,(c)抹线后,(d)旋转后,图5-17树转换为二叉树的操作过程,16,2.二叉树还原为树分以下三步:(如图所示)(1)加线:若当前结点是双亲结点的左孩子,则将该结点的右孩子,右孩子的右孩子都分别与其双亲结点连线.(2)抹线:抹掉原二叉树中所有双亲结点与右孩子的连线.(3)调整:将结点按层次排列,形成树.,17,(a)二叉树,(b)加线后,图5-18二叉树转换为树的操作过程,18,(c)抹线后,(d)调整后,图5-18二叉树转换为树的操作过程,19,二.森林与二叉树的转换1、森林转换为二叉树分以下三步:(如图所示)(1)转换:将森林中的每一棵树转换为二叉树.(2)连线:将转换后的二叉树根结点相连.(3)旋转:将添加的水平连线及原有连线以第一棵树的根结点为轴心顺时针旋转45度.,20,(a)森林,图5-19森林转换为二叉树的操作过程,21,(c)连线后,图5-19森林转换为二叉树的操作过程,22,(d)旋转后,图5-19森林转换为二叉树的操作过程,23,2.二叉树转换为森林分以下三步:(如图所示)(1)抹线:抹掉二叉树根结点右链上的所有结点的连线,分成若干个以右链上结点为根结点的子二叉树.(2)转换:将分好的子二叉树分别转换为树.(3)调整:将转换好的树的根结点排成一排.,24,A,B,C,D,(a)二叉树,图5-20二叉树还原为森林的操作过程,(b)抹线后,25,转换并调整后,图5-20二叉树还原为森林的操作过程,26,1.树的遍历(2种方法)(1)先根遍历（先根先序)若树非空,先访问树的根结点,然后依次先根遍历根的每棵子树.所得序列同转换后二叉树的先序遍历次序一致.(2)后根遍历（后根中序)若树非空,先依次后根遍历根的每棵子树.然后访问树的根结点,所得遍历序列同转换后二叉树的中序遍历次序一致.,5.3.3树和森林的遍历,27,28,(b)转换后的二叉树,图5-22树的先根,后根,层次遍历,二叉树的先序遍:A,B,C,F,G,D,E,H,I,J二叉树的中序遍:B,F,G,C,D,H,I,J,E,A,29,先根遍历时的访问次序：,ABEFCDGHIJK,后根遍历时的访问次序：,EFBCIJKHGDA,30,由此，树和森林的各种操作均可与二叉树的各种操作相对应。应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟.,31,若森林不空，则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其余树构成的森林。,先序遍历,2.森林的遍历(2种方法),即：依次从左至右对森林中的每一棵树进行先根遍历。所得序列与转换后二叉树的先序遍历次序一致.,32,1.森林中第一棵树的根结点；,2.森林中第一棵树的子树森林；,3.森林中其它树构成的森林。,可以分解成三部分：,33,中序遍历,若森林不空，则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其余树