DS树和二叉树线索二叉树树和森林.pptx

《DS树和二叉树线索二叉树树和森林.pptx》由会员分享，可在线阅读，更多相关《DS树和二叉树线索二叉树树和森林.pptx（51页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、DBCEFAECBDF二叉链表lchilddatarchildA第1页/共51页何谓线索二叉树？nThreadedBinaryTreen线索二叉树：指加上线索的，原有的空左孩子域指向前驱，原有的空右孩子指向后继的二叉树n指向结点“前驱”和“后继”的指针，称“线索”；n对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。第2页/共51页2.线索链表中结点的结构在二叉链表的结点结构中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：其中：LTag=0 lchild 域域指向指向左孩子左孩子1 lchild 域域指向指向前驱前驱RTag=0 rchild 域

2、域指向指向右孩子右孩子1 rchild 域域指向指向后继后继第3页/共51页二叉树的二叉线索存储表示/Link=0:指针，Thread=1:线索typedef enum Link,Thread PointerTag;typedef struct BiThrNode TElemType data;struct BiThrNode*lchild,*rchild;/左右孩子指针 PointerTag LTag,RTag;/左右标志 BiThrNode,*BiThrTree;第4页/共51页 二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树：前序线索二叉树 中序线索二叉树 后

3、序线索二叉树 层序线索二叉树线索二叉树第5页/共51页3.线索二叉树及其存储结构图例（a）中序线索二叉树 （b）中序线索链表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1中序序列：4 2 6 5 7 1 3头指针 头结点添加头结点后，好比为二叉树建立了一个双向线索链表，即可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。NULLNULL为使算法设计方便，增加一个头结点。第6页/共51页如何在中序线索树中找结点的后继？l 若其右标志为“1”，右链是线索，右链直接指向后继；比如4、6、7l 若其右标志为“0”，右链是指针，其

4、后继应为遍历其右子树时第一个访问的结点，即右子树中最左下的结点。比如2的后继为61 12 23 34 45 56 67 7第7页/共51页如何在中序线索树中找结点的前驱？l 若其左标志为“1”，左链为线索，直接指向前驱；比如3、6、7l 若其左标志为“0”，前驱应为遍历左子树时最后访问的一个结点，即左子树中最右下的结点。比如1的前驱为7、2的前驱为4、5的前驱为61 12 23 34 45 56 67 7第8页/共51页如何在后序线索树中找结点的后继或者如何在前序线索树中找结点的前驱？在后序线索树中找结点后继较复杂，P133，需知道结点双亲，即需带指向其双亲结点的指针域的三叉链表作存储结构。同

5、理，在前序线索树中找结点前驱也需知道结点双亲。第9页/共51页根据刚才的分析，可以看出，在中序线索链表上遍历二叉树，要比在二叉链表上中序遍历高效，虽时间还是O(n)，但常数因子比上节的非递归遍历算法小，且不需设栈。第10页/共51页线索链表的中序遍历算法6.5Status InOrderTraver_Thr(BiThrTree T,Status(*Visit)(TElemType e)/中序遍历二叉线索树中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数Visit。/T指向头结点，头结点的左链指向头结点，头结点的左链lchild指向根结点，指向根结点，

6、p=T-lchild;/p指向根结点指向根结点 while(p!=T)/空树或遍历结束时，空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;/p指向最左下结点，指向最左下结点，/即中序遍历的第一个结点即中序遍历的第一个结点 if(!Visit(p-data)return ERROR;/访问第一个结点访问第一个结点 while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/顺线索访问后继结点顺线索访问后继结点 p=p-rchild;return OK;0 1 00 2 01 3 11 4 10 5 01

7、6 11 7 1T0 1 1 Thrt空树空树01第11页/共51页分析：建立线索链表，实质上就是在遍历的过程中将二叉链表中的空指针改为指向前驱或后继的线索。4.如何建立线索化链表？第12页/共51页对二叉链表T进行中序线索化的递归算法(带头结点)StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)步骤：1.生成头结点Thrt，如果树非空，左孩子指向树根，否则，回指自身；2.pre=Thrt;调用不带头结点的中序线索化的递归算法;3.最后一个结点线索化（指向头结点）1 A B D C E111110000T第13页/共51页/中序遍历二叉链表T，并

8、将其中序线索化，Thrt指向头结点。Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/建立头结点Thrt=(BiThrTree)malloc(sizeof(BiThrNode);if(!Thrt)exit(OVERFLOW);Thrt-ltag=Link;Thrt-rtag=Thread;Thrt-rchild=Thrt;/右指针回指 if(!T)/空树，左指针回指Thrt-lchild=Thrt;ThrtLinkThread01算法6.6第14页/共51页1else/非空树，进行线索化 Thrt-lchild=T;/头结点的lchild指

9、向二叉链表根 pre=Thrt;/pre指向T的前驱 InThreading(T);/中序线索化二叉链表T pre-rchild=Thrt;/最后一个结点线索化pre-rtag=Thread;Thrt-rchild=pre;return OK;Thrt A B D C Epre输出：输出：B C A E D10111110000preT第15页/共51页void InThreading(BiThrTree p)if(p)InThreading(p-lchild);/左子树线索化/此时p所指结点的左子树不存在或已线索化if(!p-lchild)/左孩子为空，建立p所指结点的前驱线索 p-lchi

10、ld=pre;p-ltag=Thread;if(!pre-rchild)/右孩子为空，建立pre所指结点的后继线索 pre-rchild=p;pre-rtag=Thread;pre=p;/保持pre指向p的前驱 InThreading(p-rchild);/右子树线索化 对二叉链表p进行中序线索化的递归算法(不带头结点)1 Thrt A B D C Epre10111110000prep第16页/共51页ABDECFG例：对下图的树按先序、后序、中序线索化第17页/共51页第6章 树和二叉树6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林 6.4.1 树的

11、存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历6.6 赫夫曼树及其应用第18页/共51页6.4.1 树的存储结构三种常用的链表结构：n双亲表示法n孩子表示法n孩子兄弟表示法第19页/共51页1.双亲表示法即以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲的下标。DACREBFHGK双亲结点下标9876543210666311000-1KHGFEDCBAR第20页/共51页树的双亲表存储表示#define MAX_TREE_SIZE 100 typedef struct PTNode /结点结构 TElemType data;int parent;/双亲

12、位置域 PTNode;typedef struct /树结构 PTNode nodesMAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;第21页/共51页分析：这种存储结构利用每个结点（除根结点）只有唯一双亲的性质，parent(T,x）操作可在常量时间内实现。反复调用parent操作，直到遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个结构。第22页/共51页2.孩子表示法n 多重链表+孩子链表n 多重链表n 由于树中每个结点可能有多棵子树，则考虑用多重链表，即结点有多个指针域，其中每个指针指向一个孩子，此时有两种结点格式：da

13、tadegreechild1child2childddatachild1child2childd第23页/共51页采用第一种格式：指针域的个数等于树的度 多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，所以链表中有很多空链域，造成空间浪费。datachild1child2childdn个结点度为k的树中必有n*(k-1)+1个空链域。第24页/共51页采用第二种格式：指针域的个数等于结点的度结点是不同构的，其中d为结点的度，degree域的值同d，此时可以节省存储空间，但结点结构不一致，操作不方便。datadegreechild1child2childdA 2B 3C 2

14、E 1I 0G 0H 0F 0D 0ACBHFEDGI第25页/共51页有没有既能节省空间又操作方便的办法呢？第26页/共51页另一种方式：孩子链表表示法1.把每个结点的孩子结点用一个单链表表示。则n个结点有n个孩子链表（叶子的孩子链表为空)。2.而n个头指针又组成一个线性表，为便于查找，采用顺序存储结构。第27页/共51页365120789KHGEFRDCBA0123456789DACREBFHGK表结点孩子结点第28页/共51页树的孩子链表存储表示typedef struct CTNode /孩子结点int child;/孩子对应表结点的下标 struct CTNode*next;/指向下

15、一个孩子结点的指针CTNode，*ChildPtr;typedef struct /表结点 TElemType data;ChildPtr firstchild;/孩子链的头指针，指向第一个孩子结点CTBox;typedef struct /树结构 CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;第29页/共51页分析：与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于parent(T，x)操作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。第30页/共51页3.孩子兄弟表示法或称二叉链表表示法。即以二叉链表作树的存储结构

16、。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。第31页/共51页树的二叉链表（孩子-兄弟）存储表示typedef struct CSNode TElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;结点结构 firstchild data nextsibling第32页/共51页REKCFABGHDDACREBFHGK二叉链表（孩子兄弟）表示法例：第33页/共51页分析：这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个结点增设一个(parent)域，则同样能方便地

17、实现parent(T,x)操作。第34页/共51页6.4.2 森林和二叉树的转换树、森林与二叉树之间可以互相进行转换，即任何一个森林或一棵树都可以唯一地对应一棵二叉树，而任何一棵二叉树也能唯一地对应到一个森林或一棵树上。正是由于这样的一一对应关系，可以把树的处理问题转化为二叉树的处理问题，从而把问题简化。下面介绍树、森林与二叉树的相互转换。第35页/共51页1.树和二叉树的对应关系第36页/共51页 1.兄弟加线.树转换为二叉树方法ABCDEFG2.保留双亲与第一孩子连线,删去与其他孩子的连线.3.所有横线转动45oGDABECF第37页/共51页ABCDEGHFI(a)ABCDEGHFI(b

18、)ABCDEGHFI(c)ABCDEGHFI(d)例：第38页/共51页2.森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。那么，若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。第39页/共51页1森林转换成二叉树如果F=T1，T2，Tm是森林，则可以按如下规则转换成一棵二叉树B=ROOT，LB，RB1）若F为空，即m=0，则B为空二叉树。2）若F非空，即m0，则B的根ROOT即为森林中第一棵树的根ROOT（T1），B的左子树LB是从第一棵树T1的子树森林F1=T11，T12，T1m1转换而成的二叉树；其

19、右子树RB是从其余树的森林F=T2，T3，Tm转换而成的二叉树。转换方法：将森林中的每棵树转换成二叉树；从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。第40页/共51页12第41页/共51页BCDEGHFI（a）BCDEGHFI（b）BCDEGHFI（c）BCDEGHFI（d）第42页/共51页二叉树转换成森林、树如果B=ROOT，LB，RB是一棵二叉树，则可以按如下原则转换成森林F=T1，T2，Tm1）若B为空，则F为空；2）若B非空，则F中第一棵树T1的根ROOT（T1）为二叉树B的根ROO

20、T；第一棵树T1的子树森林F1是由B的左子树LB转换而成的森林；F中除了T1之外的其余树组成的森林F=T2，T3，Tm是由B的右子树RB转换而成的森林。转换方法：加线若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、，都与结点y用线连起来；去线删去原二叉树中所有的双亲结点与右孩子结点的连线；层次调整第43页/共51页FHGEAICDBFHGDCEBAIFEDCBAHGI加线去线层次调整IHGBCDAFE第44页/共51页6.4.3 树和森林的遍历1.树的遍历：有两种次序先根(序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根(序)遍历：若树不空，则先依次后根遍历

21、各棵子树，然后访问根结点。第45页/共51页例：对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIA B E F C D G H IE F B C G H I D A第46页/共51页2.森林的遍历先序遍历(对森林中的每一棵树进行先根遍历)1）若森林不空，访问第一棵树的根结点；2）先序遍历第一棵树的子树森林；3）先序遍历(除第一棵树外)其余树构成的森林。中序遍历1）若森林不空，中序遍历第一棵树的子树森林；2）访问第一棵树的根结点；3）中序遍历(除第一棵树外)其余树构成的森林。第47页/共51页例：对森林进行先序遍历，获得的先序序列是：对森林进行中序遍历，获得的中序序列是：BCDEGHFIB E F C D G H IE F B C G H I D第48页/共51页总结：1.二叉树的线索化2.树的表示及其遍历操作；3.建立森林与二叉树的对应关系。第49页/共51页作业6.156.196.216.23复习课本算法6.56.66.7第50页/共51页感谢您的欣赏！第51页/共51页