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

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

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

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

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

class BiTree
{
public:
BiTree()
{
cout<<"请依次输入前序的扩展二叉数，‘#’表示空"<<endl;
root=Creat(root);
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<<q->data;
if (q->lchild!=NULL)
{
Q[++rear]=q->lchild;
}
if (q->rchild!=NULL)
{
Q[++rear]=q->rchild;
}
}
cout<<endl;
}
void Count()//计算叶子和结点数
{
int lCount=0,nCount=0;
Count(root,nCount,lCount);
cout<<"叶子数"<<lCount<<"结点数"<<nCount<<endl;
}
private:
int front,rear;
BiNode *root,*q,*Q[SIZE];//指向根结点的头指针,Q是存放指针的数组
BiNode *Creat(BiNode *bt)//构造函数调用(指针函数)，前序构造二叉树
{
char ch;
cout<<"请输入数据"<<endl;
cin>>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<<bt->data<<" ";
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
void InOrder(BiNode *bt)//中序(LDR)
{
if(bt==NULL){return;}
else{
InOrder(bt->lchild);
cout<<bt->data<<" ";
InOrder(bt->rchild);
}
}
void PostOrder(BiNode *bt)//后序(LRD)
{
if(bt==NULL){return;}
else{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout<<bt->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<<"**********************************"<<endl;
cout<<"1、前序遍历二叉树"<<endl;
cout<<"2、中序遍历二叉树"<<endl;
cout<<"3、后序遍历二叉树"<<endl;
cout<<"4、计算叶子树和结点数"<<endl;
cout<<"5、退出"<<endl;
cout<<"**********************************"<<endl;
cin>>index;
if(index==5){return 0;}

switch(index)
{
case 1:
a.PreOrder();
cout<<"遍历完成"<<endl;
break;
case 2:
a.InOrder();
cout<<"遍历完成"<<endl;
break;
case 3:
a.PostOrder();
cout<<"遍历完成"<<endl;
break;
case 4:
a.Count();
break;
default:
cout<<"输入错误"<<endl;
break;
}
}while(index);
return 0;
}
四、 测试结果：

前序构造二叉树

主界面

前序遍历

中序遍历

后序遍历

计算叶子数和结点数

程序退出