数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_二叉树的遍历_课程设计_实验报告
设计题目：二叉树的遍历
1
课题名称二叉树的遍历院系年级专业学号姓名成绩
课题设计目的与设计意义1.课题设计目的：培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2.课题设计意义：。锻炼我们的编码能力，真正的理解数据结构的编码思想，并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。指导教师：
年月日
目录第一章课程与设计的目的与意义..............................................................................11.1课题设计目的：..............................................................................................11.2课题设计意义：..............................................................................................1第二章可行性分析......................................................................................................12.1创建二叉树链表的结点存储结构及数据的输入函数.................................12.1.1用单链表s记录输入的数据...............................................................12.1.2利用非递归调用分别生成根节点的左子树和右子树。...................12.1.3返回菜单重新选择。...........................................................................12.2先序遍历、中序遍历、后序遍历二叉链表。..............................................22.3主函数..............................................................................................................2第三章、调试界面：....................................................................................................23.1调试所用二叉树：..........................................................................................23.2程序运行如下：..............................................................................................3
第四章、错误分析：....................................................................................................5第五章、总结................................................................................................................5第六章、附录..............................................................................................................66.1源程序..............................................................................................................66.2参考资料.......................................................................................................12
1
第一章课程与设计的目的与意义1.1课题设计目的：培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1.2课题设计意义：学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并
在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。课程设计按照教学计划需要一周时间完成，一周中每天至少要上两小时的上机来调试C或C++语言设计的程序，总共至少要上机调试程序10小时。属教师安排上机时间学生不得缺席。第二章可行性分析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;
2
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退出"<
第三章、调试界面：3.1调试所用二叉树：ABCDEF
G输入的二叉树是：ABC##DE#F##G###（#代表空结点）
3
输出的遍历应该是：先序遍历：ABCDEFG中序遍历：CBEFDGA后序遍历：CBGEFDA层序遍历：ABCDEFG中序线索化遍历：CBEFDGA3.2程序运行如下：
：图1菜单界面图2创建界面
3、先序非遍历二叉树：
4
4、中序非遍历二叉树：
5、后序非遍历二叉树：
6、层次遍历二叉树：
5
7、中序线索化，中序遍历：第四章、错误分析1、中序线索化后，先序、中序、后序、层次遍历均出现错误，陷入死循环，改正：另外编写一个创建二叉树的函数，中序线索化另外重新创建，中序输出函数也另外编写2、中序线索化时，用到的线索在结构体内定义，在线索化时，显示为未定义改正：直接在外部定义线索#defineLink0和#defineThread1第五章、总结
实验开始时定义结构时，比细心，总会有或多或少的问题出现，如数据域和指针域定义的类型不一样，在实验过程中总有这样或那样的问题，在本次实验中，二叉树的先序，中序，后序遍历都是采用非递归调用，用起来稍微复杂，这使我更进一步学习和理解了树的遍历，更灵活地运用了指针与数组。第六章、附录6.1源程序#include#include#include#include#defineLink0#defineThread1
6
intright=0;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNodelchild,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(BiTreeT){TElemTypech;scanf("%c",&ch);if(ch==''#'')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));
if(!T)exit(-1);(T)->data=ch;
7
CreateBiTree(&(T)->lchild);CreateBiTree(&(T)->rchild);}}voidPreOrderTraverse(BiTree&T){BiTreep,S[20];inttop=-1;p=T;do{while(p!=NULL)
{cout<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<<"";
8
cout<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<<"";cout<data;}if(top>0){s2[top-1]=1;p=s1[top-1]->rchild;
}}while(top>0);}voidLevelOrder(BiTree&b){BiTreequ[20];intfront,rear;front=rear=-1;rear++;qu[rear]=b;while(front!=rear)
{front=(front+1)%20;
9
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(BiTreeThrt,BiTreeT){if(!((Thrt)=(BiTree)malloc(sizeof(BiTNode))))exit(0);(Thrt)->LTag=Link;(Thrt)->RTag=Thread;(Thrt)->rchild=(Thrt);if(!T)(Thrt)->lchild=(Thrt);
else
10
{(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;cout<data;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;cout<<"";cout<data;}p=p->rchild;}}intmain()
{BiTreeT,t;inte;while(e!=0){cout<
cin>>e;cout<
11
if(e==1){cout<<"按先序输入二叉树序列以#表示空节点："<
cout<<"中序遍历递归算法是："<
LevelOrder(T);}if(e==6){cout<<"按先序输入二叉树序列以#表示空节点："<
return0;}
12
6.2参考资料[1]严蔚敏、吴伟民.数据结构（C语言版）.清华大学出版社.2002[2]殷人昆等著.数据结构》（C++版）.清华大学出版社.2001[3]金远平.数据结构》（C++描述）.清华大学出版社2005[4]许卓群.数据结构与算法.高等教育出版社.2004[5]FrankM.Carrano.数据结构与Ｃ++高级教程清华大学出版社.2004[6]严蔚敏、吴伟民.数据结构习题集（C语言版）.清华大学出版社.2002
|
|
