数据结构课程设计之二叉树的遍历

《数据结构》课程设计报告题目学生姓名学号专业班级指导老师设计日期指导老师评阅意见：评阅成绩：签名：目录问题定义······································3可行性分析···································3-4调试界面·····································4-7错误分析······································7总结·········································7-8附录········································8-14一、问题定义1.1课题：建立二叉树，层序、先序、中序、后序遍历（用递归或非递归的方法）以及中序线索化。1.2意义：通过以前的学习以及查看相关资料，按照题目要求编写程序，进一步加强对编程的训练，使得自己掌握一些将书本知识转化为实际应用当中去，在整个程序中，主要应用的是链表，但也运用了栈。通过两种方法解决现有问题。1.3要求：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；实现二叉树的中序线索化。二、可行性分析2.1创建二叉树链表的结点存储结构及数据的输入函数因为每个结点所存储的数据类型为字符串，却无法使用字符串和String等数据类型，所以使用单链表作为结点所存储的数据类型。以#表示空结点。利用先序遍历创建链表2.1.1用单链表s记录输入的数据2.1.2利用非递归调用分别生成根节点的左子树和右子树。2.1.3返回菜单重新选择。基本程序如下：voidCreatBiTree_q(BiTree&T)/{······if(ch=='#')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(0);T-data=ch;T-LTag=Link;T-RTag=Link;CreatBiTree_q(T-lchild);CreatBiTree_q(T-rchild);}}2.2先序遍历、中序遍历、后序遍历二叉链表。A、先序遍历：访问根节点，左子树，右子树的顺序。B、中序遍历：访问左子树，根节点，右子树的顺序。C、后序遍历：访问左子树，右子树，根节点的顺序。D、层次遍历：从根结点开始，按从左至右的顺序依次访问。E、中序线索化：将二叉树线索化，再进行中序遍历输出。2.3主函数a、调用生成二叉树的函数，从键盘输入二叉树的各个结点b、分别调用先序遍历、中序遍历、后序遍历二叉树的函数，输出所有结点显示的菜单为：***********************************************请选择遍历算法1.按先序输入二叉树序列以#表示空节点2.先序遍历二叉树递非归算法3.中序遍历二叉树非递归算法4.后序遍历二叉树非递归算法5.层次遍历二叉树非递归算法6.中序线索遍历二叉树算法0.按0退出endl请输入序号（0，1,2,3,4,5,6）：三、调试界面：3.1调试所用二叉树：ABCDEFG输入的二叉树是：ABC##DE#F##G###（#代表空结点）输出的遍历应该是：先序遍历：ABCDEFG中序遍历：CBEFDGA后序遍历：CBGEFDA层序遍历：ABCDEFG中序线索化遍历：CBEFDGA3.2程序运行如下：1、菜单界面：2、创建界面：3、先序非遍历二叉树：4、中序非遍历二叉树：5、后序非遍历二叉树：6、层次遍历二叉树：7、中序线索化，中序遍历：四、错误分析：1、中序线索化后，先序、中序、后序、层次遍历均出现错误，陷入死循环，改正：另外编写一个创建二叉树的函数，中序线索化另外重新创建，中序输出函数也另外编写2、中序线索化时，用到的线索在结构体内定义，在线索化时，显示为未定义改正：直接在外部定义线索#defineLink0和#defineThread1五、总结实验开始时定义结构时，比细心，总会有或多或少的问题出现，如数据域和指针域定义的类型不一样，在实验过程中总有这样或那样的问题，在本次实验中，二叉树的先序，中序，后序遍历都是采用非递归调用，用起来稍微复杂，这使我更进一步学习和理解了树的遍历，更灵活地运用了指针与数组。六、附录6.1源程序#includeiostream.h#includestdio.h#includestdlib.h#includemalloc.h#defineLink0#defineThread1intright=0;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;intLTag,RTag,flag;}BiTNode,*BiTree;BiTreepre;voidCreatBiTree_q(BiTree&T){TElemTypech;scanf(%c,&ch);if(ch=='#')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(0);T-data=ch;T-LTag=Link;T-RTag=Link;CreatBiTree_q(T-lchild);CreatBiTree_q(T-rchild);}}voidCreateBiTree(BiTree*T){TElemTypech;scanf(%c,&ch);if(ch=='#')*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(-1);(*T)-data=ch;CreateBiTree(&(*T)-lchild);CreateBiTree(&(*T)-rchild);}}voidPreOrderTraverse(BiTree&T){BiTreep,S[20];inttop=-1;p=T;do{while(p!=NULL){coutp-data;top++;S[top]=p;p=p-lchild;}if(top-1){p=S[top];top--;p=p-rchild;}}while((p!=NULL)||(top-1));}intinorderTraverse(BiTree&T){BiTreep,s[20];inti=-1;p=T;while(p||i-1){if(p){i++;s[i]=p;p=p-lchild;}else{p=s[i];cout;coutp-data;i--;p=p-rchild;}}return0;}voidpostorder(BiTreeT){ints2[20],top=0;BiTreep,s1[20];p=T;do{while(p!=NULL){s1[top]=p;s2[top++]=0;p=p-lchild;}while(top&&s2[top-1]==1){top--;p=s1[top];cout;coutp-data;}if(top0){s2[top-1]=1;p=s1[top-1]-rchild;}}while(top0);}voidLevelOrder(BiTree&b){BiTreequ[20];intfront,rear;front=rear=-1;rear++;qu[rear]=b;while(front!=rear){front=(front+1)%20;b=qu[front];printf(%c,b-data);if(b-lchild!=NULL){rear=(rear+1)%20;qu[rear]=b-lchild;}if(b-rchild!=NULL){rear=(rear+1)%20;qu[rear]=b-rchild;}}}voidInThreading(BiTreep){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;InThreading(p-rchild);}}voidInOrderThreading(BiTree*Thrt,BiTreeT){if(!((*Thrt)=(BiTree)malloc(sizeof(BiTNode))))exit(0);(*Thrt)-LTag=Link;(*Thrt)-RTag=Thread;(*Thrt)-rchild=(*Thrt);if(!T)(*Thrt)-lchild=(*Thrt);else{(*Thrt)-lchild=T;pre=(*Thrt);InThreading(T);pre-rchild=(*Thrt);pre-RTag=Thread;(*Thrt)-rchild=pre;}}voidInorderTraverse_Thr(BiTree&T){BiTreep;p=T-lchild;while(p!=T)p=T{while(p-LTag==Link)p=p-lchild;coutp-data;while(p-RTag==Thread&&p-rchild!=T){p=p-rchild;cout;coutp-data;}p=p-rchild;}}intmain(){BiTreeT,t;inte;while(e!=0){coutendl请选择遍历算法：endl;cout1.按先序输入二叉树序列以#表示空节点endl;cout2.先序遍历二叉树递归算法：endl;cout3.中序遍历二叉树递归算法：endl;cout4.后序遍历二叉树递归算法：endl;cout5.层次遍历二叉树递归算法endl;cout6.中序线索遍历二叉树算法endl;cout0.按0退出endl;cout请输入序号（0，1,2,3,4,5,6）：endl;cine;coutendl;if(e==1){cout按先序输入二叉树序列以#表示空节点：endl;CreateBiTree(&T);coutendl;}if(e==2){cout先序遍历递归算法是：endl;;PreOrderTraverse(T);coutendl;}if(e==3){cout中序遍历递归算法是：endl;;inorderTraverse(T);coutendl;}if(e==4){cout后序遍历的非递归算法是：endl;postorder(T);coutendl;}if(e==5){printf(\n层次遍历二叉树:\n);LevelOrder(T);}if(e==6){cout按先序输入二叉树序列以#表示空节点：endl;CreatBiTree_q(T);coutendl;printf(中序线索化二叉树:\n);InOrderThreading(&t,T);printf(线索化工作已经完成!中序遍历二叉树\n);InorderTraverse_Thr(t);printf(\n);}}return0;}6.2参考资料【1】严蔚敏、吴伟民主编《数据结构》（C语言版）清华大学出版社2002【2】殷人昆等著《数据结构》（C++版）清华大学出版社2001【3】金远平著《数据结构》（C++描述）清华大学出版社2005【4】许卓群等著《数据结构与算法》高等教育出版社2004【5】FrankM.Carrano等著《数据结构与