武汉科技大学WuhanUniversityofScienceandTechnology数据结构DataStructures张凯计算机学院软件工程系2011年3月12日树和森林第6章树和二叉树树的基本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其应用树的存储结构§6.4树和森林三种常用的存储结构：(1)双亲表示法(2)孩子表示法(3)孩子兄弟表示法树的存储结构——双亲表示法§6.4树和森林即以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。DACREBFHGK双亲结点下标9876543210666311000-1KHGFEDCBAR树的双亲表存储表示§6.4树和森林#defineMAX_TREE_SIZE100typedefstructPTNode{//结点结构Elemdata;intparent;//双亲位置域}PTNode;typedefstruct{//树结构PTNodenodes[MAX_TREE_SIZE];intr,n;//根结点的位置和结点个数}PTree;树的存储结构——双亲表示法§6.4树和森林这种存储结构利用每个结点（除根结点）只有唯一双亲的性质，Parent(T,x)操作可在常量时间内实现。反复调用Parent操作，直到遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个结构。树的存储结构——孩子表示法§6.4树和森林由于树中每个结点可能有多棵子树，则考虑用多重链表，即结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：datadegreechild1child2…childdydatachild1child2…childdx采用第一种格式§6.4树和森林datachild1child2…childdx多重链表中的结点是同构的，其中dx为树的度。由于树中很多结点的度小于dx，所以链表中有很多空链域，造成空间浪费。采用第二种格式§6.4树和森林多重链表中的结点是不同构的，其中dy为结点的度，dergee域的值同dy，此时可以节省存储空间，但操作不方便。datadegreechild1child2…childdy§6.4树和森林有没有既能节省空间又操作方便的办法呢？另一种方式§6.4树和森林把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空)。而n个头指针又组成一个线性表，为便于查找，采用顺序存储结构。§6.4树和森林3^6^51^2078^9^K^H^G^EFR^DC^BA0123456789DACREBFHGK树的孩子链表存储表示§6.4树和森林typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{//双亲结点结构Elemdata;ChildPtrfirstchild;//孩子链的头指针}CTBox;typedefstruct{//树结构:CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根结点的位置}CTree;树的存储结构——孩子表示法§6.4树和森林与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于Parent(T,x)操作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。§6.4树和森林3^6^51^2078^9^^^^^C^KHGEFRDBA0123456789DACREBFHGK466620-1044树的存储结构——孩子兄弟表示法§6.4树和森林或称二叉树表示法，或称二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。树的存储结构——孩子兄弟表示法§6.4树和森林^R^E^^K^^C^FAB^G^H^D^DACREBFHGK树的二叉链表（孩子-兄弟）存储表示§6.4树和森林typedefstructCSNode{Elemdata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;树的存储结构——孩子兄弟表示法§6.4树和森林这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个结点增设一个(parent)域，则同样能方便地实现Parent(T,x)操作。森林和二叉树的转换§6.4树和森林1.树和二叉树的对应关系由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。^D^CAB^AEBDCAEBCD对应^E^^^D^CAB^^E^^^E^CAB^^D^^存储解释解释存储树转换为二叉树方法§6.4树和森林1）对每个孩子进行从左到右的排序；2）在兄弟之间加一条连线；3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；4）以根结点为轴心，将整个树顺时针转45°。ABCDEGHFIaABCDEGHFIbABCDEGHFIc1）在兄弟之间加一条连线；2）...
