实验三--二叉树的基本运算
- 格式：doc
- 大小：94.00 KB
- 文档页数：13
实验三 二叉树的基本运算
一、实验目的
1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容
1、问题描述
建立一棵二叉树，试编程实现二叉树的如下基本操作：
(1). 按先序序列构造一棵二叉链表表示的二叉树T；
(2). 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
(3). 求二叉树的深度/结点数目/叶结点数目；(选做)
(4). 将二叉树每个结点的左右子树交换位置。（选做）
2、基本要求
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）。
3、测试数据
如输入：abc00de0g00f000（其中ф表示空格字符）
则输出结果为：
先序：a->b->c->d->e->g->f
中序：a->b->c->d->e->g->f
后序：a->b->c->d->e->g->f
三、程序代码
#include
#include
#define OK 1
#define ERROR -1
typedef char TElemType;
int i; typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree&T) //创建二叉树
{
char a;
cin>>a;
if(a=='0') T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) {return ERROR;}
T->data=a;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
int PreOrderTraverse(BiTree&T) //先序遍历二叉树
{
if(T)
{
//cout<<"此为先序遍历"<
cout
if(PreOrderTraverse(T->lchild))
if(PreOrderTraverse(T->rchild))
return OK;
return ERROR;
}else return OK;
}
int InOrderTraverse(BiTree&T) //中序遍历二叉树
{
if(T)
{
//cout<<"此为中序遍历"<
if
(InOrderTraverse(T->lchild))
{
cout
if(InOrderTraverse(T->rchild))
return OK;
}
return ERROR;
}else return OK; }
int PostOrderTraverse(BiTree&T) //后序遍历二叉树
{
if(T)
{
//cout<<"此为后序遍历"<
if (PostOrderTraverse(T->lchild))
if(PostOrderTraverse(T->rchild))
{
cout
i++;
return (OK);
}
return (ERROR);
}
else
return (OK);
}
int CountDepth(BiTree&T) //计算二叉树的深度
{
if(T==NULL)
{
return 0;
}
else
{
int depl=CountDepth(T->lchild);
int depr=CountDepth(T->lchild);
if(depl>depr)
{
return depl+1;
}
else
{
return depr+1;
}
}
}
void main() //主函数
{
BiTree T;
cout<<"请输入二叉树节点的值以创建树"<
CreateBiTree(T); cout<<"此为先序遍历";
PreOrderTraverse(T);
cout<<"end"<
cout<<"此为中序遍历";
InOrderTraverse(T);
cout<<"end"<
cout<<"此为后序遍历";
PostOrderTraverse(T);
cout<<"end"<
}
四、调试结果及运行界面：
五、实验心得
通过这次程序上机实验让我认识到了以前还不太了解的二叉树的性质和作用，这次实验的的确确的加深了我对它的理解。还有很多很多知识我是通过看书本、请教同学老师的，但是想深一层，这都是暴露了我对知识掌握得不牢固的表现，我不能够过分依赖，而是应该平常多多上机实践来巩固知识，发现问题并解决问题。把学过的二叉树的操作的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。
最佳答案
#include
#include
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{
DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{
BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else
{
t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍历二叉树t */
void preorder(BiTree t)
{
if(t!=NULL)
{
printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/* 中序遍历二叉树t */
void inorder(BiTree t) {
if(t!=NULL)
{
inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}
/* 后序遍历二叉树t */
void postorder(BiTree t)
{
if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}
void enqueue(BitTNode *t)
{
if (front!=(rear+1)%M)
{
rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/
BitTNode * delqueue()
{
if(front==rear)return NULL;
{
front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/
/* 按层次遍历二叉树t */
void levorder(BiTree t)
{
BitTNode *p;
