全线索二叉链表实验报告.docx

全线索链表应用报告提交人：郭超峰 班级：计算机1404学号：20143678一：问题定义及需求分析二：概要设计三：详细设计四：调试分析五：使用说明六:测试结果（截屏）七：组内个人设计部分八：附录（带源代码）一：问题定义及需求分析课题：全线索链表应用课题描述：对二叉树的二叉链表结点增加两个指针域，前驱指针prior和后继指 针next。通过该结点构造全线索二叉链表。课题要求：设计一个全线索二叉链表的应用程序。1)创建全线索二叉树。2)完成全线索二叉树的主要基本操作。3)给出简单应用实例。输入输出形式：本实验中全线索二叉树元素均为整形（int）。程序功能：1：创建二叉树。2：对二叉树中序遍历进行全线索化。3：求树中任意元素的前驱、后继、左孩子、右孩子。4：对二叉树进行元素的插入和删除。5：对二叉树的清空操作。测试数据：测试的二叉树为如下18765432二：概要设计typedef struct BiThrNodeint data;struct BiThrNode *lchild,*rchild,*prior,*next;BiThrNode,*BiThrTree; /抽象数据类型BiThrNodetypedef structElemType data100;int Stacksize;SqStack; /抽象数据类型SqStackvoid *InitStack(SqStack *p); /初始化栈int StackEmpty(SqStack *S); /判断栈空int Push(SqStack *S,ElemType e); /入栈ElemType Pop(SqStack *S,ElemType e); /出栈BiThrTree CreatBiTree(BiThrTree p); /二叉树的构建BiThrTree InOrderThreading(BiThrTree p); /中序线索化int InOrder(BiThrTree p); /求中序序列int qianqu(BiThrTree p); /求前驱int houji(BiThrTree p); /求后继int zuohai(BiThrTree p); /求左孩子int youhai(BiThrTree p); /求右孩子int Insert(BiThrTree p); /插入元素int Delete(BiThrTree p); /删除元素int Clear(BiThrTree p); /将二叉树清空Int main() /主函数调用上述函数求解相应问题三：详细设计各模块的算法如下：Status InitStack(SqStack *p) /初始化栈p.Stacksize=-1;return OK;Status StackEmpty(SqStack *S) /判断栈空if(p-Stacksize=-1)return TURE;else return FALSE;Status Push(SqStack *S,ElemType e) /入栈P-Stacksize=p-Stacksize+1;P-datap-Stacksize=e;return OK;Status Pop(SqStack *S,ElemType e) /出栈e=p-datap-Stacksize;P-Stacksize=p-Stacksize-1;return e;Status CreatBiTree(BiThrTree p) /二叉树的构建scanf(&m);if(m=0) p=NULL;elseif(!(p=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); /存储分配失败 elsep-data=m;p-prior=NULL;p-next=NULL;p-lchild=NULL;p-rchild=NULL;p-lchild=CreatBiTree(p-lchild); /递归构建左子树p-rchild=CreatBiTree(p-rchild); /递归构建右子树return p; /返回头节点Status InOrderThreading(BiThrTree p) /中序线索化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; return Thr; /返回头节点Status InOrder(BiThrTree p) /求中序序列for(p1=p-next;p1!=p;p1=p1-next) printf(p1-data); /输出节点值求前驱、后继、左孩子、右孩子思路差距不大，下面以求前驱为例：Status qianqu(BiThrTree p) /求前驱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; Status Insert(BiThrTree p) /插入元素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) case 1: /插入元素作为左孩子 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; case 2: /插入元素作为右孩子 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/elseStatus Delete(BiThrTree p) /删除元素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/DeleteStatus Clear(BiThrTree p) /将二叉树清空 for(p1=p-next;p2!=p;) p2=p1-next;free(p1); /释放节点p1 p1=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，测试成功！七：组内个人设计部分typedef struct BiThrNodeint data;struct BiThrNode *lchild,*rchild,*prior,*next;BiThrNode,*BiThrTree; /抽象数据类型BiThrNodeBiThrTree CreatBiTree(BiThrTree p); /二叉树的构建BiThrTree InOrderThreading(BiThrTree p); /中序线索化int Insert(BiThrTree p); /插入元素int Delete(BiThrTree p); /删除元素Int main() /主函数调用上述函数求解相应问题int InOrder(BiThrTree p); /求中序序列int qianqu(BiThrTree p); /求前驱七：附录（带源程序） 注：算法中已经带有注释，故下列代码不重复含注释！#include#include#define INIT_STACK_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -2#define ERROR -1#define OK 1typedef struct BiThrNodeint data;struct BiThrNode *lchild,*rchild,*prior,*next;BiThrNode,*BiThrTree;typedef BiThrNode* ElemType;typedef structElemType data100;int Stacksize;SqStack;BiThrTree pre;int main() BiThrTree CreatBiTree(BiThrTree p); BiThrTree InOrderThreading(BiThrTree p); int InOrder(BiThrTree p); int qianqu(BiThrTree p); int houji(BiThrTree p); int zuohai(BiThrTree p); int youhai(BiThrTree p); int Insert(BiThrTree p); int Delete(BiThrTree p); int Clear(BiThrTree p); int a; BiThrTree T; T=NULL; printf(构造二叉树：n); T=CreatBiTree(T); printf(二叉树建立完成！n); T=InOrderThreading(T); system(cls); printf(*全线索二叉树*n); printf(*1:求前驱*n); printf(*2:求后继*n); printf(*3:求左孩子*n); printf(*4:求右孩子*n); printf(*5:插入元素*n); printf(*6:删除元素*n); printf(*7:求中序序列*n); printf(*8:清空二叉树并退出*n); printf(输入要进行的项目：); scanf(%d,&a); switch(a) case 1:qianqu(T);break; case 2:houji(T);break; case 3:zuohai(T);break; case 4:youhai(T);break; case 5:Insert(T);break; case 6:Delete(T);break; case 7:InOrder(T);break; case 8:Clear(T); exit(0); return OK;int InitStack(SqStack *p)p-Stacksize=-1;return 0;int Push(SqStack *p,ElemType e)p-Stacksize=p-Stacksize+1;p-datap-Stacksize=e; return 0;ElemType Pop(SqStack *p,ElemType e)e=p-datap-Stacksize;p-Stacksize=p-Stacksize-1;return e;BiThrTree CreatBiTree(BiThrTree p)int m;printf(输入元素：n);scanf(%d,&m);if(m=0)p=NULL;elseif(!(p=(BiThrTree)malloc(sizeof(BiThrNode)exit (0);elsep-data=m;p-prior=NULL;p-next=NULL;p-lchild=NULL;p-rchild=NULL;p-lchild=CreatBiTree(p-lchild);p-rchild=CreatBiTree(p-rchild);return p;int StackEmpty(SqStack *p)if(p-Stacksize=-1)return 1;else return 0;BiThrTree InOrderThreading(BiThrTree p)int InitStack(SqStack *p);int StackEmpty(SqStack *S);int Push(SqStack *S,ElemType e);ElemType Pop(SqStack *S,ElemType e);BiThrTree Thr;SqStack S;InitStack(&S);BiThrTree p1;if(!(Thr=(BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW); Thr-data=0; Thr-lchild=p; Thr-rchild=NULL; p1=p; pre=Thr; 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; printf(二叉树线索化完成！n); return Thr;int qianqu(BiThrTree p) int houji(BiThrTree p); int zuohai(BiThrTree p); int youhai(BiThrTree p); int Insert(BiThrTree p); int InOrder(BiThrTree p); int Delete(BiThrTree p); int Clear(BiThrTree p);int e,m,j;printf(输入要查找的元素：);scanf(%d,&e);BiThrTree p2;BiThrTree p3;for(p2=p-next;p2-data!=0;p2=p2-next) if(p2-data=e) p3=p2-prior; if(p3-data=0) printf(该点不存在中序前驱！n); break; else printf(该点的中序前驱为：); printf(%dn,p3-data); break; printf(继续按1，退出按0n); scanf(%d,&j); if(j) printf(输入要进行的项目：); scanf(%d,&m); switch(m) case 1:qianqu(p);break; case 2:houji(p);break; case 3:zuohai(p);break; case 4:youhai(p);break; case 5:Insert(p);break; case 6:Delete(p);break; case 7:InOrder(p);break; case 8:Clear(p); exit(0); else exit(0);return 0;int houji(BiThrTree p) int qianqu(BiThrTree p); int zuohai(BiThrTree p); int youhai(BiThrTree p); int Insert(BiThrTree p); int InOrder(BiThrTree p); int Delete(BiThrTree p); int Clear(BiThrTree p); int e,m,j;printf(输入要查找的元素：);scanf(%d,&e);BiThrTree p2;BiThrTree p3;for(p2=p-next;p2!=p;p2=p2-next) if(p2-data=e) p3=p2-next; if(p3-data=0) printf(该点不存在中序后继！n); break; else printf(该点的中序后继为：); printf(%dn,p3-data); break; printf(继续按1，退出按0n); scanf(%d,&j); if(j) printf(输入要进行的项目：); scanf(%d,&m); switch(m) case 1:qianqu(p);break; case 2:houji(p);break; case 3:zuohai(p);break; case 4:youhai(p);break; case 5:Insert(p);break; case 6:Delete(p);break; case 7:InOrder(p);break; case 8:Clear(p); exit(0); else exit(0); return 0;int zuohai(BiThrTree p) int qianqu(BiThrTree p); int houji(BiThrTree p); int youhai(BiThrTree p); int Insert(BiThrTree p); int InOrder(BiThrTree p); int Delete(BiThrTree p); int Clear(BiThrTree p); int e,m,j;printf(输入要查找的元素：);scanf(%d,&e);BiThrTree p2;BiThrTree p3;for(p2=p-next;p2!=p;p2=p2-next) if(p2-data=e) p3=p2-lchild; if(p3=NULL) printf(该点不存在左孩子！n); break; else printf(该点的左孩子为：); printf(%dn,p3-data); break; printf(继续按1，退出按0n); scanf(%d,&j); if(j) printf(输入要进行的项目：); scanf(%d,&m); switch(m) case 1:qianqu(p);break; case 2:houji(p);break; case 3:zuohai(p);break; case 4:youhai(p);break; case 5:Insert(p);break; case 6:Delete(p);break; case 7:InOrder(p);break; case 8:Clear(p); exit(0); else exit(0); return 0;int youhai(BiThrTree p) int qianqu(BiThrTree p); int houji(BiThrTree p); int zuohai(BiThrTree p); int Insert(BiThrTree p); int InOrder(BiThrTree p); int Delete(BiThrTree p); int Clear(BiThrTree p); int e,m,j;printf(输入要查找的元素：);scanf(%d,&e);BiThrTree p2;BiThrTree p3;for(p2=p-next;p2!=p;p2=p2-next) if(p2-data=e) p3=p2-rchild; if(p3=NULL) printf(该点不存在右孩子！n); break; else printf(该点的右孩子为：); printf(%dn,p3-data); break; printf(继续按1，退出按0n); scanf(%d,&j); if(j) printf(输入要进行的项目：); scanf(%d,&m); switch(m) case 1:qianqu(p);break; case 2:houji(p);break; case 3:zuohai(p);break; case 4:youhai(p);break; case 5:Insert(p);break; case 6:Delete(p);break; case 7:InOrder(p);break; case 8:Clear(p); exit(0); else exit(0); return 0;int InOrder(BiThrTree p) int qianqu(BiThrTree p); int houji(BiThrTree p); int zuohai(BiThrTree p); int youhai(BiThrTree p); int Insert(BiThrTree p); int Delete(BiThrTree p); int Clear(BiThrTree p);BiThrTree p1;int j,m;printf(中序序列为：n);for(p1=p-next;p1!=p;p1=p1-next) printf(%d,p1-data);printf(n); printf(继续按1，退出按0n); scanf(%d,&j); if(j) printf(输入要进行的项目：); scanf(%d,&m); switch(m) case 1:qianqu(p);break; case 2:houji(p);break; case 3:zuohai(p);break; case 4:youhai(p);break; case 5:Insert(p);break; case 6:Delete(p);break; case 7:InOrder(p);break; case 8:Clear(p); exit(0); else exit(0);return 0;int Insert(BiThrTree p) int qianqu(BiThrTree p); int houji(BiThrTree p); int zuohai(BiThrTree p); int youhai(BiThrTree p); int InOrder(BiThrTree p); int Delete(BiThrTree p); int Clear(BiThrTree p);int a,b,i,j,m;BiThrTree p1,p2;p2=(BiThrTree)malloc(sizeof(BiThrNode);printf(输入所要插入的节点：);scanf(%d,&a);printf(输入所要查找的节点：);scanf(%d,&b);for(p1=p-next;p1!=p;p1=p1-next) if(p1-data=b) break;if(p1=p) printf(该节点不存在！n);else printf(*1：插入为左孩子*n); printf(*2：插入为右孩子*n); printf(选择操作：); scanf(%d,&j); switch(j) case 1: 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; case 2: 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