#include <iostream.h>
#include <malloc.h>
#include <iomanip.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define length 50
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &BT) //先序次序输入二叉树中节点的值，空格表示空树
{
char ch;
cin>>ch;
if (ch== '/') BT=NULL;
else
{
BT=(BiTNode *)malloc(sizeof(BiTNode)); //构造新结点
BT->data=ch;
CreateBiTree(BT->lchild); //构造左子树
CreateBiTree(BT->rchild); //构造右子树
}
return OK;
}
//先序遍历
void PreTraverse(BiTree BT)
{
if(BT!=NULL)
{
cout<<BT->data;
PreTraverse(BT->lchild);
PreTraverse(BT->rchild);
}
}
// 中序遍历
void InTraverse(BiTree BT){
if (BT!=NULL){
InTraverse(BT->lchild);
cout<<BT->data;
InTraverse(BT->rchild);
}
}
//后序遍历
void LastTraverse(BiTree BT){
if (BT!=NULL){
LastTraverse(BT->lchild);
LastTraverse(BT->rchild);
cout<<BT->data;
}
}
//层次遍历
void LevelTraverse(BiTree BT){
BiTree array[length],pos;
int front,end; //头尾指针
array[1]=BT;
front=end=1;
while (front<=end){ //出队
pos=array[front];
front++;
cout<<pos->data<<" ";
if(pos->lchild!=NULL)
{
end++;
array[end]=pos->lchild;
}
if(pos->rchild!=NULL)
{
end++;
array[end]=pos->rchild;
}
}
}

//计算节点数目
void Node(BiTree BT,int *count1){
if(BT){
(*count1)++;
Node(BT->lchild,count1);
Node(BT->rchild,count1);
}
}
//计算叶子节点数目
void Leaf(BiTree BT,int *count2)
{
if (BT)
{
Leaf(BT->lchild,count2);
if (BT->lchild==NULL && BT->rchild==NULL)
(*count2)++;
Leaf(BT->rchild,count2);
}
}
//计算二叉树的高度，其中h1和h2分别是以BT为根的左右子树的高度
int hight(BiTree BT)
{
int h1=0,h2=0;
if (BT==NULL)
return ERROR;
else
{
h1=hight(BT->lchild);
h2=hight(BT->rchild);
if(h1<h2)
{
int c=h1;
h1=h2;
h2=c;
}
h1++;
}
return h1;
}
//交换左右二叉数
void Change_Left_Right(BiTree BT)
{
if(BT)
{
Change_Left_Right(BT->lchild);
Change_Left_Right(BT->rchild);
BiTree k=BT->lchild;
BT->lchild=BT->rchild;
BT->rchild=k;
}
}
void main()
{
int x=0;
int count1=0,count2=0;
BiTree BT;
cout<<"please input the value of node"<<endl;
CreateBiTree(BT);
if(BT==NULL)
cout<<"The BiTree is Empty."<<endl;
else{
cout<<"先序遍历为"<<endl;
PreTraverse(BT);
cout<<endl;

cout<<"中序遍历为"<<endl;
InTraverse(BT);
cout<<endl;

cout<<"后序遍历为"<<endl;
LastTraverse(BT);
cout<<endl;

cout<<"层次遍历为:"<<endl;
LevelTraverse(BT);
cout<<endl;

//交换左右二叉数
Change_Left_Right(BT);
cout<<"交换左右二叉数后先序遍历为"<<endl;
cout<<BT->data;
PreTraverse(BT->lchild);
PreTraverse(BT->rchild);

Node(BT,&count1);
cout<<"节点个数为："<<count1<<endl;

Leaf(BT,&count2);
cout<<"叶子结点个数:"<<count2<<endl;

cout<<"二叉树高度:"<<hight(BT)<<endl;

}
}