全线索二叉链表实验报告

全线索链表应用报告提交人：郭超峰班级：计算机1404学号：20143678一：问题定义及需求分析二：概要设计三：详细设计四：调试分析五：使用说明六:测试结果（截屏）七：组内个人设计部分八：附录（带源代码）一：问题定义及需求分析课题：全线索链表应用课题描述：对二叉树的二叉链表结点增加两个指针域，前驱指针prior和后继指针next。通过该结点构造全线索二叉链表。课题要求：设计一个全线索二叉链表的应用程序。1)创建全线索二叉树。2)完成全线索二叉树的主要基本操作。3)给出简单应用实例。输入输出形式：本实验中全线索二叉树元素均为整形（int）。程序功能：1：创建二叉树。2：对二叉树中序遍历进行全线索化。3：求树中任意元素的前驱、后继、左孩子、右孩子。4：对二叉树进行元素的插入和删除。5：对二叉树的清空操作。测试数据：测试的二叉树为如下12345678二：概要设计typedefstructBiThrNode{intdata;structBiThrNode*lchild,*rchild,*prior,*next;}BiThrNode,*BiThrTree;//抽象数据类型BiThrNodetypedefstruct{ElemTypedata[100];intStacksize;}SqStack;//抽象数据类型SqStackvoid*InitStack(SqStack*p);//初始化栈intStackEmpty(SqStack*S);//判断栈空intPush(SqStack*S,ElemTypee);//入栈ElemTypePop(SqStack*S,ElemTypee);//出栈BiThrTreeCreatBiTree(BiThrTreep);//二叉树的构建BiThrTreeInOrderThreading(BiThrTreep);//中序线索化intInOrder(BiThrTreep);//求中序序列intqianqu(BiThrTreep);//求前驱inthouji(BiThrTreep);//求后继intzuohai(BiThrTreep);//求左孩子intyouhai(BiThrTreep);//求右孩子intInsert(BiThrTreep);//插入元素intDelete(BiThrTreep);//删除元素intClear(BiThrTreep);//将二叉树清空Intmain()//主函数调用上述函数求解相应问题三：详细设计各模块的算法如下：StatusInitStack(SqStack*p){//初始化栈p.Stacksize=-1;returnOK;}StatusStackEmpty(SqStack*S){//判断栈空if(p-Stacksize=-1)returnTURE;elsereturnFALSE;}StatusPush(SqStack*S,ElemTypee){//入栈P-Stacksize=p-Stacksize+1;P-data[p-Stacksize]=e;returnOK;}StatusPop(SqStack*S,ElemTypee){//出栈e=p-data[p-Stacksize];P-Stacksize=p-Stacksize-1;returne;}StatusCreatBiTree(BiThrTreep){//二叉树的构建scanf(&m);if(m==0)p=NULL;else{if(!(p=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);//存储分配失败else{p-data=m;p-prior=NULL;p-next=NULL;p-lchild=NULL;p-rchild=NULL;p-lchild=CreatBiTree(p-lchild);//递归构建左子树p-rchild=CreatBiTree(p-rchild);//递归构建右子树}}returnp;//返回头节点}StatusInOrderThreading(BiThrTreep){//中序线索化InitStack(&S);if(!(Thr=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);//存储分配失败Thr-data=0;Thr-lchild=p;//Thr为头节点Thr-rchild=NULL;p1=p;pre=Thr;//pre为全局变量，指向p1的前一个节点while(p1||!StackEmpty(&S)){if(p1){Push(&S,p1);p1=p1-lchild;//进栈}else{p1=Pop(&S,p1);//出栈pre-next=p1;p1-prior=pre;//中序线索化pre=p1;p1=p1-rchild;}}pre-next=Thr;//最后一个节点线索化Thr-prior=pre;returnThr;//返回头节点}StatusInOrder(BiThrTreep){//求中序序列for(p1=p-next;p1!=p;p1=p1-next){printf(p1-data);//输出节点值}求前驱、后继、左孩子、右孩子思路差距不大，下面以求前驱为例：Statusqianqu(BiThrTreep){//求前驱scanf(&e);//输入要查找元素for(p2=p-next;p2-data!=0;p2=p2-next){//逐个检查树中元素if(p2-data==e){p3=p2-prior;if(p3-data==0){Printf(“该点不存在中序前驱！”)；break;}else{printf(该点的中序前驱为：);printf(p3-data);//输出e的前驱break;}}}StatusInsert(BiThrTreep){//插入元素p2=(BiThrTree)malloc(sizeof(BiThrNode));printf(输入所要插入的节点：);scanf(&a);printf(输入所要查找的节点：);scanf(&b);for(p1=p-next;p1!=p;p1=p1-next){//逐个检查树中元素if(p1-data==b)break;}if(p1==p)printf(该节点不存在！\n);else{switch(j){case1:{//插入元素作为左孩子p2-data=a;p2-lchild=NULL;p2-rchild=NULL;p2-next=p1;p2-prior=p1-prior;p1-prior-next=p2;p1-prior=p2;p1-lchild=p2;break;}case2:{//插入元素作为右孩子p2-data=a;p2-lchild=NULL;p2-rchild=NULL;p2-prior=p1;p2-next=p1-next;p1-next-prior=p2;p1-next=p2;p1-rchild=p2;break;}default:exit(0);}}//switch}//else}StatusDelete(BiThrTreep){//删除元素scanf(&a);//输入要删除的元素for(p1=p-next;p1!=p;p1=p1-next){//逐个检查树中是否有此元素if(p1-data==a)break;}if(p1==p)printf(该树中无此节点！);else{if(p1==p1-prior-rchild){//元素作为右孩子p1-prior-next=p1-next;p1-next-prior=p1-prior;p1-prior-rchild=NULL;free(p1);//释放P1}if(p1==p1-next-lchild){//元素作为左孩子p1-prior-next=p1-next;p1-next-prior=p1-prior;p1-next-lchild=NULL;free(p1);//释放p1}}//else}//DeleteStatusClear(BiThrTreep){//将二叉树清空for(p1=p-next;p2!=p;){p2=p1-next;free(p1);//释放节点p1p1=p2;}free(p);//释放头节点}四：调试分析1：对所遇到问题的解决方法及分析1）建立二叉树时遇到问题：输入时未使用0来表明无左右孩子，导致递归无法结束，原因是为理解递归建立二叉树的过程。2）建立二叉树后进行相应问题的求解后，无法进行多次求解，经分析后采用子函数相互调用的方法顺利解决。3）其余一些程序语法及逻辑错误，经组内成员严谨排查顺利解决2：算法的时空分析及改进设想1）算法时空分析：相应算法的时间复杂度均为O（n）2）改进设想：1）可以使用函数指针来使用求前驱、后继、左孩子、右孩子等子函数。2）或许可以使用一子函数代替程序中实现多次求解的代码，简化程序。五：使用说明如下依次输入12400560800700300得到原始二叉树：然后进入菜单界面如下：之后按步骤进行相应问题求解！六：测试结果（截屏）第一项测试：求6的前驱得到2，测试成功！第二项测试：求5的后继得到7，测试成功！第三项测试：求5的左孩子得到6，测试成功！第四项测试：求2的右孩子得到5，测试成功！第五项测试：将9插入做为6的左孩子，测试成功！第六项测试：删除节点4后求2的左孩子，结果不存在，测试成功！第七项测试：求中序序列得到42685713，测试成功！七：组内个人设计部分typedefstructBiThrNode{intdata;structBiThrNode*lchild,*rchild,*prior,*next;}BiThrNode,*BiThrTree;//抽象数据类型BiThrNodeBiThrTreeCreatBiTree(BiThrTreep);//二叉树的构建BiThrTreeInOrderThreading(BiThrTreep);//中序线索化intInsert(BiThrTreep);//插入元素intDelete(BiThrTreep);//删除元素Intmain()//主函数调用上述函数求解相应问题intInOrder(BiThrTreep);//求中序序列intqianqu(BiThrTreep);//求前驱七：附录（带源程序）注：算法中已经带有注释，故下列代码不重复含注释！#includestdio.h#includestdlib.h#defineINIT_STACK_SIZE100#defineSTACKINCREMENT10#defineOVERFLOW-2#defineERROR-1#defineOK1typedefstructBiThrNode{intdata;structBiThrNode*lchild,*rchild,*prior,*next;}BiThrNode,*BiThrTree;typedefBiThrNode*ElemType;typedefstruct{ElemTypedata[100];intStacksize;}SqStack;BiThrTreepre;intmain(){BiThrTreeCreatBiTree(BiThrTreep);BiThrTreeInOrderThreading(BiThrTreep);intInOrder(BiThrTreep);intqianqu(BiThrTreep);inthouji(BiThrTreep);intzuohai(BiThrTreep);intyouhai(BiThrTreep);intInsert(BiThrTreep);intDelete(BiThrTreep);intClear(BiThrTreep);inta;