数据结构课程设计二叉树的遍历报告11

《数据结构课程设计二叉树的遍历报告11》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告姓名班级学号指导老师一、课程设计目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计要求1)学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。2)学生要发挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时

2、向教师汇报。3)课程设计按照教学计划需要一周时间完成，一周中每天至少要上两小时的上机来调试C或C++语言设计的程序，总共至少要上机调试程序10小时。属教师安排上机时间学生不得缺席。三、课程设计内容二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。四、课程设计原理1.设计思想以广义表格式输入一个二叉树，将其接收至一维数组中，利用栈结构建立二叉链表树；通过先、中、后访问根结点递归算法遍历二叉树；利用栈结构依次将结点入栈、出栈实现二叉树的非递归遍历算法；利用队列的入队、出队操作实现二叉树的层次遍历。例如：a(c(,d)，f(g,))建立如

3、下图所示二叉树。cadfg2.数据结构typedefBTREENODEPTRelemtype;1)队列数据类型定义typedefstruct{elemtype*elem;intfront,rear;intsize;}SqQueue;2)栈数据类型定义typedefstructstack_tag{elemtype*elem;inttop;intsize;}SQSTACK;3)二叉树数据类型定义typedefstructbtreenode{chardata;structbtreenode*lchild,*rchild;}BTREENODE,*BTREENODEPTR,*BTREE;

4、2.主要模块设计BTREECreateBtree1(char*str)；//创建二叉树voidPreOrder(BTREEroot)；//先序递归遍历二叉树voidInOrder(BTREEroot)；//中序递归遍历二叉树voidPostOrder(BTREEroot)；//后序递归遍历二叉树voidPreOrder_1(BTREEroot)；//先序非递归遍历二叉树voidInOrder_1(BTREEroot)；//中序非递归遍历二叉树voidPostOrder_1(BTREEroot)；//后序非递归遍历二叉树voidLayerOrder(BTREEroot)；//层次

5、遍历其他模块包括栈的初始化及其基本操作和队列的初始化及基本操作。主菜单先序递归遍历中序递归遍历后序递归遍历先序非递归遍历中序非递归遍历后序非递归遍历层次遍历结束将以广义表形式输入的二叉树接收到数组str[80]中，成功建立二叉树1.详细设计1)二叉树的建立其中mark的值1、2、3、4分别指str[i]为字母、‘(’、‘，’、‘)’；tag为左、右孩子的标志；root=null检查str[1~’’]‘(’‘)’‘，’‘mark=1；root->data=str[0],root->lchild=root->rchild=null;p=root;str[0]是否为字母YNNma

6、rk==2?mark=2str[i]入栈tag=0mark==3?mark=3tag=1Nmark=4pop为空returnnullNYY‘)’‘mark==1&&栈不空新建结点pp->data=str[i]p->lchild=p->rchild=nulltag==0?'循环结束后returnroot栈顶->rchild=p栈顶->lchild=pYN以先序遍历的顺序创建二叉树的各个结点，流程图如图4-3所示。将二叉树的各结点以字符串数组的形式存放在ch中，首先判断数组的第一个元素是否为空，如果为空则结二叉树的遍历结果返回空，反之遍历下一个结点。下一个结点不为零，则其为致左子树

7、，否则致为右子树，依次循环直到最终输出为回车键，循环结束。1)二叉树的递归遍历(以先序遍历为例)结点为空N访问根节点先序遍历方式遍历左子树先序遍历方式遍历右子树结束Y开始2)二叉树的非递归遍历(以先序遍历为例)初始化队列，root入队栈非空出栈p；打印p->dataYp->lchild!=nullYp->lchild入栈p->lchild!=nullNYNp->rchild入栈结束N1)二叉树的层次遍历访问元素所指结点，若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子