二叉树的遍历.docx

二叉树的遍历.docx

《二叉树的遍历.docx》由会员分享，可在线阅读，更多相关《二叉树的遍历.docx（22页珍藏版）》请在冰点文库上搜索。

二叉树的遍历

数据结构课程设计

实验报告

题目名称：

二叉树的遍历及左右子树的交换

学院：

信息科学与工程学院

一、问题描述

实现二叉树的中序、前序、后序遍历的递归、非递归遍历算法，层次遍历的非递归遍历算法，应包含建树的实现，其次将其所有结点的左右子树交换。

二、基本要求

要求：

首先要按照一种确定的遍历顺序建立二叉树，然后分别利用递归和非递归算法显示该二叉树的前序、中序、后序遍历，利用非递归算法显示其层次遍历，最后交换结点的左右子树，实现所有结点的左右子树交换，并且验证交换结果是否正确。

三、数据结构的设计

由数据结构中二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，所以在本程序中二叉树的构造采用二叉链表的链式存储结构，链表中的结点应包含三个域：

数据域和左、右孩子的指针域。

这种存储结构可以方便二叉树的建立以及遍历。

1、结点的数据结构

structBiTNode

{

//数据

chardata;

//左右孩子指针

structBiTNode*lchild,*rchild;

}

2、基本操作

intCreateBiTree（BiTree&T）

初始条件：

按照结点的先序序列创建二叉树；

操作结果：

构造一棵二叉树。

voidPreOrder（BiTreeT）

初始条件：

二叉树T存在

操作结果：

按照前序遍历（递归）方法遍历二叉树

voidInOrder（BiTreeT）

初始条件：

二叉树T存在

操作结果：

按照中序遍历（递归）方法遍历二叉树

voidPostOrder（BiTreeT）

初始条件：

二叉树T存在

操作结果：

按照后序遍历（递归）方法遍历二叉树

voidPreOrder2（BiTreeT）

初始条件：

二叉树T存在

操作结果：

按照前序遍历（非递归）方法遍历二叉树

voidInOrder2（BiTreeT）

初始条件：

二叉树T存在

操作结果：

按照中序遍历（非递归）方法遍历二叉树

voidPostOrder2（BiTreeT）

初始条件：

二叉树T存在

操作结果：

按照后序遍历（非递归）方法遍历二叉树

voidLevelOrder（BiTreeT）

初始条件：

二叉树T存在

操作结果：

按照层次遍历（非递归）方法遍历二叉树

voidSwapChild（BiTNode**p）

初始条件：

二叉树T存在

操作结果：

将二叉树左右结点交换

四、软件模块结构图

、

五、程序流程图

六、调试分析

运行程序，例如输入如下所示的二叉树。

A

BC

DEF

时间复杂度分析：

很显然，前序.中序.后序递归算法的复杂度是相同的，递归算法非常的简单。

例如前序先访问跟节点，然后访问左节点，再访问右节点。

仔细看一下递归程序，就会发现，其实每次都是子树的左子树（lchild），直到左子树为空，然后开始从递归的最深处返回，然后开始恢复递归现场，访问右子树。

其实过程很简单：

一直往左走 root->lchild->lchild->lchild...->null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，时间方面每个节点调用一次函数，访问一次，是O（n）.没有空间开销，所以是0.中序、后序递归算法同前序一样。

时间复杂度是O（n）,空间复杂度是0.同理可知中序与后序也是一样的。

非递归层序遍历有不一样。

层序遍历中每次将节点压入队，然后弹出，再让左子树入队，再让右子树入队，在遍历过程中，左右子树依次入队出队。

时间复杂度O（n），空间复杂度为0。

问题一：

刚开始编创建算法的时候调试总是出错，后来经过参考数据结构相关资料才发现有一个地方少写一行申请空间的代码。

问题二：

非递归算法在编程时都是不很顺利，其中层序遍历有点难，需要掌握队列的知识，但是经过我的仔细分析，最终成功的解决了这个问题。

问题三：

要注意输入必要的头文件，否则编译时会出错，有时不知道头文件可以查阅书本。

七、测试数据

数据测试主要是由截图来说明，编译成功后，按照前序遍历的方法输入子树，空子树用#表示，在本程序中输入的是一个有六个结点的二叉树（见上图），输入ABD##E##CF###,则构成上图所示的二叉树。

输入二叉树后，分别调用前序遍历函数、中序遍历函数、后序遍历函数以及层次遍历函数，在功能实现后调换二叉树所有的左右子树，再分别前序遍历函数、中序遍历函数、后序遍历函数以及层次遍历函数。

所有功能都实现后，退出程序。

程序运行中的截图如下所示：

1主菜单界面

2建立一棵有六个结点的二叉树

3随机遍历二叉树

4交换左右子树

5随机遍历二叉树

0退出程序

八、用户使用手册

该程序主要用于求一个二叉树的各种遍历，用户可以通过先序遍历建立一个二叉树，然后可以得到其中、后序遍历以及层次遍历，此外，该程序还可以进行二叉树左右子树的交换，用户可以根据程序的提示进行相应的操作。

九、心得体会

为期两周的课程设计结束了，在这次的课程设计中我们将抽象的数据结构理论知识与大一所学的C++语言相结合，完成了这次课程设计。

在完成这个课程设计的过程中，从问题分析、程序设计以及程序调试每个环节都必须要做到完美，因为这几环都是环环相扣的，只有在前一环做好的情况下才能完好的做第二步 。

 课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程．”千里之行始于足下”。

通过这次课程设计，我深深体会到这句千古名言的真正含义．我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础． 通过这次程序设计，我在许多方面都有所提高。

通过这次课程设计，综合运用本专业所学课程：

数据结构与C语言程序的理论知识，同时也将相关的理论知识都有了全面的复习，独立思考的能力也有了提高。

在这次设计过程中，体现出自己单独设计程序的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。

在此感谢我们的所有的课程设计的指导老师.，老师严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；这次课程设计中遇到了各种各样的困难，有些不能自己解决的都得到老师您的细心指导。

而您开朗的个性和宽容的态度，也帮助我能够很顺利的完成了这次课程设计。

同时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊。

六、源程序

#include

#include

#include

#include

usingnamespacestd;

//二叉树结点

typedefstructBiTNode{

//数据

chardata;

//左右孩子指针

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

//按先序序列创建二叉树

intCreateBiTree（BiTree&T）{

chardata;

//按先序次序输入二叉树中结点的值（一个字符），'#'表示空树

scanf（"%c",&data）;

if（data=='#'）{

T=NULL;

}

else{

T=（BiTree）malloc（sizeof（BiTNode））;

//生成根结点

T->data=data;

//构造左子树

CreateBiTree（T->lchild）;

//构造右子树

CreateBiTree（T->rchild）;

}

return0;

}

//输出

voidVisit（BiTreeT）{

if（T->data!

='#'）{

printf（"%c",T->data）;

}

}

//先序遍历

voidPreOrder（BiTreeT）{

if（T!

=NULL）{

//访问根节点

Visit（T）;

//访问左子结点

PreOrder（T->lchild）;

//访问右子结点

PreOrder（T->rchild）;

}

}

//中序遍历

voidInOrder（BiTreeT）{

if（T!

=NULL）{

//访问左子结点

InOrder（T->lchild）

//访问根节点

Visit（T）;

//访问右子结点

InOrder（T->rchild）;

}

}

//后序遍历

voidPostOrder（BiTreeT）{

if（T!

=NULL）{

//访问左子结点

PostOrder（T->lchild）;

//访问右子结点

PostOrder（T->rchild）;

//访问根节点

Visit（T）;

}

}

/*先序遍历（非递归）

思路：

访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

*/

voidPreOrder2（BiTreeT）{

stackstack;

//p是遍历指针

BiTreep=T;

//栈不空或者p不空时循环

while（p||!

stack.empty（））{

if（p!

=NULL）{

//存入栈中

stack.push（p）;

//访问根节点

printf（"%c",p->data）;

//遍历左子树

p=p->lchild;

}

else{

//退栈

p=stack.top（）;

stack.pop（）;

//访问右子树

p=p->rchild;

}

}//while

}

/*中序遍历（非递归）

思路：

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

先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

*/

voidInOrder2（BiTreeT）{

stackstack;

//p是遍历指针

BiTreep=T;

//栈不空或者p不空时循环

while（p||!

stack.empty（））{

if（p!

=NULL）{

//存入栈中

stack.push（p）;

//遍历左子树

p=p->lchild;

}

else{

//退栈，访问根节点

p=stack.top（）;

printf（"%c",p->data）;

stack.pop（）;

//访问右子树

p=p->rchild;

}

}//while

}

//后序遍历（非递归）

typedefstructBiTNodePost{

BiTreebiTree;

chartag;

}BiTNodePost,*BiTreePost;

voidPostOrder2（BiTreeT）{

stackstack;

//p是遍历指针

BiTreep=T;

BiTreePostBT;

//栈不空或者p不空时循环

while（p!

=NULL||!

stack.empty（））{

//遍历左子树

while（p!

=NULL）{

BT=（BiTreePost）malloc（sizeof（BiTNodePost））;

BT->biTree=p;

//访问过左子树

BT->tag='L';

stack.push（BT）;

p=p->lchild;

}

//左右子树访问完毕访问根节点

while（!

stack.empty（）&&（stack.top（））->tag=='R'）{

BT=stack.top（）;

//退栈

stack.pop（）;

BT->biTree;

printf（"%c",BT->biTree->data）;

}

//遍历右子树

if（!

stack.empty（））{

BT=stack.top（）;

//访问过右子树

BT->tag='R';

p=BT->biTree;

p=p->rchild;

}

}//while

}

//交换左右子树（递归算法）

voidSwapChild（BiTNode**p）{BiTNode*temp;

if（（*p））{

//交换左右子树指针

temp=（*p）->lchild;

（*p）->lchild=（*p）->rchild;

（*p）->rchild=temp;

SwapChild（&（（*p）->lchild））;

SwapChild（&（（*p）->rchild））;}

}

//层次遍历

voidLevelOrder（BiTreeT）{

BiTreep=T;

//队列

queuequeue;

//根节点入队

queue.push（p）;

//队列不空循环

while（!

queue.empty（））{

//对头元素出队

p=queue.front（）;

//访问p指向的结点

printf（"%c",p->data）;

//退出队列

queue.pop（）;

//左子树不空，将左子树入队

if（p->lchild!

=NULL）{

queue.push（p->lchild）;

}

//右子树不空，将右子树入队

if（p->rchild!

=NULL）{

queue.push（p->rchild）;

}

}

}

intmain（）

{

inti;

BiTreeT;

loop1:

cout<<"*-*-*-*-*-*-*-*-*-*-*可选择的操作*-*-*-*-*-*-*-*-*-*-*-*-*"<

cout<

cout<<"**1.按先序序列创建二叉树**"<

cout<

cout<<"**2.先序遍历（非递归）**"<

cout<

cout<<"**3.先序遍历（递归）**"<

cout<

cout<<"**4.中序遍历（非递归）**"<

cout<

cout<<"**5.中序遍历（递归）**"<

cout<

cout<<"**6.后序遍历（非递归）**"<

cout<

cout<<"**7.后序遍历（递归）**"<

cout<

cout<<"**8.层序遍历**"<

cout<

cout<<"**9.左右子树交换**"<

cout<

cout<<"*-*-*-*-*-*-*-*-*-*-*-*0.退出*-*-*-*-*-*-*-*-*-*-*-*-*-*-*"<

cout<

cout<<"请输入你的选择:

"<

cin>>i;

switch（i）

{

case1:

{

printf（"请输入所要创建的二叉树的先序序列：

\n"）;

BiTreeT;

CreateBiTree（T）;

system（"cls"）;

gotoloop1;

}break;

case2:

{

printf（"\n"）;

printf（"先序遍历（非递归）：

\n"）;

printf（"\n"）;

PreOrder2（T）;

getchar（）;

system（"cls"）;

gotoloop1;

}break;

case3:

{printf（"先序遍历（递归）：

\n"）;

PreOrder（T）;

printf（"\n"）;

getchar（）;

system（"cls"）;

gotoloop1;

}break;

Case4；{

printf（"中序遍历（非递归）：

\n"）;

InOrder2（T）;

printf（"\n"）;

getchar（）;

system（"cls"）;

gotoloop1;

}break;

case5:

{

printf（"中序遍历（递归）：

\n"）;

InOrder（T）;

printf（"\n"）;

system（"cls"）;

getchar（）;

gotoloop1;

}break;

case6:

{

printf（"后序遍历（非递归）：

\n"）;

PostOrder2（T）;

printf（"\n"）;

getchar（）;

system（"cls"）;

gotoloop1;

}break;

case7:

{

printf（"后序遍历：

\n"）;

PostOrder（T）;

printf（"\n"）;

getchar（）;

system（"cls"）;

gotoloop1;

}break;

case8:

{

printf（"层次遍历：

\n"）;

LevelOrder（T）;

printf（"\n"）;

getchar（）;

system（"cls"）;

gotoloop1;

}break;

case9:

{

SwapChild（&T）;

printf（"交换成功!

\n"）;

printf（"\n"）;

getchar（）;

system（"cls"）;

gotoloop1;

}break;

case0:

{

system（"cls"）;

cout<<"谢谢使用!

\n";

}break;

default:

cout<<"error!

"<

getchar（）;

system（"cls"）;

gotoloop1;

break;

}

return0;

}