实验三二叉树的基本运算
一、实验目的
1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容
[问题描述]
建立一棵二叉树，试编程实现二叉树的如下基本操作：
1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
3. 求二叉树的深度/结点数目/叶结点数目；(选做)
4. 将二叉树每个结点的左右子树交换位置。
（选做）
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），
[测试数据]
如输入：ABCффDEфGффFффф（其中ф表示空格字符）
则输出结果为
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
层序：ABCDEFG
[选作内容]
采用非递归算法实现二叉树遍历。
三、实验程序
#include <iostream>
#include <math.h>
using namespace std;
typedef char TElemType;
typedef struct BiTNode{ //定
义节点
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int DLRcreat(BiTree &T) //先序建立二叉树
{
char d;
cin>>d;
if(d=='#')T=NULL;
else
{
T=new BiTNode;
if(!T)exit(1);
T->data=d;
DLRcreat(T->lchild);
DLRcreat(T->rchild);
}
return 0;
}
int florder(BiTree T) //
层序遍历指针数组
{
BiTNode *Q[100]; //树节点指针数组，用于存放遍历到的元素地址
if(T==NULL)cout<<"空的二叉树"<<endl;
Q[0]=T; //存入树根
int i;
int j=1;
for(i=0;i<j;i++)
{
if(Q[i]->lchild!=NULL) //如果有左孩子，存入地址，j加一，否则没操作
{
Q[j]=Q[i]->lchild ;
j++;
}
if(Q[i]->rchild!=NULL) //如果有右孩子，存入地址，j加一，否则没操作
{
Q[j]=Q[i]->rchild ;
j++;
}
for(i=0;i<j;i++)cout<<" "<<Q[i]->data;
return 0;
}
int howmuch(BiTree T,int h)
{
BiTNode *Q[100]; //树节点指针数组，用于存放遍历到的元素地址
if(T==NULL)cout<<"空的二叉树"<<endl;
Q[0]=T; //存入树根
int i,k=0;
int j=1; //j-1为总节点
for(i=0;i<j;i++)
{
if(Q[i]->lchild!=NULL) //如果有左孩子，存入地址，j加一，否则没操作
{
Q[j]=Q[i]->lchild ;
j++;
if(Q[i]->rchild!=NULL) //如果
有右孩子，存入地址，j加一，否则没操作
{
Q[j]=Q[i]->rchild ;
j++;
}
if(Q[i]->lchild==NULL&&Q[i]->rchild==NULL)k++; //计算叶子数
}
i=ceil(log(j-1))+1; //计算深度
if(h==0)return j;
else if(h==1)return k;
else if(h==2)return i;
else {cout<<"参数错误";}
return 0;
}
int DLRorder(BiTree T) //先序遍历
{
if(T != NULL)
{
cout<<" "<<T->data; // 访问根结点
DLRorder(T->lchild); // 前序遍历左子树
DLRorder(T->rchild); // 前序遍历右子树
}
return 0;
}
int LDRorder(BiTree T) //中序遍历递归
{
if(T!=NULL)
{
LDRorder(T->lchild);
cout<<" "<<T->data;
LDRorder(T->rchild );
}
return 0;
}
int LRDorder(BiTree T)
//后序遍历递归
{
if(T!=NULL)
{
LDRorder(T->lchild);
LDRorder(T->rchild );
cout<<" "<<T->data;
}
return 0;
}
int exchang(BiTree &T) //交换左右子树
{
if(T != NULL)
{
if(T->lchild!=NULL&&T->rchild!=NULL)
//当有左右孩子时才交换
{
char t;
t=T->lchild->data;T->lchild->data=T->rchild->data;
T->rchild->data=t;
//交换数据
}
exchang(T->lchild);
// 递归调用
exchang(T->rchild);
}
return 0;
}
int choose(BiTree T) //功能选择
{
int a;cin>>a;
if(a==1){cout<<"先序遍历";DLRorder(T);}
else if(a==2){cout<<"中序遍历";LDRorder(T);}
else if(a==3){cout<<"后序遍历";LRDorder(T);}
else if(a==4){cout<<"层序遍历";florder(T);}
else if(a==5){cout<<"总节点数："<<howmuch(T,0);}
else if(a==6){cout<<"总叶子数："<<howmuch(T,1);}
else if(a==7){cout<<"树的深度："<<howmuch(T,2);}
else if(a==8){cout<<"交换前
"<<endl;florder(T);exchang(T);cout<<"交换后
";florder(T);}
else if(a==9)exit(1);
else cout<<"没有这个操作"<<endl;
cout<<endl<<"操作完成,请输入下一个操作"<<endl;
choose(T);
return 0;
}
int main() //主函数
{
cout<<"----------------二叉树的基本操作
----------------"<<endl;
cout<<"请先建立二叉树，按先序的方式输入如果数据为空
输入#"<<endl;
BiTree T; //定义二叉树，初始化
DLRcreat(T);
cout<<"1.先序遍历二叉树 2.中序遍历二
叉树"<<endl;
cout<<"3.后序遍历二叉树 4.层序遍历二
叉树"<<endl;
cout<<"5.求总节点数 6.求叶子总数
"<<endl;
cout<<"7.深度-完全二叉树有效 8.左右子树交换"<<endl;
cout<<"9.退出"<<endl;
choose(T);
return 0;
}
四、实验过程及结果截图。