#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"
#include "math.h"
#define NULL 0
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T){ //建立二叉链表
char ch;
ch=getchar();
if(ch==' ')
T=NULL;
else {
if(!(T=(BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch; //将输入的数值赋给根结点
CreateBiTree(T->lchild); //构造左子树
CreateBiTree(T->rchild); //构造右子树
}
return OK;
}
Status ExchangeBitree(BiTree &T){ //交换二叉树的左右子树
BiTree t;
if(T==NULL)
return OK;
else {
t=T->lchild;
T->lchild=T->rchild;
T->rchild=t;
ExchangeBitree(T->lchild);
ExchangeBitree(T->rchild);
return OK;
}
}
Status PreOrderTraverse(BiTree &T){ //先序遍历二叉树
if(T==NULL) //二叉树空,返回
return OK;
else {
cout<<T->data<<' '; //输出根结点
PreOrderTraverse(T->lchild); //递归遍历访问左子树
PreOrderTraverse(T->rchild); //递归遍历访问右子树
return OK;
}
}
Status InOrderTraverse(BiTree &T){ //中序遍历二叉树
if(T==NULL) //二叉树空,返回
return OK;
else {
InOrderTraverse(T->lchild); //递归遍历访问左子树
cout<<T->data<<' '; //输出根结点
InOrderTraverse(T->rchild); //递归遍历访问右子树
return OK;
}
}
Status PostOrderTraverse(BiTree &T){ //后序遍历二叉树
if(T==NULL) //二叉树空,返回
return OK;
else {
PostOrderTraverse(T->lchild); //递归遍历访问左子树
PostOrderTraverse(T->rchild); //递归遍历访问右子树
cout<<T->data<<' '; //输出根结点
return OK;
}
}
Status NodeCount(BiTree T){ //统计二叉树的结点个数
if(T==NULL) //如果是空树,返回0
return 0;
else //否则访问左右子树,并求得结点总数,最后加1,即根结点
return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
}
Status LeafNodeCount(BiTree &T){ //统计叶结点个数
if(T==NULL) //如果二叉树为空,返回0
return 0;
else if((T->lchild==NULL)&&(T->rchild==NULL)) //如果为叶子结点,返回1
return 1;
else
return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);//叶子结点树为左子树与右子树叶子数之和
}
Status DepthBiTree(BiTree &T){ //计算二叉树的深度
int m,n;
if(T==NULL) //如果二叉树为空,则深度为0
return 0;
else {
m=DepthBiTree(T->lchild)+1;
n=DepthBiTree(T->rchild)+1;
}
return (m>n?m:n);
}
Status DblOrderTraverse(BiTree &T){ //双序遍历二叉树
if(T==NULL)
return OK;
else {
cout<<T->data;
DblOrderTraverse(T->lchild);
cout<<T->data;
DblOrderTraverse(T->rchild);
return OK;
}
}
int main(int argc, char* argv[])
{
BiTree T;
int a;
char c;
cout<<"\t^_^您好!\n\t请按照先序顺序输入一棵字母二叉树"<<endl;
CreateBiTree(T);
cout<<"请选择操作:";
cout<<"\t1.返回先序遍历结果"<<endl;
cout<<"\t\t2.返回中序遍历结果"<<endl;
cout<<"\t\t3.返回后序遍历结果"<<endl;
cout<<"\t\t4.求取二叉树结点总数"<<endl;
cout<<"\t\t5.求取二叉树叶子结点总数"<<endl;
cout<<"\t\t6.求取二叉S树深度"<<endl;
cout<<"\t\t7.交换二叉树的左右子树"<<endl;
cout<<"\t\t8.双序访问二叉树的左右子树"<<endl;
do{
cout<<"操作";
cin>>a;
switch(a){
case 1: cout<<"先序遍历的结果为:\t";
PreOrderTraverse(T);
break;
case 2: cout<<"中序遍历的结果为:\t";
InOrderTraverse(T);
break;
case 3: cout<<"后序遍历的结果为:\t";
PostOrderTraverse(T);
break;
case 4: cout<<"二叉树的结点总数为: ";
cout<<NodeCount(T);
break;
case 5: cout<<"二叉树的叶子结点总数为: ";
cout<<LeafNodeCount(T);
break;
case 6: cout<<"二叉树的深度为: ";
cout<<DepthBiTree(T);
break;
case 7: ExchangeBitree(T);
cout<<"交换后前序遍历:\t";
PreOrderTraverse(T);
cout<<endl<<"交换后中序遍历:\t";
InOrderTraverse(T);
cout<<endl<<"交换后后序遍历:\t";
PostOrderTraverse(T);