第6章 树形结构 (31).ppt

《第6章 树形结构 (31).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、lchildltagdatartagrchild称采用这种结构存储的叫线索链表，二叉树的第三种存储方式。其中指示前驱和后继的链域称为线索（也就是lchild、rchild如果指向的不是左右孩子而是前驱和后继那么就称为线索）图中指向的是线索用虚线来画，否则用实线。加上线索的二叉树称为线索二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化中序线索二叉树先序线索二叉树后序线索二叉树ABCDE整体结构：增设一个头结点，使其lchild指向二叉树的根结点，并将该结点作为遍历访问的第一个结点的前驱和最后一个访问结点的后继。最后用头

2、指针指向头结点，通过这个头指针找到该棵线索二叉树ABDEC0000111111016.6.2线索化二叉树为了实现线索化二叉树,将前面二叉树结点的类型定义修改如下：typedefstructnode{ElemTypedata;/*结点数据域*/intltag,rtag;/*增加的线索标记*/structnode*lchild;/*左孩子或线索指针*/structnode*rchild;/*右孩子或线索指针*/}TBTNode;/*线索树结点类型定义*/6.6.2线索化二叉树算法设计typedefstructnode{ElemType

3、data;intltag,rtag;//增加的线索标记structnode*lchild;structnode*rchild;}TBTNode;TBTNode*CreateTBTNode(char*str)//建立二叉树（二叉链表的方式）TBTNode*CreaThread(TBTNode*b)//线索化二叉树ABDEC000011111101ABCDE算法设计TBTNode*CreaThread(TBTNode*b)//线索化二叉树ABDEC01增加一个头结点，将整棵树作为他的左孩子选择一种遍历方式，将二叉树线索化，生成某种访问

4、顺序的线索化二叉树。1100110011TBTNode*CreaThread(TBTNode*b)/*中序线索化二叉树*/{TBTNode*root;root=(TBTNode*)malloc(sizeof(TBTNode));/*创建头结点*/root->ltag=0;root->rtag=1;root->lchild=b;{pre=root;Thread(b);pre->rchild=root;pre->rtag=1;root->rchild=pre;}returnroot;}01ABDEC110011001pre1Threa

5、d(p)算法思路是：*p指向当前访问的结点*pre指向前一访问的结点采用中序遍历的方式Thread(b->lchild);printf("%c",b->data);Thread(b->rchild);当前访问结点没有左孩子，就设置为线索，指向前驱如果访问过的结点没有右孩子，则设置为线索，指向后继TBTNode*pre;/*全局变量*/voidThread(TBTNode*&p)/*对二叉树b进行中序线索化*/{if(p!=NULL){Thread(p->lchild);/*左子树线索化*/if(p->lchild==NULL)/*

6、前驱线索*/{p->lchild=pre;p->ltag=1;}/*建立当前结点的前驱线索*/elsep->ltag=0;if(pre->rchild==NULL)/*后继线索*/{pre->rchild=p;pre->rtag=1;}/*建立前驱结点的后继线索*/elsepre->rtag=0;pre=p;Thread(p->rchild);/*递归调用右子树线索化*/}}中序遍历(递归)6.6.3遍历线索化二叉树要遍历的第一个结点依次找结点的后继直到回到头结点所有的问题归结为如何找后继结点？D结点的后继：rtag=1,rchi

7、ld指向后继01ABDEC1100110011PPB结点的后继：rtag=0,rchild指向右孩子，从右孩子开始从左指针的方向找到第一个没有左孩子的结点Sif(p->rtag==1)p=p->rchild;else{p=p->rchild;while(p->ltag==0)p=p->lchild;}6.6.3遍历线索化二叉树从根结点开始找遍历的第一个结点01ABDEC1100110011tbP=tb->lchildpwhile(p->lchild!=tb)p=p->lchild;6.6.3遍历线索化二叉树1、要遍历的第一个结点2

8、、依次找结点的后继3、直到回到头结点if(p->rtag==1)p=p->rchild;else{p=p->rchild;while(p->ltag==0)p=p->lchild;}voidThInOrder(TBTNode*tb){TBTNode