算法5线索二叉树ppt课件.ppt

《算法5线索二叉树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.4线索二叉树1线索二叉树6.4.1线索二叉树的定义6.4.2线索二叉树的遍历算法2目的：利用二叉树的空指针保存遍历序列的前驱和后继。n个结点的二叉树,有2n个指针,只用了n-1个,有n+1个是空指针。用空的左指针指向某一遍历序列的前驱.用空的右指针指向某一遍历序列的后继.这两种指针称为线索(Thread)。为了区分线索与真实指针，给结点增加两个域Ltag和Rtag6.4.1线索二叉树的概念3lchildLtagdataRtagrchildLtag=0:lchild指向结点的左子女；Ltag=1:lchild指向某一遍历序列前驱；Rtag=0:rchild指向结点的右子

2、女；Rtag=1:rchild指向某一遍历序列后继；6.4.1线索二叉树的概念4//二叉树的二叉线索存储表示typedefenum{Link,Thread}PointerTag;//Link==0：指针，Thread==1：线索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;//左右孩子指针PointerTagLTag,RTag;//左右标志}BiThrNode,*BiThrTree;lchildLtagdataRtagrchild6.4.1线索二叉树的概念5加了线索的二叉树是线索二叉

3、树；给二叉树加线索的过程是线索化（穿线）；按前序遍历序列穿线的二叉树是前序线索二叉树；按中序遍历序列穿线的二叉树是中序线索二叉树；按后序遍历序列穿线的二叉树是后序线索二叉树；中序线索二叉树简称线索二叉树；6加了线索的二叉树是线索二叉树；二叉树加线索的过程是线索化（穿线）；按前序遍历序列穿线的二叉树是前序线索二叉树；按中序遍历序列穿线的二叉树是中序线索二叉树；按后序遍历序列穿线的二叉树是后序线索二叉树；中序线索二叉树简称线索二叉树；6.4.1线索二叉树的概念7线索二叉树(ThreadedBinaryTree)AGDBFcE（a）二叉树A00C00E11F11B0101D1O

4、G11（b）先序线索树rootABDGCEF8线索二叉树(ThreadedBinaryTree)AGDBFCE（a）二叉树A00C00E11F11B0101D1OG11（c）中序线索树rootDGBAECF9线索二叉树(ThreadedBinaryTree)AGDBFCE（a）二叉树A00C00E11F11B0101D1OG11（d）后序线索树rootGDBEFCA10DBFEACNULLNULL中序线索二叉树线索二叉树(ThreadedBinaryTree)116.4.2线索二叉树的遍历算法算法6.5：中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。

5、T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法。StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){p=T->lchild;//p指向根结点while(p!=T){//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild);if(!Visit(p->data))returnERROR;//访问其左子树为空的结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//

6、访问后继结点}p=p->rchild;}returnOK;}//InOrderTraverse_Thr126.4.2线索二叉树的遍历算法算法6.6：中序遍历二叉树T，并将其中序线索化，Thrt指向头结点StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;//建头结点Thrt->rchild=Thrt;//右指针回指if(!T)Thrt

7、->lchild=Thrt;//若二叉树空，则左指针回指else{Thrt->lchild=Thrt;pre=Thrt;InThreading(T);//中序遍历进行中序线索化pre->rchild=Thrt;pre->RTag=Thread;//最后一个结点线索化Thrt->rchild=pre;}returnOK;}//InOrderThreading136.4.2线索二叉树的遍历算法voidINThreading(BiThrTreep){if(p){InThreading(p->lchild);//左子树线索化if(!p