层次遍历

更新时间:2023-07-23 22:37:59 阅读：评论：0

年级	2009	班号	组号	学号
专业	数学与应用数学	班号	组号	姓名
实验名称	二叉树的遍历			实验室	9202
实验目的或要求	了解二叉树的定义、性质、存储结构等相关知识，在熟悉这些内容的基础上掌握二叉树在某种存储结构下遍历以及相关算法的实现及应用，能根据本章所学到的有关知识设计出有效的算法。
实验原理（算法流 flying fish程）	1、实验内容二叉树的创建和遍历演示（1）从键盘输入二叉树的各结点值，按先序递归方式创建二叉树（2）分别实现先序、中序、后序递归遍历二叉树（3）输出二叉树的按层次遍历序列 2、存储结构描述及说明用链式存储结构储存二叉树，结点定义如下： typedef struct BiTNode { char data; struct BiTNodelchild,rchild; } data表示二叉树中的字符。lchild为指向一个包含（data lchild rchild）的结构体变量的指针变量，指向二叉树的左孩子。rchild为指向一个包含（data lchild rchild）的结构体变量的指针变量，指向二叉树的右孩子。 victoriacross3、函数说明 BiTNode* CreatBiTree()是返回值为指向结构体指针的函数，带头结点，用于建立二叉树。 void PreOrderTraver(): 是返回值为空的递归函数，用于二叉树的先序遍历。 void InOrderTraver(BiTNode* T): 是返回值为空的递归函数，用于二叉树的中序遍历。 void PostOrderTraver(BiTNode* T): 是返回值为空的递归函数，用于二叉树的后序遍历。 void LevelorderTraver(BiTNode *T):是返回值为空的函数，用于二叉树的层次遍历。 4、模块之间的调用关系 main PreOrderTraver InOrderTraver jidePostOrderTraver LevelorderTraver （写不完时，可另加附页。）

雅思阅读评分标准

组内分工（可选）
实验结果 osaki分析及心得体会	实验结果分析：二叉树如下图：本实验中输入的二叉树如左图所示，以@代表空子树，按先序递归方式输入为abd@@eg@@@c@fh@@@。先序遍历二叉树，结果应为abdegcfh。中序遍历二叉树，结果应为dbgeachf。后序遍历二叉树，结果应为dgebhfca。层次遍历二叉树，结果应为abcdefgh。结果均与上图中运行的结果一致，正确。心得体会： 1．通过本次试验，让我更深刻的理解了二叉树的性质。 2．通过这次实验，我更深刻的理解了递归算法的内涵，并熟悉了队列的应用。 3．通过这次实验，我发现了很多自己平时疏忽的细节，以后再学习过程中会注意。
成绩评定	教师签名：年月日

二叉树遍历源代码如下：

#include "stdio.h"

#include "stdlib.h"

typedef struct BiTNode

{

char data;

struct BiTNode*lchild,*rchild;

}BiTNode;

BiTNode* CreatBiTree()

{

BiTNode*Root;

char c;

scanf("%c",&c);

if(c=='@')Root=NULL; /*以@字符表示空子树*/

{

Root=(BiTNode*)malloc(sizeof(BiTNode)); /*分配存储空间*/

Root->data=c;

Root->lchild=CreatBiTree(); /*对函数进行递归调用*/

Root->rchild=CreatBiTree();

}

return(Root); /*返回二叉树根指针*/

}

void PreOrderTraver(BiTNode* T)

{

if(T!=NULL)

{

printf("%c",T->data); /*访问根结点*/

PreOrderTraver(T->lchild); /*递归调用函数进行先序遍历T的左子树*/

PreOrderTraver(T->rchild); /*递归调用函数进行先序遍历T的右子树*/domination

}

void InOrderTraver(BiTNode* T)

{

if(T!=NULL)

{

InOrderTraver(T->lchild); /*递归调用函数进行中序遍历T的左子树*/

printf("%c",T->data); /*访问根结点*/

InOrderTraver(T->rchild); /*递归调用函数进行中序遍历T的右子树*/

}

void PostOrderTraver(BiTNode* T)

{

bkd

if(T!=NULL)

{

PostOrderTraver(T->lchild); /*递归调用函数进行后序遍历T的左子树*/

PostOrderTraver(T->rchild); /*递归调用函数进行后序遍历T的右子树*/

printf("%c",T->data); /*访问根结点*/

}

void LevelorderTraver(BiTNode *T)

{

int front=0,rear=1; /*用队列进行存储并初始化*/

BiTNode *q[100];

shineq[0]=T; /*数组储存二叉树指针*/

blazed

while(front<rear) /*当队列为空时结束*/

{

if(q[front]) /*二叉树不为空*/

{

printf("%c",q[front]->data);

q[rear++]=q[front]->lchild; /*将左子树存入队列中*/

无氟冰箱

q[rear++]=q[front]->rchild; /*将右子书存入队列中*/

front++;

}

{

front++;

}

main()

{

BiTNode*T;

printf("请按先序序列输入二叉树结点，以字符@作为空子树\n");

T=CreatBiTree();

printf("先序递归遍历二叉树结果如下:\n");

PreOrderTraver(T);

printf("\n");

printf("中序递归遍历二叉树结果如下:\n");

InOrderTraver(T);

printf("\n");

printf("后序递归遍历二叉树结果如下:\n");

PostOrderTraver(T);

printf("\n");

printf("层次历二叉树结果如下:\n");

LevelorderTraver(T);

printf("\n");

}

本文发布于:2023-07-23 22:37:59，感谢您对本站的认可！

本文链接：https://www.wtabcd.cn/fanwen/fan/90/186678.html

上一篇：shell递归遍历目录中的所有文件、文件夹

下一篇：实验五-二叉树的遍历

标签：二叉树遍历递归结果先序结构

留言与评论（共有 0 条评论）

组内分工（可选）
实验结果 osaki分析及心得体会	实验结果分析：二叉树如下图：本实验中输入的二叉树如左图所示，以@代表空子树，按先序递归方式输入为abd@@eg@@@c@fh@@@。先序遍历二叉树，结果应为abdegcfh。中序遍历二叉树，结果应为dbgeachf。后序遍历二叉树，结果应为dgebhfca。层次遍历二叉树，结果应为abcdefgh。结果均与上图中运行的结果一致，正确。心得体会： 1．通过本次试验，让我更深刻的理解了二叉树的性质。 2．通过这次实验，我更深刻的理解了递归算法的内涵，并熟悉了队列的应用。 3．通过这次实验，我发现了很多自己平时疏忽的细节，以后再学习过程中会注意。
成绩评定	教师签名：年月日