数据结构课设二叉树的遍历.doc

数据结构 课程设计说明书 题目： 二叉树的遍历 学生姓名： 学 号： 院 （系）： 专 业： 指导教师： 年 月日  目 录 TOC \o 1-3 \h \u HYPERLINK \l _Toc376259993 1 需求分析 PAGEREF _Toc376259993 \h 1 HYPERLINK \l _Toc376259994 2 概要设计 PAGEREF _Toc376259994 \h 1 HYPERLINK \l _Toc376259995 2.1 功能设计 PAGEREF _Toc376259995 \h 1 HYPERLINK \l _Toc376259996 2.2 算法流程图 PAGEREF _Toc376259996 \h 2 HYPERLINK \l _Toc376259997 3 详细设计 2 HYPERLINK \l _Toc376259998 3.1 创建二叉树 2 HYPERLINK \l _Toc376259999 3.2 二叉树的递归遍历算法 PAGEREF _Toc376259999 \h 3 HYPERLINK \l _Toc376260000 3.3 二叉树的层次遍历算法 PAGEREF _Toc376260000 \h 3 HYPERLINK \l _Toc376260001 3.4 二叉树的非递归遍历算法 PAGEREF _Toc376260001 \h 3 HYPERLINK \l _Toc376260002 4 测试数据与分析 3 HYPERLINK \l _Toc376260003 5 算法分析 9 HYPERLINK \l _Toc376260004 6 总结 9 HYPERLINK \l _Toc376260005 参 考 文 献 PAGEREF _Toc376260005 \h 10 HYPERLINK \l _Toc376260006 附录 PAGEREF _Toc376260006 \h 11 二叉树的遍历 数据结构课程设计 PAGE 10 PAGE 15 1 需求分析 数据结构是信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。数据结构研究四个方面的问题： （1）数据的逻辑结构，即数据之间的逻辑关系； （2）数据的物理结构，即数据在计算机内的存储方式； （3）对数据的加工，即基于某种存储方式的操作算法； （4）算法的分析；即评价算法的优劣。 本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。 根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。 （1）创建二叉树：按先序次序输入，构造二叉链表表示的二叉树。 （2）设计算法：先序遍历,中序遍历,后序遍历。 （3）编写程序：设计main()函数调用以上步骤实现相关功能。 本程序用Microsoft Visual Studio 2008编写，可以实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。 2 概要设计 2.1 功能设计 （1）typedef struct BTNode—定义二叉树 定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。 （2）CreateBiTree(BiTree T)—构建二叉树 此函数的功能是构建二叉树。从键盘上按先序次序输入字符构造二叉链表表示的二叉树T，其中用星号表示空树 。 NRPreOrder(BiTree bt)—先序遍历（非递归） 此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。 （4）NRInOrder(BiTree bt)—中序遍历（非递归） 此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。 （5）NRPostOrder(BiTree bt)—后序遍历（非递归） 此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根