资源描述：
《实验三全线索链表应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验三全线索链表应用班级:计算机1405组别：4姓名：刘诚阳学号:201437121・问题定义及需求分析1.1课题目的和任务问题描述：对二叉树的二叉链表结点增加两个指针域，前駆指针prior和后继指针nexto通过该结点构造全线索二叉链表。实验要求：设计一个全线索二叉链表的应用程序。1）创建全线索二叉树。2）完成全线索二叉树的主要基本操作。3）给出简单应用实例1.2数据形式输入数据形式：通过键盘输入数据输入值的范围：输入值的范围均为float型,范围为1.2e-38至3.4e+38。输出数据形式：输出到显示
2、器。1.3程序功能将全线索作用于二叉排序树中，通过对其进行中序遍历线索化，实现通过线索搜索某个节点的前驱和后继，并且利用线索，实现对整个树中数据的中序线索输出，并口能够在删除树中某个节点后，实现对该树的重新线索化。1.4测试数据75271368378〃树中元素的个数〃依次输入的树中元素值//需要输出前駆和后继的元素值//删除的元素值〃重新线索化后，需要输出前驱和后继的元索值2・概要设计2.1抽象数据类型需要定义一个全线索二叉树，该树中含有数据，左右孩子，以及分别指向前驱和后继的指针。通过前驱和后继指针，将建
3、立的二叉树屮序线索化,从而实现对数据更方便和快速的获取。2.2主程序流程及各模块之间的调用关系删除成功中序线索搜索并输出该数的前驱和后继SearchPN()3.详细设计2.1存储结构实现typedefstructType{//数据类型结构体声明floatnum;}Type;typedefstructBiTNode{//二叉树结构体声明structTypedata;structBiTNode*Ichild,*rchild,*prior,*next;}BiTNode,*BiTree;1.2负责模块的伪码算法(1
4、)intvisit(Typee,BiTreeT){//找到相同元素并返回它的前驱和后继if(T->data二二e)return1;elsereturn0;(2)constintTnOrderTraverse_Thr(BiTreeT,Typee,int(*visit)(Typec,BiTrccT),Typc&prior,Type&next){//中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继B=T->next;while(B非空且不等于T){if(visit(e,B)){//找到等于e的B
5、结点值if(B前驱等于T){next=B->next->data;//B只冇后继return2;}elseif(B后继等于T){prior=B->prior->data;//B只有前驱return3;}else{//B前驱和后继都不等于T(prior,next)=(B->prior->data,B->next->data);return1;//fjij驱和后继都存在}}B=B->next;}return0;(3)constintSearchPN(BiTreeThrt,BiTreeT){〃利用金线索查找所需元
6、素的前驱和后继cin»e;//输入要查找的元素m二InOrderTraverseThr(Thrt,e,(*visit),prior,next);//全线索屮序查找棄个元素的前驱和后继if(呼二1)｛输出前驱和后继｝elseif(m==2)｛前驱不存在,输出后继｝elseif(m==3)｛后继不存在,输出前驱｝else｛查找失败，树中无该元素｝return1;4•调试分析1.1问题分析与解决方法对于给定输入数，查找它的前驱和后继，需要考虑该数是否存在前驱和后继，如果没冇前驱和后继，则需要输出不存在标志。利用线
7、索指针很容易进行判断，如杲需要查找的元素的前驱是线索的头(线索的头是个空结点)，那么该元素就不存在前驱，只存在后继；而如果需要查找的元素的后继是线索的头，那么它就不存在后继，只有前駆。因此通过if进行判断，就可以成功输出需要查询的元素的前驱和后继。2.2算法的时空分析在树中查找某个元素并输出该元素的前张和后继的整个时间复杂度最多为0(町，空间复杂度为0(1)。4.3算法的改进设想全线索的应用主要是为了方便树的遍历，能够快速的访问某个节点的前驱和后继，因此口J以考虑将线索应用于平衡二叉树上，从而进一步提高平衡
8、二叉树获取数据的速度。4.4经验和体会在整个程序的编写过程中，出现一个问题，如果是首次线索化，便可以通过线索成功输出该树，但当删除某个节点后，再次进行线索化，然后利用线索输出该树就无法得到完整的树。后来经过调试发现，由于第一次的线索化，该树内的各个线索指针已被赋值，所以第二次线索化实际上是失败的，因此需要先对树进行去线索化操作(把线索指针指空)后，再对其进行线索化，这样才能输出正确的数据。可见，程序各个模块Z间的
