#include<stdio.h>
#include<stdlib.h>
#define SIZE 50
int numberOfLeaves=0;
int numberOfNodes=0;
int depth=0;
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct{
BiTNode *base;
int front;
int rear;
int length;
}Queue,*PQueue;
typedef enum{Visit , Travel}TaskType;
typedef struct{
BiTree ptr; // 指向根结点的指针
TaskType task; // 任务性质
}ElemType;
typedef struct{
ElemType *base;
ElemType *top;
int length;
}Stack,*PStack;
//队列操作
void init_Q(Queue &Q);
void En_Q(Queue &Q,BiTree T);
void De_Q(Queue &Q,BiTree &T);
//树操作
void CreateBiTree(BiTree &T);
void PreOrderTraverse(BiTree T);//递归先序遍历
void InOrderTraverse(BiTree T);//递归中序遍历
void PostOrderTraverse(BiTree T);//递归后序遍历
void LevelOrderTraverse(BiTree T);//层次遍历
void PreOrder_iter(BiTree BT); //非递归先序遍历
void InOrder_iter( BiTree BT );//非递归中序遍历
void PostOrder_iter( BiTree BT );//非递归后序遍历
void GetLeaves(BiTree T);
void GetNumberOfNodes(BiTree T);
int GetDepth(BiTree T);
int max(int a,int b);
//栈操作
void init(Stack &S);
void Push(Stack &S,ElemType e);
void Pop(Stack &S,ElemType &e);
int StackEmpty(Stack S);
int GetTop(Stack S,ElemType &p);
void main(){
int select=1;
BiTree T=NULL;
while(1){
printf("请选择要执行的操作:\n");
printf("1.创建二叉树\n");
printf("2.二叉树的递归遍历算法（前、中、后）\n");
printf("3.二叉树的非递归遍历算法 （前、中、后）\n");
printf("4.二叉树的层次遍历算法\n");
printf("0.退出\n");
scanf("%d",&select);
getchar();
switch(select){
case 0:return;
case 1:printf("请输入二叉树:\n");
CreateBiTree(T);
break;
case 2:printf("\n先序遍历:\n");
PreOrderTraverse(T);
printf("\n中序遍历:\n");
InOrderTraverse(T);
printf("\n后序遍历:\n");
PostOrderTraverse(T);
break;
case 3:printf("\n非递归先序遍历:\n");
PreOrder_iter(T);
printf("\n非递归中序遍历:\n");
InOrder_iter(T);
printf("\n非递归后序遍历:\n");
PostOrder_iter(T);
break;
case 4:printf("\n层序遍历:\n");
LevelOrderTraverse(T);
break;
default:printf("请确认选择项:\n");
}
}
}
void CreateBiTree(BiTree &T){
char ch=getchar();
if(ch==' ') T=NULL;
else{
if(!(T=new BiTNode)) exit(1);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){
if(T){
putchar(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
putchar(T->data);
InOrderTraverse( T->rchild);
}
}
void PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse( T->rchild);
putchar(T->data);
}
}
void init_Q(Queue &Q){
Q.base=new BiTNode[SIZE];
Q.front=Q.rear=0;
Q.length=0;
}
void En_Q(Queue &Q,BiTree T){
if(Q.length==SIZE){
printf("FULL!\n");
return;
}
Q.base[Q.rear]=*T;
Q.rear=(Q.rear+1)%SIZE;
Q.length++;
}
void De_Q(Queue &Q,BiTree &T){
if(Q.length==0){
printf("EMPTY!\n");
return;
}
T=&(Q.base[Q.front]);
Q.front=(Q.front+1)%SIZE;
Q.length--;
}
void LevelOrderTraverse(BiTree T){
Queue Q;
init_Q(Q);
if(T){
En_Q(Q,T);
}
while(Q.front!=Q.rear){
BiTree temp;
De_Q(Q,temp);
putchar(temp->data);
if(temp->lchild) En_Q(Q,temp->lchild);
if(temp->rchild) En_Q(Q,temp->rchild);
}
}
int max(int a,int b){
return a>=b?a:b;
}
int GetDepth(BiTree T){
int ldepth=0,rdepth=0;
if(!T) depth=0;
else{
ldepth=GetDepth(T->lchild);
rdepth=GetDepth(T->rchild);
depth=1+max(ldepth,rdepth);
}
return depth;
}
void init(Stack &S){
S.base=new ElemType[SIZE];
S.top=S.base;
S.length=0;
}
void Push(Stack &S,ElemType e){
*S.top++=e;
S.length++;
}
void Pop(Stack &S,ElemType &e){
e=*(--S.top);
S.length--;
}
int StackEmpty(Stack S){
if(S.length>0)return 0;
else return 1;
}
int GetTop(Stack S,ElemType &e){
if(S.length!=0) {
e=*(S.top-1);
return 1;
}
else return 0;
}
void PreOrder_iter(BiTree BT){
Stack S;
init(S);
ElemType e;
e.ptr=BT;
e.task=Travel;
if(BT){
Push(S,e);
}
while(!StackEmpty(S)){
Pop(S,e);
if(e.task==Visit) {
printf("%c",e.ptr->data);
}
else{
if(e.ptr){
BiTree p;
p=e.ptr;
e.ptr=p->rchild;
Push(S,e);
e.ptr=p->lchild;
Push(S,e);
e.ptr=p;
e.task=Visit;
Push(S,e);
}
}
}
}
void InOrder_iter( BiTree BT ) {
Stack S;
init(S);
ElemType e;
e.ptr=BT; e.task=Travel;
if(BT) Push(S,e);// 布置初始任务
while(!StackEmpty(S)){
Pop(S,e); // 每次处理一项任务
if (e.task==Visit) printf("%c",e.ptr->data);
else{
if(e.ptr){// 处理非空树的遍历任务
BiTree p;
p=e.ptr;
e.ptr=p->rchild;
Push(S,e);// 遍历右子树
e.ptr=p;
e.task=Visit;
Push(S,e); // 访问根结点
e.ptr=p->lchild;
e.task=Travel;
Push(S,e);//遍历左子树
}
}//else
} //while
}//InOrder_iter
void PostOrder_iter( BiTree BT ) {
Stack S;
init(S);
ElemType e;
e.ptr=BT;
e.task=Travel;
if(BT) Push(S, e);// 布置初始任务
while(!StackEmpty(S)){
Pop(S,e);
if (e.task==Visit) printf("%c",e.ptr->data);
else{
if(e.ptr){
BiTree p;
p=e.ptr;
e.task=Visit;
Push(S,e); // 访问根结点
p=e.ptr;
e.task=Travel;
e.ptr=p->rchild;
Push(S,e); // 遍历右子树
e.ptr=p->lchild;
Push(S,e); // 遍历左子树
}
}//else
} //while
}//PostOrder_iter