二叉树 C语言
- 格式：doc
- 大小：39.00 KB
- 文档页数：6
实验报告评分：
管理学院系10 级学号PB10204019 姓名杨晓东
二叉树的基本操作实验报告
一．实验内容：实现创建和遍历二叉树的基本操作
二．实验目的：
（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；
（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。
三．问题描述：
（1）编程实现构造一棵二叉树的算法，适合任意合法输入的二叉树的建立，并进行相应异常处理。
（2）编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法可在先序、中序和后序遍历算法中任选其一。
四．基本操作：
（1）二叉树的二叉链表存储表示
typedef struct BiTNode
{char data;
struct BiTNode *lchild,*rchild; //指向该结点的左右孩子指针
}BiTNode,*BiTree;
（2）主要的实现思路：
a.首先定义二叉树的存储形式，这里使用了二叉链表
b.用CreateBiTree(T)构造二叉链表表示的二叉树T，并用i和n来记录和
控制当前输入的结点个数
c.用InorderTraverse(T)遍历该二叉树
五.运行结果。
六.源程序。
#include<stdio.h>
#include <stdlib.h>
typedef struct tree{
char data;
struct tree *lchild;
struct tree *rchild;
}*Ptree,Dtree;
//先序创建二叉树
Ptree createTree()
{
char ch;
Ptree t;
ch=getchar();
if(ch=='#')
t=NULL;
else
{
t=(Ptree)malloc(sizeof(Dtree));
t->data=ch;
t->lchild=createTree();
t->rchild=createTree();
}
return t;
}
//定义队列
typedef struct queue_{
Ptree data[100];
int front,rear;
}Dqueue,*Pqueue;
//初始化队列
Pqueue initQueue()
{
Pqueue p;
p=(Pqueue)malloc(sizeof(Dqueue));
if(p)
{
p->front=0;
p->rear=0;
}
return p;
}
//判断队列是否为空
int emptyQueue(Pqueue p)
{
if(p->front==p->rear)
return 1;
else
return 0;
}
//入队
void inQueue(Pqueue p,Ptree t)
{
p->rear=(p->rear+1)%100;
p->data[p->rear]=t;
}
//出队
void outQueue(Pqueue p,Ptree* t)
{
p->front=(p->front+1)%100;
*t=p->data[p->front];
}
//层次遍历
void levelOrder(Ptree t)
{
Ptree p=t;
Pqueue Q;
if(p)
{
Q=initQueue();//初始化队列
printf("%c",p->data);
inQueue(Q,p);
while(!emptyQueue(Q))//当队列不为空
{
outQueue(Q,&p);//出队
if(p->lchild)
{
printf("%c",p->lchild->data);
inQueue(Q,p->lchild);//进队
}
if(p->rchild)
{
printf("%c",p->rchild->data);
inQueue(Q,p->rchild);//进队
}
}
}
}
//先序遍历
void preOrder(Ptree t)
{
if(t)
{
printf("%c",t->data);
preOrder(t->lchild);
preOrder(t->rchild);
}
}
//中序遍历
void inOrder(Ptree t)
{
if(t)
{
inOrder(t->lchild);
printf("%c",t->data);
inOrder(t->rchild);
}
}
//后序遍历
void postOrder(Ptree t)
{
if(t)
{
postOrder(t->lchild);
postOrder(t->rchild);
printf("%c",t->data);
}
}
//求叶子数
int leafCount(Ptree t)
{
int count1,count2;
if(t==NULL)
return 0;
else
{
if(t->lchild==NULL&&t->rchild==NULL)
return 1;
else
{
count1=leafCount(t->lchild);
count2=leafCount(t->rchild);
return count1+count2;
}
}
}
//求二叉树每层节点的个数,保存到数组num中void levelCount(Ptree t,int l,int num[])
{
if(t)
{
num[l]++;
levelCount(t->lchild,l+1,num);
levelCount(t->rchild,l+1,num);
}
}
//求二叉树的高度
int heightTree(Ptree t)
{
int h1,h2;
if(t==NULL)
return 0;
else
{
h1=heightTree(t->lchild);
h2=heightTree(t->rchild);
if(h1>h2)
return h1+1;
else
return h2+1;
}
}
//主函数
int main()
{
int num[10]={0};
int height;
int i;
Ptree t;
t=createTree();//先序创建二叉树
printf("后序遍历");//后续遍历
postOrder(t);
printf("\n");
printf("先序遍历");//先序遍历
preOrder(t);
printf("\n");
printf("层次遍历");//层次遍历
levelOrder(t);
printf("\n");
height=heightTree(t);//数的深度
printf("深度:%d\n",height);
levelCount(t,1,num);//每层节点数
for(i=1;i<=height;i++)
printf("第%d层个数:%d\n",i,num[i]);
printf("叶子总数:%d\n",leafCount(t));//叶子数return 0;
}。
