// Tree.cpp : 定义控制台应用程序的入口点。
//

#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>
#define QueueMaxSize 20
#define StackMaxsize 10
typedef char ElemType;
struct BTreeNode {
ElemType data;
struct BTreeNode* left;
struct BTreeNode* right;
};

/*初始化二叉树*/
void InitBTree(struct BTreeNode** BT)
{
*BT=NULL;
}
/*建立二叉树*/
void CreateBTree(struct BTreeNode** BT, char* a)
{
struct BTreeNode* p;
struct BTreeNode* s[StackMaxsize];
int top=-1;
int k;
int i=0;
*BT=NULL;
while (a[i])
{
switch(a[i]){
case ' ':
    break;
case '(':
if(top==StackMaxsize-1){
printf("占空间太小,需增加StackMaxSize!\n");
exit(1);
}
top++;s[top]=p;k=1;
break;
case ')':
if(top==-1){
printf("二叉树广义表字符串错!\n");
exit(1);
}
top--;break;
case ',':
   k=2;break;
default:
  // p=malloc(sizeof(struct BTreeNode));      
  p=(BTreeNode *)malloc(sizeof(BTreeNode));
   p->data=a[i];p->left=p->right=NULL;
  if(*BT==NULL) *BT=p;
  else{
  if(k==1) s[top]->left=p;
  else s[top]->right=p;
}
}
 i++;
}
}
/*输出二叉树*/
void PrintBTree(struct BTreeNode* BT)
{
if(BT!=NULL){
  printf("&c",BT->data);
if(BT->left!=NULL||BT->right!=NULL)
{
  printf("(");
  PrintBTree(BT->left);
 if(BT->right!=NULL) printf(",");
 PrintBTree(BT->right);
 printf(")");
}
}
}
/*前序遍历*/
void Preorder(struct BTreeNode* BT)
{
  if(BT!=NULL) {
 printf("%c",BT->data);
Preorder(BT->left);
Preorder(BT->right);
}
}
/*中序遍历*/
void Inorder(struct BTreeNode* BT)
{
if(BT!=NULL){
 Inorder(BT->left);
 printf("%c",BT->data);
 Inorder(BT->right);
}
}
/*后序遍历*/
void Postorder(struct BTreeNode* BT)
{
if(BT!=NULL){
 Inorder(BT->left);
 Inorder(BT->right);
 printf("%c",BT->data);
}
}
/*按层遍历*/
void Levelorder(struct BTreeNode* BT)
{
 struct BTreeNode* p;
 struct BTreeNode* q[QueueMaxSize];
 int front=0,rear=0;
 if(BT!=NULL)
 {
 rear=(rear+1)%QueueMaxSize;
 q[rear]=BT;
}
while (front!=rear)
{
 front=(front+1)%QueueMaxSize;
 p=q[front];
 printf("%c",p->data);
 if(p->left!=NULL)
 {
 rear=(rear+1)%QueueMaxSize;
 q[rear]=p->left;
 if(p->right!=NULL)
 {
 rear=(rear+1)%QueueMaxSize;
 q[rear]=p->right;
}
}
}
}

/*求二叉树的深度*/
int BTreeDepth(struct BTreeNode* BT)
{
 if(BT==NULL)
   return 0;
 else 
 {
 int dep1=BTreeDepth(BT->left);
 int dep2=BTreeDepth(BT->right);
 if(dep1>dep2)
   return dep1+1;
 else
   return dep2+1;
}
}
void Count(BTreeNode* BT,int& C1,int& C2)
        //分别统计出二叉树中所有结点数和叶子结点数
        {
         if(BT!=NULL){
         C1++;//统计所有结点
         if(BT->left==NULL&&BT->right==NULL)
         C2++;  //统计叶子结点数
         Count(BT->left,C1,C2);
         Count(BT->right,C1,C2);
         }
       }

void main()
{
struct BTreeNode* bt;
char b[50];
ElemType x,*px;
InitBTree(&bt);
printf("输入二叉树广义表字符串:\n");
scanf("%s",b);
CreateBTree(&bt,b);
PrintBTree(bt);
printf("\n");
printf("前序:");
Preorder(bt);printf("\n");
printf("中序:");
Inorder(bt);printf("\n");
printf("后序:");
Postorder(bt);printf("\n");
printf("按层:");
Levelorder(bt);printf("\n");
printf("二叉树的深度:");
printf("%d\n",BTreeDepth(bt));
printf("统计所有节点数及叶子节点数:");
printf("%d,%d,%d\n",Count(bt,bt,bt));
ClearBTree(&bt);
}