《数据结构课件：第6章 树和二叉树3树和森林》由会员分享，可在线阅读，更多相关《数据结构课件：第6章 树和二叉树3树和森林（32页珍藏版）》请在装配图网上搜索。
1、树和森林第第6 6章章 树和二叉树树和二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用v树树的存储的存储结构结构6.4 树和森林树和森林三种常用的存储结构：(1)双亲表示法(2)孩子表示法(3)孩子兄弟表示法v树树的存储的存储结构结构双亲双亲表示法表示法6.4 树和森林树和森林即以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。DACREBFHGK双亲结点下标9876543210666311000-1KHGFEDCBARv树树的双亲的双亲表存储表存储表示表示6.4 树和森林树和森林#define MAX_TREE_SIZE 100 typed
2、ef struct PTNode /结点结构 Elem data;int parent;/双亲位置域 PTNode;typedef struct /树结构 PTNode nodesMAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;v树树的存储的存储结构结构双亲双亲表示法表示法6.4 树和森林树和森林 这种存储结构利用每个结点（除根结点）只有唯一双亲的性质，Parent(T,x)操作可在常量时间内实现。反复调用Parent操作，直到遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个结构。v树树的存储的存储结构结构孩子孩子表示法表示法6
3、.4 树和森林树和森林 由于树中每个结点可能有多棵子树，则考虑用多重链表，即结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：datadegreechild1child2childdydatachild1child2childdxv采用采用第一种格式第一种格式6.4 树和森林树和森林datachild1child2childdx 多重链表中的结点是同构的，其中dx为树的度。由于树中很多结点的度小于dx，所以链表中有很多空链域，造成空间浪费。v采用第二采用第二种格式种格式6.4 树和森林树和森林 多重链表中的结点是不同构的，其中dy为结点的度，derge
4、e域的值同dy，此时可以节省存储空间，但操作不方便。datadegreechild1child2childdy6.4 树和森林树和森林有没有既能节省空间有没有既能节省空间又操作方便的办法呢？又操作方便的办法呢？v另另一种方式一种方式6.4 树和森林树和森林 把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空)。而n个头指针又组成一个线性表，为便于查找，采用顺序存储结构。6.4 树和森林树和森林365120789KHGEFRDCBA0123456789DACREBFHGKv树树的孩子链表存储表示的孩子链表存储表示6.4 树和森林树和
5、森林typedef struct CTNode /孩子结点 int child;struct CTNode*next;*ChildPtr;typedef struct /双亲结点结构 Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;typedef struct /树结构:CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTreev树树的存储结构的存储结构孩子表示法孩子表示法6.4 树和森林树和森林 与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于Parent(T,x)操作。可根据某种需要，将二者结
6、合起来，即带双亲的孩子链表。6.4 树和森林树和森林365120789CKHGEFRDBA0123456789DACREBFHGK466620-1044v树树的存储结构的存储结构孩子孩子兄弟表示法兄弟表示法6.4 树和森林树和森林 或称二叉树表示法，或称二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。v树树的存储结构的存储结构孩子孩子兄弟表示法兄弟表示法6.4 树和森林树和森林REKCFABGHDDACREBFHGKv树树的二叉链表（孩子的二叉链表（孩子-兄弟）存储表示兄弟）存储表示6.4 树和森林树和森林typedef stru
7、ct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;v树树的存储结构的存储结构孩子孩子兄弟表示法兄弟表示法6.4 树和森林树和森林 这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个结点增设一个(parent)域，则同样能方便地实现Parent(T,x)操作。v森林森林和二叉树的转换和二叉树的转换6.4 树和森林树和森林1.树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。DCABAEBDCAEBCD对应E
8、DCABEECABD存储解释解释存储v树树转换为二叉树方法转换为二叉树方法6.4 树和森林树和森林1）对每个孩子进行从左到右的排序；2）在兄弟之间加一条连线；3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；4）以根结点为轴心，将整个树顺时针转45。ABCDEGHFIaABCDEGHFIbABCDEGHFIc1）在兄弟之间加一条连线；2）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；3）以根结点为轴心，将整个树顺时针转45。ABCDEGHFIdABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId1）在兄弟之间加一条连线；2）对每个结点，除了左孩子外，
9、去除其与其余孩子之间的联系；3）以根结点为轴心，将整个树顺时针转45。v森林森林和二叉树的转换和二叉树的转换6.4 树和森林树和森林2.森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。EFADBC树与二叉树对应ADBCGIHJEFGJHIADBCEFGJHI森林与二叉树对应树根相连森林转二叉树方法森林转二叉树方法1BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId森林转二叉树方法森林转二叉树方法2兄弟相连长兄为父孩子靠左头根为根 二叉树
10、还原为森林二叉树还原为森林ADBCEFGJHI要点：把最右边的子树变为森林，其余右子树变为兄弟 森林与二叉树对应ADBCEFGJHIEFADBCGIHJ树与二叉树对应v树树和森林的遍历和森林的遍历6.4 树和森林树和森林1.树的遍历：有三条搜索路径先根(序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根(序)遍历：若树不空，则先依次后根遍历 各棵子树，然后访问根结点。按层次遍历：若树不空，则自上而下自左至 右访问树中每个结点。v例：树的遍历例：树的遍历6.4 树和森林树和森林对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIA B E F
11、 C D G H IE F B C G H I D Av森林森林的遍历的遍历6.4 树和森林树和森林先序遍历(对森林中的每一棵树进行先根遍历)1）若森林不空，访问森林中第一棵树的根结点；2）先序遍历森林中第一棵树的子树森林；3）先序遍历森林中(除第一棵树外)其余树构成的森林。后序遍历(对森林中的每一棵树进行后根遍历)1）若森林不空，后序遍历森林中第一棵树的子树森林；2）访问森林中第一棵树的根结点；3）后序遍历森林中(除第一棵树外)其余树构成的森林。v例例：森林的：森林的遍历遍历6.4 树和森林树和森林对森林进行先序遍历，获得的先序序列是：对森林进行后序遍历，获得的后序序列是：BCDEGHFIB E F C D G H IE F B C G H I D武汉科技大学Wuhan University of Science and Technology
数据结构课件：第6章 树和二叉树3树和森林
