#include<stdio.h>
#include<process.h>
typedef struct bitree
{
char data;
struct bitree *left,*right;
}bitree,*BiTree;
typedef struct queue
{
BiTree data;
struct queue *next;
}*Queue;
typedef struct
{
Queue front;
Queue rear;
}Link;
int createtree(BiTree *T)
{
char c;
scanf("%c",&c);
if(c=='#')
(*T)=NULL;
else
{
(*T)=new bitree;
(*T)->data=c;
createtree(&((*T)->left));
createtree(&((*T)->right));
}return 1;
}
int InitQueue(Link *L)
{
L->front=L->rear=new queue;
if(!L->front)
printf("Error!\n"),exit(0);
else
L->front->next=NULL;
return 1;
}
int QueueEmpty(Link L)
{
if(L.front==L.rear)
return 0;
return 1;
}
void push(Link *L,BiTree B)
{
Queue p=new queue;
if(!p)
{
printf("error!\n");
}
p->data=B;
p->next=NULL;
L->rear->next=p;
L->rear=p;
}
BiTree pop(Link *L)
{
Queue q;
if(L->front==L->rear)
printf("Error!\n");
q=L->front->next;
L->front->next=q->next;
if(L->rear==q)
L->rear=L->front;
return q->data;
}
void countleaves(BiTree T,int *i)
{
if (T) {
if ((!T->left)&&(!T->right))
(*i)++;
countleaves(T->left,i);
countleaves(T->right,i);
}
}
void countall(BiTree T,int *i)
{
if(T!=NULL)
{
(*i)++;
countall(T->left,i);
countall(T->right,i);
}
}
int depth(BiTree T)
{
int a,b,c;
if(!T)
c=0;
else
{
a=depth(T->left);
b=depth(T->right);
c=1+(a>b?a:b);
}
return c;
}
void preorder(BiTree T)
{
if(T!=NULL)
{
printf("%c",T->data);
preorder(T->left);
preorder(T->right);
}
}
void inorder(BiTree T)
{
if(T!=NULL)
{
preorder(T->left);
printf("%c",T->data);
preorder(T->right);
}
}
void postorder(BiTree T)
{
if(T!=NULL)
{
preorder(T->left);
preorder(T->right);
printf("%c",T->data);
}
}
void layer(BiTree T)
{
Link L;
BiTree B;
InitQueue(&L);
if(T)
{
push(&L,T);
while(QueueEmpty(L))
{
B=pop(&L);
printf("%c",B->data);
if(B->left)
push(&L,B->left);
if(B->right)
push(&L,B->right);
}
}
}
void main()
{
BiTree T;
int a=0,b=0;
printf("请输入数据(以'#'表示不存在):\n");
if(!createtree(&T))
printf("创建失败!\n");
printf("层次遍历结果：\n");
layer(T);
printf("\n");
printf("先序遍历结果:\n");
preorder(T);
printf("\n");
printf("中序遍历结果:\n");
inorder(T);
printf("\n");
printf("后序遍历结果:\n");
postorder(T);
printf("\n");
printf("所求深度结果：\n");
printf("%d\n",depth(T));
printf("叶子节点个数：\n");
countleaves(T,&a);
printf("%d\n",a);
printf("全部节点个数：\n");
countall(T,&b);
printf("%d\n",b);
}
