《数据结构》课程设计 报告样本 001

数据结构课程设计

《数据结构》课程设计报告

设计题目： 二叉树的遍历 姓 名： 陈 诗 雨 学 号： 2008k230103 专 业： 软件工程 班 级： KT923-1 指导教师： 马春江

2011年 1月 10日

0

数据结构课程设计

目 录

一、问题描述 ............................................................................................................... 2

问题描述：创建二叉树并遍历 ............................................................................................... 2 基本要求： ............................................................................................................................... 2

二、需求分析 ............................................................................................................... 2 三、概要设计 ............................................................................................................... 2

1．创建二叉树 ......................................................................................................................... 2 2．二叉树的非递归前序遍历示意图 ..................................................................................... 2 3．二叉树的后序非递归遍历示意图 ..................................................................................... 3

四、数据结构设计 ....................................................................................................... 3

1． 2．

二叉树结点数据类型定义为： ................................................................................... 3 二叉树数据类型定义为： ........................................................................................... 3

五、算法设计 ............................................................................................................... 4

1、创建二叉树 ......................................................................................................................... 4 2、非递归前序遍历 ................................................................................................................. 5 3、非递归后序遍历 ................................................................................................................. 5 4、求二叉树的高度 ................................................................................................................. 6 5、 求二叉树每一层的结点数 ........................................................................................... 7 6、求两节点最近共同祖先 ..................................................................................................... 7 6、算法流程图 ......................................................................................................................... 8

六、程序测试与实现 ................................................................................................... 9

1、函数之间的调用关系 ......................................................................................................... 9 2、主程序 ................................................................................................................................. 9 3、测试数据 ........................................................................................................................... 11 4、测试结果 ........................................................................................................................... 11

七、调试分析 ............................................................................................................. 12 八、遇到的问题及解决办法 ..................................................................................... 13 九、心得体会 ............................................................................................................. 13

1

数据结构课程设计

一、问题描述

问题描述：创建二叉树并遍历 基本要求：

1、 分别运用非递归的方式完成对二叉树的先序和后序遍历 2、 输出二叉树的高度 3、 输出每一层的结点数

4、 查找结点P 和结点Q的最近共同祖先

二、需求分析

1． 本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉

树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。 2． 程序运行后显现提示信息，等候用户输入0—6以进入相应的操作功能。 3． 用户输入数据完毕，程序将输出运行结果。 4． 测试数据应为字符型数据。

三、概要设计

1．创建二叉树

输入数据不低于15个，用递归方法建立二叉树。

2．二叉树的非递归前序遍历示意图

图3.2二叉树前序遍历示意图

2

数据结构课程设计

3．二叉树的后序非递归遍历示意图

图3.4二叉树后序遍历示意图

四、数据结构设计

1． 二叉树结点数据类型定义为：

template struct BiNode {

BiNode *rchild,*lchild;//指向左右孩子的指针 T data; //结点数据信息 };

2． 二叉树数据类型定义为：

template class BiTree {

template

friend ostream & operator <<(ostream &os ,BiTree &bt); public:

BiTree();//无参构造函数

BiTree(int m){};//有参空构造函数

BiTree(T ary[],int num,T none);//有参构造函数 ~BiTree();//析构函数

void preorder();//递归前序遍历 void inorder();//递归中序遍历 void postorder();//递归后续遍历 void levelorder();//层序遍历

int count();//计算二叉树的结点数 int depth();//计算二叉树的深度

3

数据结构课程设计

void display(ostream &os);//打印二叉树，有层次 void LevelNum();//计算每一层结点数 void PreOrder();//非递归前序遍历 void PostOrder();//非递归后序遍历 void creat();//创建二叉树

T leastCommanAncestor(T va, T vb);//求树中任意两结点最近共同祖先 protected:

//以下函数供上面函数调用 //对应相同功能

void creat(BiNode * &root);//创建 void release(BiNode* &root);//删除

BiNode * Build(T ary[],int num,T none,int idx);//用数组创建二叉树 void PreOrder(BiNode* root);//前序遍历 void PostOrder(BiNode* root);//后续遍历 void LevelNum(BiNode* root);//层序遍历 void preorder(BiNode* root);//递归前序遍历 void inorder(BiNode* root);//递归中序遍历 void postorder(BiNode* root);//递归后续遍历 void levelorder(BiNode*root);//层序遍历 int count(BiNode* root);//计算结点数 int depth(BiNode* root);//计算深度

void display(ostream& os,BiNode* root,int dep);//打印

static bool leastCommanAncestor(BiNode *root, T va, T vb, BiNode

*&result, BiNode* parrent);//求最近共同祖先

private:

BiNode *rootptr; };

五、算法设计

1、创建二叉树

//实现外部递归调用 void BiTree::creat() { creat(rootptr);

}

//类体内递归创建二叉树 template

void BiTree::creat(BiNode * & root) { T item; cin>>item;

if(item=='#') root=NULL; else

{

4