实验三 全线索链表应用.docxVIP

实验三 全线索链表应用 问题定义及需求分析 1.1课题目的和任务 问题描述： 对二叉树的二叉链表结点增加两个指针域，前驱指针prior和后继指针next。通过该结点构造全线索二叉链表。 实验要求： 设计一个全线索二叉链表的应用程序。 1)创建全线索二叉树。 2)完成全线索二叉树的主要基本操作。 3)给出简单应用实例 1.2数据形式 输入数据形式：通过键盘输入数据 输入值的范围：输入值的范围均为float型，范围为1.2e-38至3.4e+38。 输出数据形式：输出到显示器。 1.3程序功能 将全线索作用于二叉排序树中，通过对其进行中序遍历线索化，实现通过线索有哪些信誉好的足球投注网站某个节点的前驱和后继，并且利用线索，实现对整个树中数据的中序线索输出，并且能够在删除树中某个节点后，实现对该树的重新线索化。 1.4测试数据 7 //树中元素的个数 5 2 7 1 3 6 8 //依次输入的树中元素值 3 //需要输出前驱和后继的元素值 7 //删除的元素值 8 //重新线索化后，需要输出前驱和后继的元素值 概要设计 2.1抽象数据类型 需要定义一个全线索二叉树，该树中含有数据，左右孩子，以及分别指向前驱和后继的指针。通过前驱和后继指针，将建立的二叉树中序线索化，从而实现对数据更方便和快速的获取。 2.2主程序流程及各模块之间的调用关系 详细设计 3.1存储结构实现 typedef struct Type{//数据类型结构体声明 float num; }Type; typedef struct BiTNode{//二叉树结构体声明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* next; }BiTNode,*BiTree; 3.2负责模块的伪码算法 （1）int visit(Type e,BiTree T){//找到相同元素并返回它的前驱和后继 if(T-data ==e) return 1; else return 0; } （2） const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type prior,Type next){//中序遍历二叉排序线索树，并返回符合visit函数的元素的前驱和后继 B=T-next; while(B非空且不等于T){ if(visit(e,B)){//找到等于e的B结点值 if(B前驱等于T){ next=B-next-data;//B只有后继 return 2; } else if(B后继等于T){ prior=B-prior-data;//B只有前驱 return 3; } else{//B前驱和后继都不等于T (prior,next)=(B-prior-data,B-next-data); return 1;//前驱和后继都存在 } } B=B-next; } return 0; } （3）const int SearchPN(BiTree Thrt,BiTree T){ //利用全线索查找所需元素的前驱和后继 cine;//输入要查找的元素 m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next); //全线索中序查找某个元素的前驱和后继 if(m==1){输出前驱和后继} else if(m==2){前驱不存在，输出后继} else if(m==3){后继不存在，输出前驱} else{查找失败，树中无该元素} return 1; } 调试分析 4.1问题分析与解决方法 对于给定输入数，查找它的前驱和后继，需要考虑该数是否存在前驱和后继，如果没有前驱和后继，则需要输出不存在标志。利用线索指针很容易进行判断，如果需要查找的元素的前驱是线索的头（线索的头是个空结点），那么该元素就不存在前驱，只存在后继；而如果需要查找的元素的后继是线索的头，那么它就不存在后继，只