树的存储与遍历操作实验报告.doc

实验五 树的存储与遍历操作

班级：1301203 姓名：向怡 学号：2012214327 日期：2013.11.26

一、实验内容：
1、 写出一个算法建立一棵二叉树并且完成对这棵二叉树的先序遍历、中序遍历和后序遍历。
2、 利用树的遍历求二叉树的结点数
3、 利用树的遍历求二叉树的叶子数
二、实验目的：
通过这个实验，学会对树的定义，对树的存储方法，遍历的基本操作有一个清楚的认识。并且能够用程序模拟树的遍历过程。
三、 概要设计：
3.1 建立一棵二叉树并且完成对这棵二叉树的先序遍历、中序遍历和后序遍历
3.2利用树的遍历求二叉树的节点数（叶子数）
四、代码设计：
#include
using namespace std;

typedef char DataType;
const int SIZE=50;
struct BiNode
{
DataType data;
BiNode *lchild,*rchild;
};

class BiTree
{
public:
BiTree()
{
cout<<"请依次输入前序的扩展二叉数，‘#’表示空"<endl;
}
~BiTree()
{
Release(root);
}
void PreOrder()//前序遍历
{
PreOrder(root);
}
void InOrder()//中序
{
InOrder(root);
}
void PostOrder()//后序
{
PostOrder(root);
}
void LeverOrder()//层序遍历
{
front=rear=-1;//初始化栈指针
if(root==NULL)return;
Q[++rear]=root;
while (front!=rear)
{
q=Q[++front];//出队
cout<data;
if (q->lchild!=NULL)
{
Q[++rear]=q->lchild;
}
if (q->rchild!=NULL)
{
Q[++rear]=q->rchild;
}
}
cout<
cout<<"叶子数"<>ch;
if (ch=='#')
{
bt=NULL;
}else{
bt=new BiNode;
bt->data=ch;
bt->lchild=Creat(bt->lchild);//递归建立左子树
bt->rchild=Creat(bt->rchild);//递归建立右子树
}
return bt;
}
void Release(BiNode *bt)//析构函数调用
{
if (bt!=NULL)
{
Release(bt->lchild);
Release(bt->rchild);
delete bt;
}
}
void PreOrder(BiNode *bt)//前序(DLR)
{
if bt==NULL){return;}
else{
cout<data<<" ";
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
void InOrder(BiNode *bt)//中序(LDR)
{
if(bt==NULL){return;}
else{
InOrder(bt->lchild);
cout<data<<" ";
InOrder(bt->rchild);
}
}
void PostOrder(BiNode *bt)//后序(LRD)
{
if(bt==NULL){return;}
else{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout<data<<" ";
}
}
void Count(BiNode *bt,int &nCount,int &lCount)//计算叶子数和结点数（即求二叉树的所有结点中左、右子树均为不为空的结点个数之和）
{
if (bt!=NULL)
{
if (bt->lchild==NULL&&bt->rchild==NULL)
{
lCount++;
return;
}else
{
nCount++;
}
Count(bt->lchild,nCount,lCount);
Count(bt->rchild,nCount,lCount);
}
}
};

int main()
{
BiTree a;
int index;
do
{
cout<<"**********************************"<<<"2、中序遍历二叉树"<>index;
if(index==5){return 0;}

switch(index)
{
case 1:
a.PreOrder();
cout<<"遍历完成"<a.InOrder();
cout<<"遍历完成"<