线索二叉树算法的实现

线索二叉树算法的实现 数据结构课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 线索二叉树算法的实现 学生姓名 学号 班级 信管091 成绩 指导教师 计算机科学与技术系 2011 年3月4日 数据结构课程设计评阅书 题 目 线索二叉树算法的实现 学生姓名 学号 指导教师评语及成绩 成绩: 教师签名: 年 月 日 答辩教师评语及成绩 成绩: 教师签名: 年 月 日 教研室意见 总成绩: 室主任签名: 年 月 日 课程设计任务书 2010—2011学年第2 学期 专业:信息管理与信息技术 学号: 设计题目: 线索二叉树算法的实现 完成期限:自 2011 年 2 月21 日至 2011 年 3 月 4 日共 2 周 设计依据、 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 及主要内容(可另加附页): 设计要求: 1)问题分析和任务定义:根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么,(而不是怎么做,)限制条件是什么,确定问题的输入数据集合。 2)逻辑设计:对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图; 3)详细设计:定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架; 4)程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚; 5)程序调试与测试:能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果; 6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析; 7)编写课程设计报告; 以上要求中前三个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。 指导教师(签字): 教研室主任(签字): 批准日期: 年 月 日 摘 要 设计了一个线索二叉树的软件，该软件具有创建二叉树、线索二叉树、先序线索二叉树、中序线索二叉树、后序线索二叉树的功能。本软件采用VC++作为软件开发环境，采用C语言各种语句和结构实现二叉树的一系列操作，并采用友好界面向用户提示所操作过程和所输入数据方式，操作简单，界面清晰，易于为用户所接受。 关键字:线索;二叉树;先序;中序;后序 目 录 1 课题描述 .................................................................. 1 2 问题分析和任务定义 ......................................................... 2 3 逻辑设计 .................................................................. 3 4 详细设计 .................................................................. 7 5 程序编码 .................................................................. 9 6 程序调试与测试............................................................ 19 7 结果分析 ................................................................. 20 8 总结 ..................................................................... 21 参考文献 ................................................................... 22 1 课题描述 本系统重在设计二叉树的各种线索化实现，通过C语言作为编程语言，实现对二叉树的线索化，其中包括先序线索化、中序线索化以及后序线索化。旨在使用户在使用过程中能学会直接调用各种所需函数，以及掌握对二叉树的各种线索化过程。其中各函数分别为:BiThrTree CreateBiTree(BiThrTree &T); //构造二叉树 void PreOrderTraverse(BiThrTree T); //先序遍历二叉树(递归算法) void InOrderTraverse(BiThrTree T); //中序遍历二叉树(递归算法) void PosOrderTraverse(BiThrTree T); //后序遍历二叉树(递归算法) void PreOrder_Stack_Traverse(BiThrTree T); //先序遍历二叉树(非递归算法) void InOrder_Stack_Traverse(BiThrTree T); //中序遍历二叉树(非递归算法) Status PreOrderThreading(BiThrTree &Thrt, BiThrTree T); //先序线索化二叉树 void PreThreading(BiThrTree p); Status InOrderThreading(BiThrTree &Thrt, BiThrTree T); //中序线索化二叉树 void InThreading(BiThrTree p); void PreOrderTraverse_Thr(BiThrTree Thrt); //先序遍历线索化二叉树 void InOrderTraverse_Thr(BiThrTree Thrt); //中序遍历线索化二叉树 void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T); //将线索化二叉树还原 开发工具:c语言 运行环境:Visual c++6.0。 1 2 问题分析和任务定义 本软件要求制作一个能对二叉树线索化的软件，其中包括对二叉树的先序、中序、后序线索化，最后遍历线索化并输出。其中线索化要实现对同一个树的线索化，即应具备还原线索化树的程序，并重新线索化。 构造二叉树 线中后中线 序序续序序中线先遍遍遍遍遍序索序历历历历历线化线)))))索还索递递递递递化原化归归归归归 ))))) 图2.1 模块流程图 2 3 逻辑设计 本程序由主函数首先调用BiThrTree CreateBiTree(BiThrTree &T);构造二叉树，随后依次调用 函数 (1)BiThrTree CreateBiTree(BiThrTree &T); //构造二叉树 void PreOrderTraverse(BiThrTree T); //先序遍历二叉树(递归算法) void InOrderTraverse(BiThrTree T); //中序遍历二叉树(递归算法) void PosOrderTraverse(BiThrTree T); //后序遍历二叉树(递归算法) void PreOrder_Stack_Traverse(BiThrTree T); //先序遍历二叉树(非递归算法) void InOrder_Stack_Traverse(BiThrTree T); //中序遍历二叉树(非递归算法) Status PreOrderThreading(BiThrTree &Thrt, BiThrTree T); //先序线索化二叉树 void PreThreading(BiThrTree p); Status InOrderThreading(BiThrTree &Thrt, BiThrTree T); //中序线索化二叉树 void InThreading(BiThrTree p); void PreOrderTraverse_Thr(BiThrTree Thrt); //先序遍历线索化二叉树 void InOrderTraverse_Thr(BiThrTree Thrt); //中序遍历线索化二叉树 void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T); //将线索化二叉树还原; 依次完成先中后遍历和先序和中序线索化 begin开 始 S.top-N S.base>=S.stacksiChar chzeS.base=(BiThrTree*)reallocY(S.base,(S.stacksize+STANCKINCREMENT)*sizeof(BiCh==’#’ThrNode));NY!S.base!(T=(BiThree)) T=NULLY N Return FALSE exist(OVERFLOW); YT->date=ch S.top=S.base+S.st acksize;return T 结束END 图3.1 Creatbitre 图 3.2 Push *S.top++=e;(创建二叉树) (入栈) 3 returnOK; begin开 始 SqStacksN S.top==S.base YP||StackEmpty NReturn FALSE;Y P NYe=*--S.top; cout<<” ”<datePop(s,p) returnOK; End结 束 图3.3 Pop 图3.4 Perorder_2_Trave (出栈) (先序非递归遍历) 开 始开始 SqStacksThrt=(BiThrTree)malloc(.) NP||StackEmpty!TN YYPThrt->lchild=Thrt;Thrt->lchild=T;NY Push(s,p)Pop(s,p) return OK; 结 束结 束 图 3.5 Inorder_2_Trave 图 3.6 PerorderThreading (中序非递归遍历) (先序索引) 4 开 始 开始NP YN!p->lchildThrt=(BiThrtree)malloc() Y NP->lchild=pre;Y!T YN!pre->rchild Thrt->=Thrt;Thrt->lchild=T; YPre->rchild=p; PreThreading(p->lchild)N NPre=p;return OK;P->Rtag==LinkY P->Ltag==Link结 束PreThreading(p->rchild)结 束 图 3.8 InorderThreading 图 3.7 PerThreading (中序索引) begin开 始 BiThrTreep;P NYp!=Thrt InThreading(p->lchild) cout<<" "<data; N!p->lchildp->LTag==Link YP->Ltag=Thread;p=p->lchild;P->lchild=per; (p->RTag==Thread)&&(p->rchild!=Thrt)!pre->rchildp=p->rchild; N p->LTag==LinkPre->Rtag=Thread; Yp=p->lchild;p=p->rchild;Pre=p; 结 束END 图 3.10 PerorderTravese 图 3.9 InThreading 5 (先序索引输出) beginbegin BiThrTreep;BiThrTreep,post; NNp!=Thrtp!=Thrt YYNNp->LTag==Linkp->LTag==LinkY YP=p->lchild;p=p->lchild; p->LTag=Link;cout<<" "<data;N(p->RTag==Thread)&&(p->rchild!=Thrt)YN(p->RTag==Thread)&&(p->rchild!=Thrt)p->RTag=Link;Y p=p->rchild; p=p->rchild;p=p->rchild; p=Thrt->rchild; ENDEND 图 3.11 InorderTrave 图 3.12 Inorder_Thrt (中序线索输出) (线索还原) 6 4 详细设计 首先定义二叉树的存储结构如下: typedef enum PointerTag {Link,Thread}; //Link==0:指针，Thread==1:线索 typedef struct BiThrNode { //线索二叉树中结点的定义 char data; int LTag,RTag; struct BiThrNode *lchild,*rchild; }BiThrNode,*BiThrTree; 然后定义栈的存储结构: typedef struct { BiThrTree *base; BiThrTree *top; int stacksize; }SqStack; 其中二叉树的遍历可用递归和非递归两种算法实现，递归可根据如下算法实现: void PreOrderTraverse(BiThrTree T) //先序遍历 { if (T){ cout<<" "<data; /*访问根结点*/ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } 中序和后序只需改变访问次序即可;在进行进行非递归遍历时可根据栈的访问顺序依次遍历。最后线索化该二叉树也可根据递归的算法实现，其中先序线索递归实现可根据 void PreThreading(BiThrTree p) { if (!p->lchild) //先驱线索 if (p) { { p->lchild=pre; p->LTag=Thread; } if (!pre->rchild) { //后继线索 pre->rchild=p; pre->RTag=Thread; } pre = p; if(p->LTag==Link) PreThreading(p->lchild); //左子树线索化 7 if(p->RTag ==Link) PreThreading(p->rchild); } //右子树线索化 } 后续也只需改变线索化顺序即可。但在中序线索化后程序会自动还原线索化再进行先序线索化。 8 5 程序编码 #include #include #include #include #include #define OK 1 #define FALSE 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -1 typedef int Status; typedef enum PointerTag {Link,Thread}; //Link==0:指针，Thread==1:线索 typedef struct BiThrNode { //线索二叉树中结点的定义 char data; int LTag,RTag; struct BiThrNode *lchild,*rchild; }BiThrNode,*BiThrTree; //函数声明 BiThrTree CreateBiTree(BiThrTree &T); //构造二叉树 void PreOrderTraverse(BiThrTree T); //先序遍历二叉树(递归算法) void InOrderTraverse(BiThrTree T); //中序遍历二叉树(递归算法) void PosOrderTraverse(BiThrTree T); //后序遍历二叉树(递归算法) void PreOrder_Stack_Traverse(BiThrTree T); //先序遍历二叉树(非递归算法) void InOrder_Stack_Traverse(BiThrTree T); //中序遍历二叉树(非递归算法) Status PreOrderThreading(BiThrTree &Thrt, BiThrTree T); //先序线索化二叉树 void PreThreading(BiThrTree p); Status InOrderThreading(BiThrTree &Thrt, BiThrTree T); //中序线索化二叉树 void InThreading(BiThrTree p); void PreOrderTraverse_Thr(BiThrTree Thrt); //先序遍历线索化二叉树 void InOrderTraverse_Thr(BiThrTree Thrt); //中序遍历线索化二叉树 void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T); //将线索化二叉树还原 9 //构建二叉树 BiThrTree CreateBiTree(BiThrTree &T){ char ch; //BiThrTree T; cin>>ch; //从键盘输入ch; if(ch=='#') T=NULL; //如果ch='#',则T为空指针 else{ if(!(T=(BiThrTree)malloc(sizeof(BiThrNode)))) return FALSE; T->data=ch; T->LTag=Link; T->RTag=Link; //线索标志赋初值0 CreateBiTree(T->lchild);//先序建立T->lchild; CreateBiTree(T->rchild);//先序建立T->rchild; } return T; //返回树结点头指针 } //遍历二叉树(递归算法) void PreOrderTraverse(BiThrTree T) {//先序遍历 if (T){ cout<<" "<data; /*访问根结点*/ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void InOrderTraverse(BiThrTree T) {//中序遍历 if (T){ InOrderTraverse(T->lchild); cout<<" "<data; /*访问根结点*/ InOrderTraverse(T->rchild); } } 10 void PosOrderTraverse(BiThrTree T) {//后序遍历 if (T) { PosOrderTraverse(T->lchild); PosOrderTraverse(T->rchild); cout<<" "<data; /*访问根结点*/ } } //栈的相关操作 typedef struct { BiThrTree *base; BiThrTree *top; int stacksize; }SqStack; Status StackEmpty(SqStack S) { if(S.base==S.top) return OK; else return FALSE; } Status InitStack(SqStack &S) { S.base=(BiThrTree*)malloc(STACK_INIT_SIZE*sizeof(BiThrNode)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } BiThrTree GetTop(SqStack S,BiThrTree &e) { //若栈不为空，则用e返回S的栈顶元素，并返回OK;否则返回FALSE if(S.top==S.base) return FALSE; e=*(S.top-1); return e; } 11 Status Push(SqStack &S,BiThrTree e) { //入栈 if(S.top-S.base>=S.stacksize) { S.base=(BiThrTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiThrNod e)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status Pop(SqStack &S,BiThrTree &e) { //出栈 if(S.top==S.base) return FALSE; e=*--S.top; return OK; } //遍历二叉树(非递归算法) void PreOrder_2_Traverse(BiThrTree T) {//先序非递归遍历 SqStack S; InitStack(S); BiThrTree p = T; while( p || !StackEmpty(S)) { if(p) { cout<<" "<data; Push(S,p); p = p->lchild; } else{ Pop(S,p); p = p->rchild; } } 12 } void InOrder_2_Traverse(BiThrTree T) {//中序非递归遍历 SqStack S; InitStack(S); BiThrTree p = T; while( p || !StackEmpty(S)){ if(p){ Push(S, p); p = p->lchild; } else{ Pop(S, p); cout<<" "<data; p = p->rchild; } } } //线索化二叉树 BiThrTree pre; //全局变量,刚刚访问过的结点 Status PreOrderThreading(BiThrTree &Thrt, BiThrTree T) { //先序线索化二叉树 Thrt = (BiThrTree)malloc(sizeof(BiThrNode)); //创建头结点 Thrt->LTag=Link; Thrt->RTag=Thread; Thrt->rchild=Thrt; if (!T) Thrt->lchild=Thrt; //空二叉树,左指针回指 else { Thrt->lchild = T; pre = Thrt; //pre: 刚刚访问过的结点; PreThreading(T); pre->rchild=Thrt; 13 pre->RTag=Thread; Thrt->rchild=pre; } return OK; } void PreThreading(BiThrTree p) { if (p) { if (!p->lchild) { //先驱线索 p->lchild=pre; p->LTag=Thread; } if (!pre->rchild) { //后继线索 pre->rchild=p; pre->RTag=Thread; } pre = p; if(p->LTag==Link) PreThreading(p->lchild); //左子树线索化 if(p->RTag ==Link) PreThreading(p->rchild); //右子树线索化 } } // Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) {//中序线索化二叉树 Thrt = (BiThrTree)malloc(sizeof(BiThrNode)); //创建头结点 Thrt->LTag=Link; Thrt->RTag=Thread; Thrt->rchild=Thrt; if (!T) Thrt->lchild=Thrt; //空二叉树，左指针回指 else { Thrt->lchild = T; pre = Thrt; //pre: 刚刚访问过的结点; InThreading(T); 14 pre->rchild=Thrt; pre->RTag=Thread; Thrt->rchild=pre; } return OK; } void InThreading(BiThrTree p) { if (p) { InThreading(p->lchild); //左子树线索化 if (!p->lchild) { //前驱线索 p->LTag=Thread; p->lchild=pre; } if (!pre->rchild) { //后继线索 pre->RTag=Thread; pre->rchild=p; } pre = p; //保持pre指向p的前驱 InThreading(p->rchild); //右子树线索化 } } // //遍历线索化二叉树 void PreOrderTraverse_Thr(BiThrTree Thrt)//Thrt:头结点 {//遍历先序线索化二叉树 BiThrTree p; p=Thrt->lchild; while(p!=Thrt){ cout<<" "<data; while(p->LTag == Link) { p=p->lchild; cout<<" "<data; } while((p->RTag==Thread)&&(p->rchild!=Thrt))//??????????? { p = p->rchild; 15 cout<<" "<data; } if(p->LTag==Link)p = p->lchild; else p=p->rchild; } }// void InOrderTraverse_Thr(BiThrTree Thrt)//Thrt:头结点 {//遍历中序线索化二叉树 BiThrTree p; p=Thrt->lchild; while(p!=Thrt) { while(p->LTag == Link) { p=p->lchild; }cout<<" "<data; while((p->RTag==Thread)&&(p->rchild!=Thrt)){ p = p->rchild; cout<<" "<data; } p = p->rchild; } }// //将线索化后二叉树还原 void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T) { BiThrTree p,post; p=Thrt->lchild; while(p!=Thrt){ while(p->LTag == Link) p=p->lchild; p->LTag=Link; p->lchild=NULL; while((p->RTag==Thread)&&(p->rchild!=Thrt)){ p->RTag=Link; post=p->rchild; 16 p->rchild=NULL; p=post; } p = p->rchild; } p=Thrt->rchild; p->RTag=Link; p->rchild=NULL; T=Thrt->lchild; free(Thrt); } void main() { BiThrTree T,Thrt; //定义树 cout<<"按照<先序>顺序输入您要建立的二叉树(空孩子用'#' 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示)\n"; CreateBiTree(T); //先序算法建立二叉树 cout<<"\n"; cout<<"递归遍历\n"; cout<<"1:<先序> 递归遍历结果:\n"; PreOrderTraverse(T); cout<<"\n"; cout<<"2:<中序> 递归遍历结果:\n"; InOrderTraverse(T); cout<<"\n"; cout<<"3:<后序> 递归遍历结果:\n"; PosOrderTraverse(T); cout<<"\n"; cout<<"\n\n\n"; cout<<"非递归遍历\n"; cout<<"1:<先序> 非递归遍历结果:\n"; PreOrder_2_Traverse(T); cout<<"\n"; cout<<"2:<中序> 非递归遍历结果:\n"; InOrder_2_Traverse(T); cout<<"\n"; 17 cout<<"\n\n\n"; cout<<"线索化二叉树\n"; InOrderThreading(Thrt,T);//中序线索化 cout<<"1:<中序> 线索化后的内容:\n"; InOrderTraverse_Thr(Thrt); //遍历中序线索化二叉树 cout<<"\n"; InOrder_Thr_T(Thrt,T);//还原 PreOrderThreading(Thrt,T);//先序线索化 cout<<"2:<先序> 线索化后的内容:\n"; PreOrderTraverse_Thr(Thrt);//遍历先序线索化二叉树 cout<<"\n\n\n\n"; InOrder_Thr_T(Thrt,T);//还原 } 18 6 程序调试与测试 在程序调试准确的情况下会出现运行框显示“按照<先序>顺序输入您要建立的二叉树 (空孩子用#表示)”的提示语，当准确输入二叉树后结果中包括递归遍历的先序、中序、 后序遍历，非递归的先序和中序以及线索化遍历的先序和中序遍历。 如:输入ABC##DE###F#G##表示输入了一如下所示二叉树 A BF CDG E 则理论输出结果应为: 先序遍历:ABCDEFG 中序遍历:CBEDAFG 后序遍历:CEDBGFA 先序线索化后内容为:ABCDEFG 中序线索化后内容为:CBEDAFG 19 7 结果分析 程序最后将输出包括递归、非递归前序、中序、后序遍历以及先序和中序的线索化结果，则以上图: A BF CDG E 的程序最后输出结果为: 输入二叉树(按照先序遍历) 输出遍历结果(先序、中序、后序) 算法在执行中多次调用进出栈操作，虽然减少了时间的复杂度，提高了程序的运行速度，但却在空间上增大了空间复杂度，需占用更多内存一次存储访问过的数据。 20 8 总结 本课题实现了对二叉树的先序、中序、后序遍历和线索化过程，但在设计过程中由于要对同一个二叉树同时实现先序、中序和后序线索化则应该在其一次线索化后还原并重新进行线索化并输出，还原过程较线索化过程复杂，由于对语言的掌握程度不深故未能实现先序线索化的还原过程，只完成了对中序线索化的还原，在最终未能实现后序的线索化及线索化后遍历输出过程。因此程序存在严重的漏洞，以后我会在语言的熟练程度上加强，提高语言的驾驭能力，最终能够熟练掌握语言的各种的操作。 21 参考文献 [1] 严蔚敏，吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2002 [2] 李春葆.数据结构(C语言版)习题与解析[M]. 北京:清华大学出版社,2002 [3] 钱能.C++程序设计教程[M]. 北京:清华大学出版社,2003 22 1