数据结构二叉树实验报告.doc

实验三　二叉树的遍历
一、实验目的
１、熟悉二叉树的结点类型和二叉树的基本操作。
２、掌握二叉树的前序、中序和后序遍历的算法。
3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境
运行Ｃ或VC++的微机。
三、实验内容
1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。
2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。
四、设计思路
1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求
2．二叉树采用动态数组
3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点
五、程序代码
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0

typedef struct TNode//结构体定义
{
int data; //数据域
struct TNode *lchild,*rchild; // 指针域包括左右孩子指针
}TNode,*Tree;

void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值
{
int a;
scanf("%d",&a);
if(a==00) // 结点的值为空
*T=NULL;
else // 结点的值不为空
{
*T=(Tree)malloc(sizeof(TNode));
if(!T)
{
printf("分配空间失败！！TAT");
exit(ERROR);
}
(*T)->data=a;
CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树
CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树
}
}

void InitT(Tree *T)//构建空二叉树
{
T=NULL;
}

void DestroyT(Tree *T)//销毁二叉树
{
if(*T) // 二叉树非空
{
DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树
DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树
free(T);
T=NULL;
}
}

void visit(int e)//访问结点
{
printf("%d ",e);
}

void PreOrderT(Tree *T,void(*visit)(int))//先序遍历T
{
if(*T) // 二叉树非空
{
visit((*T)->data); // 先访问根结点
PreOrderT(&((*T)->lchild),visit); // 递归调用函数，先序遍历左子树
PreOrderT(&((*T)->rchild),visit); // 递归调用函数，先序遍历右子树
}
}

void InOrderT(Tree *T,void(*visit)(int))
{
if(*T)
{
InOrderT(&((*T)->lchild),visit); // 递归调用函数，中序遍历左子树
visit((*T)->data); // 访问根结点
InOrderT(&((*T)->rchild),visit); // 递归调用函数，中序遍历右子树
}
}

void PostOrderT(Tree *T,void(*visit)(int))
{
if(*T)
{
PostOrderT(&((*T)->lchild),visit); // 递归调用函数,后序遍历左子树
PostOrderT(&((*T)->rchild),visit); // 递归调用函数,序遍历右子树
visit((*T)->data); // 访问根结点
}
}

void example()
{
int i;
printf("如果你想建立如图所示的二叉树\n");
printf("\n");
printf(" 1 \n");
printf(" / \\ \n");
printf(" 3 3 \n");
printf(" / \\ \\ \n");
printf(" 4 5 7 \n");
printf("\n");
printf("请输入：1 3 4 00 00 5 00 00 3 00 7 00 00\n");
printf("\n按先序次序输入二叉树中结点的值(输入00表示节点为空)\n");
for(i=0;i<71;i++)
printf("*");
printf("\n");
}

int main ()
{
Tree T;
printf("**************欢迎使用！**************潘俊达\n");
example();
printf("\n请输入所要建立的二叉树:\n");
CreateT(&T);
InitT(&T);
int i;
printf("先序遍历二叉树：\n");
PreOrderT(&T,visit);
printf("\n");
printf("\n中序遍历二叉树：\n");
InOrderT(&T,visit);
printf("\n");
printf("\n后序遍历二叉树：\n");
PostOrderT(&T,visit);
printf("\n");
system("PAUSE");
return 0;
}
六、程序截图
1.范例函数显示，并输入先序二叉树节点值

2．先序遍历二叉树

3.中序遍历二叉树

3.后序遍历二叉树