实 验 报 告
题目： 二叉树的遍历及应用
院系： 数学系
专业： 数学与应用数学
学号： 2010114036
姓名： 郭奇瑞
一、 实验名称：二叉树的遍历及应用
二、 实验日期：20##年11月14日
三、 实验要求：编程实现二叉树的建立并对其进行遍历
四、 实验目的：
1、 掌握二叉树链式存储结构的类型定义及实现；
2、 掌握二叉树链式存储结构的各类基本运算方法；
3、 掌握二叉树各个重要性质在解决实际问题中的应用；
4、 掌握二叉树的分析方法、解决方法，从而提高实际编程能力及程序调试能力。
五、 实验内容
1、 创建二叉树；
2、 用递归方法实现二叉树的各种遍历。
六、 程序代码
#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
typedef struct Node
{
char data;
struct Node *LChild;
struct Node *RChild;
}BiTNode,*BiTree;
typedef BiTree StackElementType;
typedef struct
{
StackElementType elem[Stack_Size];
int top;
}SeqStack;
//初始化
void InitStack(SeqStack *S)
{
S->top=-1;
}
//进栈
int Push(SeqStack *S,StackElementType x)
{ if(S->top==Stack_Size-1) return(FALSE);
S->top++;
S->elem[S->top]=x;
return(TRUE);
}
//出栈
int Pop(SeqStack *S,StackElementType *x)
{
if(S->top==-1)
return(FALSE);
else
{
*x=S->elem[S->top];
S->top--;
return(TRUE);
}
}
//先序遍历
void PreOrder(BiTree root)
{
if(root!=NULL)
{
printf("%c",root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
//中序遍历
void InOrder(BiTree root)
{ if(root!=NULL)
{ InOrder(root->LChild);
printf("%c",root->data);
InOrder(root->RChild);
}
}
//后序遍历
void PostOrder(BiTree root)
{
if(root!=NULL)
{
PostOrder(root->LChild);
PostOrder(root->RChild);
printf("%c",root->data);
}
}
//创建二叉链表
void CreateBiTree(BiTree *bt)
{
char ch;
ch=getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode));
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild));
CreateBiTree(&((*bt)->RChild));
}
}
//后序遍历球二叉树高度
int PostTreeDepth(BiTree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild);
hr=PostTreeDepth(bt->RChild);
max=hl>hr?hl:hr;
return(max+1);
}
else return(0);
}
//横向打印二叉树
void PrintTree(BiTree bt,int nLayer)
{
int i;
if(bt==NULL) return;
PrintTree(bt->RChild,nLayer+1);
for( i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",bt->data);
PrintTree(bt->LChild,nLayer+1);
}
void main()
{
BiTree root;
printf("请输入序列:\n");
CreateBiTree(&root);
printf("输出结果为:\n");
printf("先序遍历结果:\n");
PreOrder(root);
printf("\n中序遍历结果:\n");
InOrder(root);
printf("\n后序遍历结果:\n");
PostOrder(root);
printf("\n二叉树的深度:\n");
printf("%d",PostTreeDepth(root));
printf("\n横向打印二叉树结果:\n");
PrintTree(root,5);
}
七、 成果展示
第二篇：二叉树的建立及遍历实验报告
实验三：二叉树的建立及遍历
【实验目的】
（1） 掌握利用先序序列建立二叉树的二叉链表的过程。
（2） 掌握二叉树的先序、中序和后序遍历算法。
【实验内容】
1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。
如：输入先序序列abc###de###，则建立如下图所示的二叉树。
并显示其先序序列为：abcde
中序序列为：cbaed
后序序列为：cbeda
【实验步骤】
1.打开VC++。
2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
#include <stdio.h>
#include <malloc.h>
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T)
{
TElemType ch;
scanf("%c",&ch);
if (ch=='#')
T= NULL;
else
{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
return OVERFLOW;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
} // CreateBiTree
void PreOrder(BiTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
void main()
{
BiTree T;
CreateBiTree(T);
printf("\n先序遍历序列:");
PreOrder(T);
printf("\n中序遍历序列:");
InOrder(T);
printf("\n后序遍历序列:");
PostOrder(T);
}
【实验心得】
这次实验主要是通过先序序列建立二叉树，和二叉树的先序、中序、后续遍历算法。通过这次实验，我巩固了二叉树这部分知识,从中体会理论知识的重要性。
在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。
例如进行二叉树的遍历的时候，要先理解各种遍历的特点。先序遍历是先遍历根节点，再依次先序遍历左右子树。中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。而后序遍历则是先依次后续遍历左右子树，再访问根节点。
掌握了这些，在实验中我们就可以融会贯通，举一反三。
所以，这次实验让我懂得了理论知识的重要性，只有领悟了最基本的知识，在实验过程中我们才能够独立的思考，大胆的推断，不断的创新，进而提高动手能力。