数据结构课程设计二叉树.docx

数据结构课程设计二叉树.docx

《数据结构课程设计二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计二叉树.docx（22页珍藏版）》请在冰点文库上搜索。

数据结构课程设计二叉树

安徽理工大学

数据结构

课程设计说明书

题目:

二叉树的遍历算法集成

院系：

计算机科学与工程学院

专业班级：

学号：

学生姓名：

指导教师：

2010年1月11日

安徽理工大学课程设计〔论文〕任务书

计算机科学与工程学院计算机软件教研室

学号

2008303003

学生姓名

刘威

专业〔班级〕

信息08-1

设计题目

二叉树的遍历算法集成

设

计

技

术

参

数

系统平台：

WindowsXP

设

计

要

求

〔1〕界面友好，易于操作。

可采用菜单或其它人机对话方式进行选择

〔2〕实现各种二叉树的遍历。

包括先序遍历、中序遍历、后序遍历的递归或非递归算法。

〔3〕要求能查找任一结点在某种遍历序列中的前驱和后继。

〔4〕演示程序以人机对话的形式进行。

每次测试完毕正确显示各种遍历序列。

工

作

量

课程设计报告要求不少于3000字。

源程序要求不少于300行

工

作

计

划

12月14日-12月16日查找相关资料

12月18日-12月21日思考相关问题

12月22日-12月28日设计算法

12月29日-1月05日编写代码

1月06日-1月09日撰写课程设计报告

参

考

资

料

[1]秦锋.数据结构（C语言版）.合肥:

中国科学技术大学出版社,2007

[2]温秀梅.VisualC++面象对象程序设计教程与实验.北京：

清华大学出版社2006

[3]何钦铭.C语言程序设计.北京:

高等教育出版社，2008

指导教师签字

教研室主任签字

2009年11月16日

学生姓名：

刘威学号：

2008303003专业班级：

信息08-1

课程设计题目：

二叉树的遍历算法集成

指导教师评语：

成绩：

指导教师：

年月日

安徽理工大学课程设计〔论文〕成绩评定表

目　　录

2、概要设计2

2.1功能设计2

2.2算法流程图3

3.3调试分析14

调试结果14

算法分析18

4、总结18

参考文献19

1、需求分析

数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业根底课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。

数据结构只要研究四个方面的问题：

（1）数据的逻辑结构，即数据之间的逻辑关系；

（2）数据的物理结构，即数据在计算机内的存储方式；（3）对数据的加工，即基于某种存储方式的操作算法；（4）算法的分析；即评价算法的优劣。

本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。

本程序用VC++6.0编写，可以实现各种二叉树的遍历。

包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。

根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。

其中二叉树的结点用字符表示。

（1）先创立二叉树：

按先序次序输入，构造二叉链表表示的二叉树。

（2）设计算法：

先序遍历,中序遍历,后序遍历.在做到层序遍历时，应注意算法如下：

根结点入队，队头元素出队，左孩子不为空入队右孩子不为空入队的顺序进行。

（3）可以参加求二叉树的深度二叉树的叶子数二叉树的结点总数等一些简单的算法。

（4）设计main（）函数调用以上步骤实现相关功能。

2、概要设计

2.1功能设计

〔1〕typedefstructBTNode

定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。

和单链表类似，一个二叉链表由头指针唯一确定，假设二叉树为空，那么头指针指向空。

并且结点内容的数据类型为字符型。

〔2〕CreateBiTree（BiTree&T）

此函数的功能是构建二叉树。

从键盘上按先序次序输入字符构造二叉链表表示的二叉树T，其中用星号表示空树。

〔3〕NRPreOrder（BiTreebt）

此函数的功能是用非递归的方法实现二叉树的先序遍历算法。

调用此函数可以获得二叉树的非递归的先序遍历的结果。

〔4〕NRInOrder（BiTreebt）

此函数的功能是用非递归的方法实现二叉树的中序遍历算法。

调用此函数可以获得二叉树的非递归的中序遍历的结果。

〔5〕NRPostOrder（BiTreebt）

此函数的功能是用非递归的方法实现二叉树的后序遍历算法。

调用此函数可以获得二叉树的非递归的后序遍历的结果。

其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。

需要判断根结点的左右子树是否均遍历过。

可采用标记法，结点入栈时，配一个标志tag一同入栈1：

遍历左子树的现场保护，2：

遍历右子树前的现场保护。

首先将bt和tag（为1）入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。

〔6〕PreOrderTraverse（BiTreeT）

函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。

〔7〕InOrderTraverse（BiTreeT）

函数功能是用递归的方法对二叉树进行中序遍历，调用此函数可以获得二叉树的递归的中序遍历的结果。

〔8〕PostOrderTraverse（BiTreeT）

函数功能是用递归的方法对二叉树进行后序遍历，调用此函数可以获得二叉树的递归的后序遍历的结果。

〔9〕LevelOrderTraverse（BiTreeT）

调用此函数可以获得二叉树的层序遍历。

〔10〕BTDepth（BiTreeT）

求二叉树的深度的算法。

〔11〕Leaf（BiTreeT）

求二叉树的叶子数的算法。

〔12〕NodeCount（BiTreeT）

求二叉树的结点总数的算法。

〔13〕main（）

主函数用while（）与switch（select）语句对二叉树的操作的算法进行了设计。

可以实现以上函数的功能，并能退出程序。

2.2算法流程图

先设计出二叉树的一些算法的函数，如非递归遍历、递归遍历、层次遍历等一些算法。

然后在主函数中逐一调用。

其中，在求任意结点在中序遍历前驱后继算法时利用了递归的中序遍历的算法。

算法流程图如图1所示。

图1算法流程图

3、详细设计

3.1界面设计

设计的界面如图2所示。

图2界面

3.2详细代码设计

〔1〕定义二叉树

用链式存储结构存储二叉树。

其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。

定义二叉树结点值的类型为字符型且结点个数不超过10个。

typedefcharElemType;

//结点个数不超过10个

constintMaxLength=10;

typedefstructBTNode{

ElemTypedata;

structBTNode*lchild,*rchild;

}BTNode,*BiTree;〔2〕查找模块

〔2〕构造二叉链表

创立二叉链表存储的二叉树。

按二叉树带空指针的先序次序输入结点值，结点类型为字符型。

按先序次序输入，其中*表示空结点。

算法是按照先序遍历思想设计的。

构造二叉链表表示的二叉树T，星号表示空树。

voidCreateBiTree（BiTree&T）{

charch;

ch=getchar（）;

if（ch=='*'）T=NULL;

else{

if（!

（T=（BTNode*）malloc（sizeof（BTNode））））cout<<"mallocfail!

";

T->data=ch;

CreateBiTree（T->lchild）;

CreateBiTree（T->rchild）;

}

}

〔3〕非递归的先序遍历算法

函数功能是用非递归的方法对二叉树进行先序遍历。

通过分析可知最后处理过的结点的右子树应该首先被访问，最先处理过的结点的右子树应该最后被访问，显然使用栈可以解决问题。

voidNRPreOrder（BiTreebt）

{BiTreestack[MaxLength],p;

inttop;

if（bt!

=NULL）{

top=0;p=bt;

while（p!

=NULL||top>0）

{while（p!

=NULL）

{

cout<data<<'';

stack[top]=p;

top++;

p=p->lchild;

}

if（top>0）

{top--;p=stack[top];p=p->rchild;}

}

}

}

〔4〕非递归的中序遍历算法

此函数的功能是用非递归的方法实现二叉树的中序遍历算法。

调用此函数可以获得二叉树的非递归的中序遍历的结果。

用非递归调用也得使用栈。

voidNRInOrder（BiTreebt）

{BiTreestack[MaxLength],p;

inttop;

if（bt!

=NULL）{

top=0;p=bt;

while（p!

=NULL||top>0）

{while（p!

=NULL）

{

stack[top]=p;

top++;

p=p->lchild;

}

if（top>0）

{top--;p=stack[top];cout<data<<'';p=p->rchild;}

}

}

}

〔5〕非递归的后序遍历算法

此函数的功能是用非递归的方法实现二叉树的后序遍历算法。

调用此函数可以获得二叉树的非递归的后序遍历的结果。

其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。

需要判断根结点的左右子树是否均遍历过。

可采用标记法，结点入栈时，配一个标志tag一同入栈1：

遍历左子树的现场保护，2：

遍历右子树前的现场保护。

首先将bt和tag（为1）入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。

typedefstruct

{

BiTreeptr;

inttag;

}stacknode;

voidNRPostOrder（BiTreebt）

{

stacknodes[MaxLength],x;

BiTreep=bt;

inttop;

if（bt!

=NULL）{

top=0;p=bt;

do

{

while（p!

=NULL）

{

s[top].ptr=p;

s[top].tag=1;

top++;

p=p->lchild;

}

while（top>0&&s[top-1].tag==2）

{

x=s[--top];

p=x.ptr;

cout<data<<'';

}

if（top>0）

{

s[top-1].tag=2;

p=s[top-1].ptr->rchild;

}

}while（top>0）;}

}

〔6〕递归的先序遍历

函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。

算法思想：

假设二叉树为空，那么结束遍历操作；否那么访问根结点；先序遍历根的左子树；先序遍历根的右子树。

voidPreOrderTraverse（BiTreeT）{

if（T）{

cout<data<<'';

PreOrderTraverse（T->lchild）;

PreOrderTraverse（T->rchild）;

}

}

〔7〕递归的中序遍历

函数功能是用递归的方法对二叉树进行中序遍历。

算法思想：

假设二叉树为空，那么结束遍历操作；否那么中序遍历根的左子树；访问根结点；中序遍历根的右子树。

voidInOrderTraverse（BiTreeT）{

if（T）{

InOrderTraverse（T->lchild）;

cout<data<<'';

a[i]=T->data;

i++;

InOrderTraverse（T->rchild）;

}

}

〔8〕递归的后序遍历

函数功能是用递归的方法对二叉树进行中序遍历。

算法思想：

假设二叉树为空，那么结束遍历操作；否那么后序遍历根的左子树；后序遍历根的右子树；访问根结点。

voidPostOrderTraverse（BiTreeT）{

if（T）{

PostOrderTraverse（T->lchild）;

PostOrderTraverse（T->rchild）;

cout<data<<'';

}

}

〔9〕层序遍历

调用此函数可以获得二叉树的层序遍历。

该算法的思想如下：

访问根结点，并将该结点记录下来；假设记录的所有节点都已经处理完毕，那么结束遍历操作；否那么重复以下操作。

取出记录中第一个还没有访问孩子的结点，假设它有左孩子，那么访问做孩子，并记录下来；假设它有右孩子，那么访问右孩子，并记录下来。

voidLevelOrderTraverse（BiTreeT）{

BiTreeQ[MaxLength];

intfront=0,rear=0;

BiTreep;

//根结点入队

if（T）{

Q[rear]=T;

rear=（rear+1）%MaxLength;

}

while（front!

=rear）{

//队头元素出队

p=Q[front];

front=（front+1）%MaxLength;

cout<data<<'';

//左孩子不为空，入队

if（p->lchild）{

Q[rear]=p->lchild;

rear=（rear+1）%MaxLength;

}

//右孩子不为空，入队

if（p->rchild）{

Q[rear]=p->rchild;

rear=（rear+1）%MaxLength;

}

}

}

〔10〕结点在中序遍历的前驱后继

此程序所用的方法并非利用线索二叉树。

对整个二叉树进行中序遍历，看看哪个结点之后是所求结点的前驱，那么该结点就是所求结点的中序前驱。

同样的也可以得到中序后继。

inti;chara[100];

voidInOrderTraverse（BiTreeT）{

if（T）{

InOrderTraverse（T->lchild）;

cout<data<<'';

a[i]=T->data;

i++;

InOrderTraverse（T->rchild）;

}

}

上面是利用的二叉树的中序遍历方法来获得结点的信息，再调用下面语句便可实现以上功能。

在主函数中应用switch（）语句。

cout<<"\n请输入您要在中序中查找前驱后继的结点（字符型）:

\n";

cin>>c;

for（j=0;j

{

if（a[j]==c）

cout<<"结点的前驱为:

\n"<

\n"<

}

break;

3.3调试分析

调试结果

（1）系统界面

系统主界面如图3所示。

图3主界面

（2）创立二叉树

创立后的二叉树如图4所示。

图4创立二叉树

〔3〕二叉树的非递归遍历算法〔前、中、后〕

非递归遍历如图5所示。

图5二叉树的非递归遍历算法〔前、中、后〕

〔4〕二叉树的递归遍历算法〔前、中、后〕

递归遍历如图6所示。

图6二叉树的递归遍历算法〔前、中、后〕

〔5〕二叉树的层次遍历算法

层次遍历如图7所示。

图7二叉树的层次遍历算法

〔6〕求二叉树的深度

创立后的二叉树的深度如图8所示。

图8求二叉树的深度

〔7〕求二叉树的叶子结点

求出的结点的个数如图9所示。

图9求二叉树的叶子结点

〔8〕求二叉树的结点总数

求出的结点总数如图10所示。

图10求二叉树的结点总数

〔9〕求结点在中序遍历的前驱后继

任意一结点的前驱后继如图11所示。

图11求结点在中序遍历的前驱后继

3.3.2算法分析

本程序按递归遍历所消耗的时间复杂度为O〔n〕，其所消耗的空间复杂度也为O〔n〕。

4、总结

虽然都说“程序＝数据结构＋算法〞，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。

我感受最深的一点是：

以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。

感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。

但现在编程感觉完全不同了。

在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？

然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。

最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。

这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。

这样无形中就提高了自己编写的程序的质量。

另外，我还体会到深刻理解数据结构的重要性。

只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。

了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。

我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。

在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！

同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！

在这次实验中，我对参数的调用也进行了很多种尝试，已差不多经能够选择适宜的参数形式来实现函数之间的数据传输交互了。

这次实验中我也出现过一些比拟严重的错误。

在用链表结构编写程序时我错误的把一个定义的一级指针用二级指针来做，结果出现了一些难以想象的后果。

这是我对根本概念理解的模糊不清造成的。

后来在同学的指点下我意识到自己的错误。

不过收获也很不少。

至少我又掌握了指针的应用，。

总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。

参考文献

[1]秦锋.数据结构（C语言版）.合肥:

中国科学技术大学出版社,2007

[2]温秀梅.VisualC++面象对象程序设计教程与实验.北京：

清华大学出版社2006

[3]何钦铭.C语言程序设计.北京:

高等教育出版社，2008