#include <stdio.h>
typedef struct bitree
{
char data;
struct bitree *lchild,*rchild;
}bitree;/*树的节点的定义*/

bitree* creatree(bitree *root)
/*根据指针root创建一颗二叉树*/
{char ch;
scanf("%c",&ch);
if (ch=='@')root = NULL;
else
{if (!(root=(bitree*)malloc(sizeof(bitree)))) exit();
root->data=ch;/*printf("%c",root->data);*/
root->lchild=creatree(root->lchild);
root->rchild=creatree(root->rchild);
}
return root;
}

/*******************************************/
/* 按照层次遍历二叉树 */
/*******************************************/

preorder(bitree *root)
{if(root!=NULL)
{printf("%c",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}

/*******************************************/
/* 按照中序遍历二叉树 */
/*******************************************/

inorder(bitree *root)
{if(root!=NULL)
{inorder(root->lchild);
printf("%c",root->data);
inorder(root->rchild);
}
}

/*******************************************/
/* 按照后序遍历二叉树 */
/*******************************************/

postorder(bitree *root)
{if(root!=NULL)
{postorder(root->lchild);
postorder(root->rchild);
printf("%c",root->data);
}
}

/*******************************************/
/* 递归法求树的深度 */
/*******************************************/

int hightree(bitree *root)
{int n,t,t1,t2;
if(root==NULL)n=0;
else{t1=hightree(root->lchild);
t2=hightree(root->rchild);
t=t1>t2?t1:t2;
n=t+1;
}
return n;
}

typedef struct { /*二叉树结点队列*/
bitree *data[30];
int front;
int rear;
}queue;

/*******************************************/
/* 按照层次遍历二叉树 */
/*******************************************/
void Levelorder(bitree *t)
{
queue q;
q.data[0]=t;
q.front=0;q.rear=1;
while(q.front<q.rear)
{
if(q.data[q.front])
{
printf("%c",q.data[q.front]->data);
q.data[q.rear++]=q.data[q.front]->lchild;
q.data[q.rear++]=q.data[q.front]->rchild;
q.front++;
}
else
{
q.front++;
}
}
printf("\n\n");
}

main()
{bitree *root;
/* Equeue Q, *S=Q;*/
int choice;
printf("please input a bitree:\n");
root=creatree(root);
while(1)
{printf("**************\n");
printf("*1->xianxu****\n");
printf("*2->zhongxu***\n");
printf("*3->houxu*****\n");
printf("*4->shendu****\n");
printf("*5->cengci****\n");
printf("*else->exit***\n");
printf("**************\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("xian xu shi:"); preorder(root); printf("\n"); break;
case 2: printf("zhong xu shi:");inorder(root); printf("\n"); break;
case 3: printf("hou xu shi:");postorder(root);printf("\n"); break;
case 4: printf("The height of tree is %d.\n",hightree(root)); break;
case 5: printf("cengci bianli shi:"); Levelorder(root); break;
default: exit(); break;
}
}
}