软件技术基础课件_第1页
软件技术基础课件_第2页
软件技术基础课件_第3页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

2.5.5穿线二叉穿线二叉树的概遍历二叉树实为把非线性结构线性化了，而这种线性有序的信息是否可以在结构中保持住呢？即保持其。穿线二叉树为我们提供了肯定的答案。穿线二叉树是二叉树的一种方式，是二叉树以一个新结点和删除一个指定结点等运算。18-在原二叉树上建立线建立线索的过程就是线性化的过，即边遍历边建立线索，遍历完成，线索建好。根据二叉树的链式 结构我们注意到：当一颗有n个结点的二叉树，便有n+个指针域存放着空NU。这是因为，n各结点一共有2n个指针域，除根结点外，每个结点有且仅有一个指向它的指针，于是共有1个指针，即只有n个指针域被有效使用。那些空值的指针域，正好被用来构造穿线二叉树。18-由此得到具体做法是，利用空值域装线索，若一个结lchid存放前驱线索；同样若结点的右孩子为空，则用空值域chid放后继线索。lag和fagtemplatestructTd;//数据intlflag;//左标志intrflag;//右标志

=0，lchild指向结点的左子=1，lchild指向结点的前驱线=0，rchild指向结点的右子结=1，rchild指向结点的后继线TTnode*lchild;//左指针TTnode*rchild;//右指针}18-18-中序穿线二叉树的构算法思 到的结点序号（指针）填入，并置右标域为1 到的结点序号（指针）填入，并置左标域为118-template<classstaticin_threaded(TTnode<T>*p,TTnode<T>{{in_threaded(p->lchild,//若上 到的结点的右指针为//则将当 到的结点序号填入，并置右标志域为if((*h!=NULL)&&((*h)-{(*h)->rchild=p;(*h)->rflag=1;//若当 到的结点的左指针为//则将上 到的结点序号填入，并置左标志域为if(p-{p->lchild=*h;p-in_threaded(p->rchild,}return}18-中序穿线二叉树的遍算法思首先，从二叉树的根结点开始该叶子结点即为中序序列的第一个结点然后从中序序列的第一个结点开始扫描，依次找出中序列中的后件。其规则如下若当前结点的右标志值为，则当前结点的右指针域值为其后件的序号。若当前结点的右标志值为，则沿右子树的左链进行搜索，直到发现某个结点的左标志值为1且左指针值不空为止，该结点即为当前结点的后件。18-中序线索二叉链表的遍template<classvoid{TTnode<T>*p;if(BT==NULL)return;二叉链表为空while(p->lflag==0)p=p->lchild;//沿左链找到叶子结点cout<<p->d<<““; while(p->rchild!=NULL)//沿右链扫描后件{if(p->rflag==1)p=p- //沿右子树的左链扫whil

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论