二叉树的遍历《数据结构》课程设计论文.doc

I 数据结构课程设计题目二叉树的遍历学号: ___ 姓名: ___ 指导教师: ___ 成绩: _______________ 完成时间: _2011 年_12月 II 目录 1 、需求分析............................................................................................... 1 2 、概要设计............................................................................................... 2 功能设计....................................................................................... 2 算法流程图................................................................................... 3 3 、详细设计............................................................................................... 4 界面设计....................................................................................... 4 详细代码分析............................................................................... 5 调试分析..................................................................................... 11 调试结果............................................................................ 14 算法分析............................................................................ 14 4 、总结..................................................................................................... 14 参考文献................................................................................................... 15 1 1 、需求分析数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业基础课程,掌握好数据结构的知识将直接关系到后续专业课程的学****数据结构只要研究四个方面的问题:(1) 数据的逻辑结构,即数据之间的逻辑关系;(2) 数据的物理结构,即数据在计算机内的存储方式; (3) 对数据的加工,即基于某种存储方式的操作算法; (4) 算法的分析;即评价算法的优劣。本实验是用链式存储结构来存储二叉树并进行一系列的算法,且结点内容的数据类型为字符型。本程序用 VC++ 编写,可以实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法,先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。根据题目知,程序主要是根据给定二叉树的先序遍历结果,构造出二叉树并输出按中,后序遍历的结果,以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。(1) 先创建二叉树:构建一个字符二叉树实例,并横向打印该二叉树。(2) 设计算法:用递归算法和非递归算法中序遍历和后序遍历这个二叉树。(3) 加入求二叉树的深度和二叉树的叶子数二叉树的结点总数等一些简单的算法。(4) 设计 main() 函数调用以上步骤实现相关功能。 2 2 、概要设计 功能设计(1)CreateBSTNode(char *s) 此函数的功能是构建一个二叉树。(2)DispBTree(BSTNode *b) 此函数的功能是打印该二叉树。(3)BSTNodeDepth(*b) 此函数的功能是求该二叉树高度。(4)DispLeaf(B STNode *b) 此函数的功能是在屏幕上输出该二叉树的叶子结点。(5)InOr