实验报告07-二叉树的递归遍历.doc
文本预览下载声明
实验目的及要求：
了解和掌握二叉树的特点；
掌握二叉树递归算法的实现；
要求完成二叉树的建立、二叉树的先序中序后序递归遍历、二叉树的显示等操作的实现。
实验设备环境及要求：
PC机一台，内存要求128M以上，VC++6.0集成开发环境。
实验内容与步骤：
1、在VC++6.0环境中新建一个工程和C++文件；
2、实现二叉树的建立、二叉树的先序中序后序递归遍历、二叉树的显示等算法，代码如下：
#include stdio.h
#include malloc.h
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}*BTNode;
void CreateBTNode(BTNode b,char *str)
{
BTNode St[MaxSize],p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!=\0)
{
switch(ch)
{
case (:top++;St[top]=p;k=1;break; /*为左节点 */
case ):top--;break;
case ,:k=2;break; /*为右节点 */
default:
p=(BTNode)malloc(sizeof(BTNode));
p-data=ch;p-lchild=p-rchild=NULL;
if(b==NULL) //p指向二叉树的根节点
b=p;
else //已建立二叉树根节点
{
switch(k)
{
case 1:St[top]-lchild=p;break;
case 2:St[top]-rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void DispBTNode(BTNode b)
{
if(b!=NULL)
{
printf(%c,b-data);
if(b-lchild!=NULL||b-rchild!=NULL)
{
printf(();
DispBTNode(b-lchild);
if(b-rchild!=NULL) printf(,);
DispBTNode(b-rchild);
printf());
}
}
}
int visit(ElemType e){
printf(%c,e);
return 1;
}
int PreOrder(BTNode b,int (*visit)(ElemType e)){
if(b){
if(visit(b-data))
if(PreOrder(b-lchild,visit))
if(PreOrder(b-rchild,visit))
return 1;
return 0;
}
else return 1;
}
int InOrder(BTNode b,int (*visit)(ElemType e)){
if(b){
if(InOrder(b-lchild,visit))
if(visit(b-data))
if(InOrder(b-rchild,visit))
return 1;
return 0;
}
else return 1;
}
int PostOrder(BTNode b,int (*visit)(ElemType e)){
if(b){
if(PostOrder(b-lchild,visit))
if(PostOrder(b-rchild,visit))
if(visit(b-data))
return 1;
return 0;
}
else return 1;
}
void main()
{
BTNode b;
CreateBTNode(b,A(B(D,E),C));
DispBTNode(b);
printf(\n);
printf(二叉树的先序遍历序列为：);
PreOrder(b,visit);
printf(\n);
printf(二叉树的中序遍历序列为：);
InOrder(b,visit);
printf(\n);
printf(二叉树的后序遍历序列为
显示全部