二叉树基本操作--实验报告.doc

实验三
二叉树的基本操作

学院:物理与电子学院
班级:电信1105班
姓名:刘岩
学号:1404110729

一、实验目的
1、熟悉二叉树的基本操作，掌握二叉树的实现以及实际应用。
3、加深对于二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境
1台WINDOWS环境的PC机，装有Visual C++ 6.0。
三、实验内容
1、问题描述
现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：
1> 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。
2> 输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。
3> 查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。
4> 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。
5> 求二叉树的结点个数NodesCount(BTNode *b)
6> 先序遍历的递归算法：void PreOrder(BTNode *b)
7> 中序遍历的递归算法：void InOrder(BTNode *b)
8> 后序遍历递归算法：void PostOrder(BTNode *b)
9> 层次遍历算法void LevelOrder(BTNode *b)

2、基本要求
实现以上9个函数。
主函数中实现以下功能：
创建下图中的树b
输出二叉树b
找到’H’节点，输出其左右孩子值
输出b的高度
输出b的节点个数
输出b的四种遍历顺序

A
B
D
C
E
H
J
K
L
M
N
F
G
I

3、程序编写
上图转化为二叉树括号表示法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

程序:
#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 *FindNode(BTNode *b,ElemType x);//查找节点
int BTNodeHeight(BTNode *b);//求高度
void DispBTNode(BTNode *b);//输出
int NodesCount(BTNode *b);//二叉树的结点个数
void PreOrder(BTNode *b);//先序遍历递归
void InOrder(BTNode *b);//中序遍历递归
void PostOrder(BTNode *b);//后序遍历递归
void LevelOrder(BTNode *b);//层次遍历

//创建
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)
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(")");
}
}
}

//查找节点
BTNode *FindNode(BTNode *b,ElemType x){
BTNode *p;
if(b==NULL)
return b;
else if(b->data==x)
return b;
else{
p=FindNode(b->lchild,x);
if(p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}

//求高度
int BTNodeHeight(BTNode *b){
int lchildh,rchildh;
if(b==NULL)
return (0);
else{
lchildh=BTNodeHeight(b->lchild);
rchildh=BTNodeHeight(b->rchild);
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}

//二叉树的结点个数
int NodesCount(BTNode *b){
if(b==NULL)
return 0;
else
return NodesCount(b->lchild)+NodesCount(b->rchild)+1;
}

//先序遍历递归
void PreOrder(BTNode *b){
if(b!=NULL){
printf("%c",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}

//中序遍历递归
void InOrder(BTNode *b){
if(b!=NULL){
InOrder(b->lchild);
printf("%c",b->data);
InOrder(b->rchild);
}
}

//后序遍历递归
void PostOrder(BTNode *b){
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c",b->data);
}
}

//层次遍历
void LevelOrder(BTNode *b){
BTNode *p;
BTNode *qu[MaxSize];
int front,rear;
front=rear=-1;
rear++;
qu[rear]=b;
while(front!=rear){
front=(front+1)%MaxSize;
p=qu[front];
printf("%c",p->data);
if(p->lchild!=NULL){
rear=(rear+1)%MaxSize;
qu[rear]=p->lchild;
}
if(p->rchild!=NULL){
rear=(rear+1)%MaxSize;
qu[rear]=p->rchild;
}
}
}

void main()
{
BTNode *b,*p,*lp,*rp;
char str[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";//根据树形图改写成的
//二叉树括号表示法的字符串*str

//char str[100];scanf("%s",&str);//自行输入括号表示的二叉树

CreateBTNode(b,str); //创建树b
printf("\n");

printf("输出二叉树:");//输出二叉树b
DispBTNode(b);
printf("\n");

printf("'H'结点:");//找到'H'节点，输出其左右孩子值
p=FindNode(b,'H');
printf("\n");
if (p!=NULL){
printf("左孩子节点的值");
printf("%c",p->lchild->data);printf("\n");
printf("右孩子节点的值");
printf("%c",p->rchild->data);printf("\n");
//此处输出p的左右孩子节点的值
}
printf("\n");

printf("二叉树b的深度:%d\n",BTNodeHeight(b));//输出b的高度
printf("二叉树b的结点个数:%d\n",NodesCount(b));//输出b的节点个数
printf("\n");

printf(" 先序遍历序列:\n");//输出b的四种遍历顺序
printf(" 算法:");PreOrder(b);printf("\n");
printf(" 中序遍历序列:\n");
printf(" 算法:");InOrder(b);printf("\n");
printf(" 后序遍历序列:\n");
printf(" 算法:");PostOrder(b);printf("\n");
printf(" 层次遍历序列:\n");
printf(" 算法:");LevelOrder(b); printf("\n");
}

四、实验心得与小结
通过本次实验，我熟悉二叉树的基本知识内容，对课本的知识有了更加深刻的理解与掌握掌握。通过查阅资料以及百度一些前人的程序设计，我学到了很多原来在课堂上掌握不到的东西，这次是我的第一次完成了二叉树的实现以及实际应用。加深了对二叉树的理解，。本次实验还运用到了递归的使用，是非常新的体验，原来都是停留在概念上的运用递归处理，这次运用到了实际的实验编程中，受益匪浅。这次实验，让我明白了一个道理，实践出真知，只有通过自己的双手实践，才能更好的理解知识与运用。

【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】

精选范本,供参考！