2023年6月22日发(作者：)

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

二叉树的建立与遍历实验报告

级 班 年 月 日 姓名 学号_

1．实验题目

建立一棵二叉树,并对其进行遍历(先序、中序、后序），打印输出遍历结果.

2．需求分析

本程序用VC编写，实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果.

①

输入的形式和输入值的范围：

输入二叉树的先序，当其结点为空时,需要输入＃.（输入的先序仅含字母和＃）

②

输出的形式：输出二叉树的先序、中序、后序。

③

程序所能达到的功能：实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、

后序），并且打印输出遍历结果。

④

测试数据：

输入数据：

输入ABC＃#DE#G#＃F#＃＃

输出结果：

二叉树的先序遍历为：

ABCDEGF

二叉树的中序遍历为:

CBEGDFA

二叉树的后序遍历为:

CGEFDBA

3．概要设计

1)

为了实现上述程序功能，需要定义二叉链表的抽象数据类型：

typedef struct BinaryTreeNode

{

TElemType data；//二叉树结点中的数据域

struct BinaryTreeNode *lchild , *rchild； //二叉树结点的左孩子和右孩子指针

｝BinaryTreeNode ，*BiTree；

基本操作：

第 1页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

A.

void CreateBinaryTree （BiTree ＆T）

初始条件：无

操作结果:建立了二叉树。

B。 void PreOrder（BiTree T)

初始条件：存在一棵二叉树

操作结果：先序遍历二叉树,并且输出先序遍历的结果。

C. void MidOrder（BiTree T)

初始条件:存在一棵二叉树

操作结果:中序遍历二叉树，并且输出中序遍历的结果。

D. void PostOrder(BiTree T）

初始条件：存在一棵二叉树

操作结果：后序遍历二叉树，并且输出后序遍历的结果。

程序包含5个函数：

错误!主函数main(）

错误!先序建立二叉树 void CreateBinaryTree （BiTree ＆T）

错误!先序遍历二叉树，并且输出先序遍历的结果 void PreOrder(BiTree T）;

错误!中序遍历二叉树，并且输出中序遍历的结果 void MidOrder（BiTree T)；

错误!序遍历二叉树，并且输出后序遍历的结果 void PostOrder（BiTree T）;

各函数间关系如下:

CreateBinaryTree

PreOrder

MidOrder

PostOrder

主函数main()

4．详细设计

第 2页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

1)

二叉链表的定义

typedef struct BinaryTreeNode

{

定义一个树结点的数据域;

定义一个该结点的左孩子指针和右孩子指针；

}

2)

void CreateBinaryTree （BiTree &T)//先序建立二叉树

｛

输入一个字符量；

if（输入字符== '＃’） T指针置值为NULL;

else

{

动态申请一个指向二叉树结构体的指针

把输入字符赋值给新指针的数据域data；

调用CreateBinaryTree（新指针的lchild成员）； 调用CreateBinaryTree(新指针的rchild成员)；

｝

｝

3)

void PreOrder(BiTree T） //先序遍历二叉树

｛

if（T指针不为NULL）

{

输出T的data域；

先序遍历左子树;

先序遍历右子树;

｝

}

4)

void MidOrder（BiTree T） //中序遍历二叉树

第 3页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

{

}

5)

void PostOrder（BiTree T） //中序遍历二叉树

if(T指针不为NULL)

{

｝

中序遍历左子树；

输出T的data域;

中序遍历右子树；

｛

if（T指针不为NULL)

｛

后序遍历左子树;

后序遍历右子树;

输出T的data域；

}

}

5．调试分析

在编写程序过程中，我将scanf("%c”,&ch）中的％c写成%d，程序运行了一段时间没有结果，经过检查，发现了这个错误。编写程序不能有一点马虎，否则后续纠错工作很辛苦，编写程序的进度变慢。

6．使用说明

程序名为：二叉树遍历。exe,运行环境为DOS。程序执行后显示

输入字符,先序建立二叉树：

此时请输入一棵二叉树的先序，并且当结点为空时,输入#

输入完成后，会输出该二叉树的先序遍历、中序遍历和后序遍历

7．测试结果

第 4页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

1)

输入数据：

输入ABC＃＃DE＃G#＃F#＃＃

输出结果：

二叉树的先序遍历为：

ABCDEGF

二叉树的中序遍历为：

CBEGDFA

二叉树的后序遍历为：

CGEFDBA

2)

输入数据:

输入AB＃＃C＃＃

输出结果:

二叉树的先序遍历为：

ABC

二叉树的中序遍历为：

BAC

二叉树的后序遍历为：

BCA

3)

二叉树如下：

先序输入这棵二叉树，程序运行结果为：

程序源代码:

第 5页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

＃include〈stdio。h>

#include〈stdlib。h〉

typedef char TElemType;

typedef struct BinaryTreeNode//二叉链表的存储结构

{

TElemType data；

struct BinaryTreeNode *lchild ， *rchild；

}BinaryTreeNode ，＊BiTree;

void CreateBinaryTree (BiTree &T)//先序建立二叉树

{

char ch；

scanf（”％c”,＆ch)；

if（ch == ’＃') T=NULL;

第 6页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

else

｛

if(!（T = (BinaryTreeNode ＊）malloc (sizeof(BinaryTreeNode）)））

exit （-1)；

//判断malloc函数是否获得符合要求的内存块，是则继续程序，否则使用exit函数强制退出程序

//如果malloc函数无法获得符合要求的内存块，malloc函数会返回NULL指针

T->data=ch;

CreateBinaryTree(T->lchild）;

CreateBinaryTree(T—〉rchild）;

｝

}

void PreOrder（BiTree T)//先序遍历二叉树

｛

if(T）

第 7页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

｛

printf(”%c ",T->data)；

PreOrder（T-〉lchild）;

PreOrder（T->rchild)；

｝

}

void MidOrder（BiTree T）//中序遍历二叉树

｛

if(T）

｛

MidOrder（T—>lchild）;

printf（”%c ”,T->data)；

MidOrder（T->rchild);

}

第 8页，共 10页

(完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

｝

void PostOrder(BiTree T）//后序遍历二叉树

｛

if（T)

｛

PostOrder（T—>lchild)；

PostOrder（T—>rchild）；

printf（”％c ”,T—〉data）；

}

}

void main()

｛

BiTree Tree；

printf("输入字符，先序建立二叉树：n”);

第 9页，共 10页 (完整word版)二叉树的建立与遍历实验报告(c语言编写,附源代码)

CreateBinaryTree（Tree)；

printf("二叉树的先序遍历为：n”）;

PreOrder(Tree);

printf（”n二叉树的中序遍历为：n"）；

MidOrder(Tree）;

printf("n二叉树的后序遍历为：n")；

PostOrder(Tree)；

getchar();

getchar()；

｝

第 10页，共 10页