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

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

图 1 算法流程图
3、详细设计
详细代码设计
(1)构造二叉数
若ch='(':则将前面刚创建的结点作为双亲结点进栈,并置k=1,表示其后创建的结点将作为这个结点的左孩子结点;
若ch=')':表示栈中结点的左右孩子结点处理完毕,退栈;
若ch=',':表示其后创建的结点为右孩子结点;
BSTNode* CreateBSTNode(char *s)
{ char ch;BSTNode *p=NULL,*b=NULL,*ps[MaxSize];
int top=-1,tag=-1;ch=*s;
while(ch){
switch(ch){
case '(':ps[++top]=p;tag=1;break;
case ',':tag=2;break;
case ')':top--;break;
default:
p=(BSTNode*)malloc(sizeof(BSTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL) b=p;
else{switch(tag){
case 1:ps[top]->lchild=p;break;
case 2: