数据结构课程设计二叉树的遍历报告.pdf
数据结构课程设计报告 姓 名 班 级 欢迎下载 2 学 号 指导老师 一、课程设计目的 培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计要求 1)学生必须仔细阅读数据结构课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。2)学生要发挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。3)课程设计按照教学计划需要一周时间完成，一周中每天至少要上两小时的上机来调试 C 或 C+语言设计的程序，总共至少要上机调试程序 10 小时。属教师安排上机时间学生不得缺席。三、课程设计内容 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。四、课程设计原理 欢迎下载 3 1.设计思想 以广义表格式输入一个二叉树，将其接收至一维数组中，利用栈结构建立二叉链表树；通过先、中、后访问根结点递归算法遍历二叉树；利用栈结构依次将结点入栈、出栈实现二叉树的非递归遍历算法；利用队列的入队、出队操作实现二叉树的层次遍历。例如：a(c(,d)，f(g,)建立如下图所示二叉树。2.数据结构 typedef BTREENODEPTR elemtype;1)队列数据类型定义 typedef struct elemtype*elem;int front,rear;int size;SqQueue;2)栈数据类型定义 typedef struct stack_tag elemtype*elem;int top;int size;SQSTACK;3)二叉树数据类型定义 typedef struct btreenode char data;struct btreenode*lchild,*rchild;BTREENODE,*BTREENODEPTR,*BTREE;3.主要模块设计 BTREE CreateBtree1(char*str)；/创建二叉树 void PreOrder(BTREE root)；/先序递归遍历二叉树 void InOrder(BTREE root)；/中序递归遍历二叉树 c a d f g 欢迎下载 4 void PostOrder(BTREE root)；/后序递归遍历二叉树 void PreOrder_1(BTREE root)；/先序非递归遍历二叉树 void InOrder_1(BTREE root)；/中序非递归遍历二叉树 void PostOrder_1(BTREE root)；/后序非递归遍历二叉树 void LayerOrder(BTREE root)；/层次遍历 其他模块包括栈的初始化及其基本操作和队列的初始化及基本操作。4.详细设计 1)二叉树的建立 其中mark的值 1、2、3、4 分别指 stri为字母、(、，、)；tag为左、右孩子的标志；主菜单 先序递归遍历 中序递归遍历 后序递归遍历 先序非递归遍历 中序非递归遍历 后序非递归遍历 层次遍历 结束 将以广义表形式输入的二叉树接收到数组 str80中，成功建立二叉树 欢迎下载 5 2)二叉树的递归遍历(以先序遍历为例)root=null 检查 str10()，mark=1；root-data=str0,root-lchild=root-rchild=null;p=root;str0是否为字母 Y N N mark=2mark=2 stri入栈 tag=0 mark=3mark=3 tag=1 N mark=4 pop 为空 return null N Y Y)mark=1&栈不空 新建结点 p p-data=stri p-lchild=p-rchild=null tag=0?循环结束后return root 栈顶-rchild=p 栈顶-lchild=p Y N 欢迎下载 6 3)二叉树的非递归遍历(以先序遍历为例)4)二叉树的层次遍历 访问元素所指结点，若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。初始化队列，root 入队 栈非空 出栈p；打印p-data Y p-lchild!=null Y p-lchild入栈 p-lchild!=null N Y N p-rchild入栈 结束 N 结点为空 N 访问根节点 先序遍历方式遍历左子树 先序遍历方式遍历右子树 结束 Y 开始 欢迎下载 7 五、运行结果 1.建立二叉树 2.先序遍历 初始化队列，root 入队 队列非空 出队p；打印p-data Y p-lchild!=null Y p-lchild入队 p-lchild!=null N Y N p-rchild 入结束 N 欢迎下载 8 3.中序遍历 4.后序遍历 5.层次遍历 6.退出程序 欢迎下载 9 7.出错信息 六、设计总结 二叉树是数据结构的的基本内容。虽然程序规模不大，我依然付出了努力，仍免不了各种错误的出现。编程过程需要很大的毅力和耐心，而且要有良好的思维和扎实的专业基础知识，所以我需要不断的学习，发现自身不足之处并改正它，逐步提高自己。
