#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
typedef char ElemType;
struct BTreeNode{
  ElemType data;
  BTreeNode* left;
  BTreeNode* right;
};
#include "test9_stack.h"
#include "test10.h"
void main()
{
  BTreeNode* bt;
  InitBTree(bt);
  char b[50];
  cout<<"输入二叉树用广义表表示的字符串:"<<endl;
  cin.getline(b,sizeof(b));
  CreateBTree(bt,b);
  PrintBTree(bt);
  cout<<endl;
  cout<<"前序：";
  PreOrder(bt);
  cout<<endl;
  cout<<"中序：";
  InOrder(bt);
  cout<<endl;
  cout<<"中序（非递归算法）:";
  InOrder_fdg(bt);
  cout<<endl;
  cout<<"后序：";
  PostOrder(bt);
  cout<<endl;
  cout<<"按层：";
  LevelOrder(bt);
  cout<<endl;
  ElemType x;
  cout<<"输入一个待查字符："<<endl;
  cin>>x;
  if(FindBTree(bt,x))
    cout<<"查找字符"<<x<<"成功!"<<endl;
  else
    cout<<"查找字符"<<x<<"失败!"<<endl;
  cout<<"深度：";
  cout<<DepthBTree(bt)<<endl;
  if(ChangeBTree(bt)){
    printf("将二叉树中的所有结点的左右子树进行交换后: \n");
    PrintBTree(bt);
    cout<<endl;
  }
  printf("二叉树中的结点总数: %d \n",CountBTree(bt));
  BTreeNode* newbt;
  newbt=CopyBTree(bt);
  printf("复制二叉树得新二叉树：\n");
  PrintBTree(newbt);
  ClearBTree(bt);
  ClearBTree(newbt);
}

void PreOrder(BTreeNode* BT)
{
  if(BT!=NULL){
    cout<<BT->data<<' ';
    PreOrder(BT->left);
    PreOrder(BT->right);
  }
}

void InOrder(BTreeNode* BT)
{
  if(BT!=NULL){
    InOrder(BT->left);
    cout<<BT->data<<' ';
    InOrder(BT->right);
  }
}

void PostOrder(BTreeNode* BT)
{
  if(BT!=NULL){
    PostOrder(BT->left);
    PostOrder(BT->right);
    cout<<BT->data<<' ';
  }
}

void InitBTree(BTreeNode*& BT)
{
  BT=NULL;
}

void CreateBTree(BTreeNode*& BT,char *a)
{
  const int MaxSize=10;
  BTreeNode*s[MaxSize];
  int top=-1;
  BT=NULL;
  BTreeNode *p;
  int k;
  int i=0;
  while(a[i])
  {
    switch(a[i]){
        case ' ':
        break;
        case '(':
        if(top==MaxSize-1){
          cout<<"stack space needs increase!"<<endl;
          exit(1);
        }
        top++;
        s[top]=p;
        k=1;
        break;
      case ')':
        if(top==-1){
          cout<<"二叉树广义表字符串错！"<<endl;
          exit(1);
        }
        top--;
        break;
      case ',':
        k=2;
        break;
      default:
        p=new 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++;
  }
}

bool EmptyBTree(BTreeNode *BT)
{
  return BT==NULL;
}

int DepthBTree(BTreeNode *BT)
{
  if(BT==NULL)
    return 0;
  else{
    int dep1=DepthBTree(BT->left);
    int dep2=DepthBTree(BT->right);
    if(dep1>dep2)
      return dep1+1;
    else
      return dep2+1;
  }
}

bool FindBTree(BTreeNode *BT,ElemType &x)
{
  if(BT==NULL)
    return false;
  else{
    if(BT->data==x){
      x=BT->data;
      return true;
    }
    else{
      if(FindBTree(BT->left,x))
        return true;
      if(FindBTree(BT->right,x))
        return true;
      return false;
    }
  }
}

void PrintBTree(BTreeNode *BT)
{
  if(BT!=NULL){
    cout<<BT->data;
    if(BT->left!=NULL||BT->right!=NULL){
      cout<<'(';
      PrintBTree(BT->left);
      if(BT->right!=NULL)
        cout<<',';
      PrintBTree(BT->right);
      cout<<')';
    }
  }
}

void ClearBTree(BTreeNode *&BT)
{
  if(BT!=NULL){
    ClearBTree(BT->left);
    ClearBTree(BT->right);
    delete BT;
    BT=NULL;
  }
}

void LevelOrder(BTreeNode* BT)
{
  const int MaxSize=30;
  BTreeNode* q[MaxSize];
  int front=0,rear=0;
  BTreeNode* p;
  if(BT!=NULL){
    rear=(rear+1)%MaxSize;
    q[rear]=BT;
  }
  while(front!=rear){
    front=(front+1)%MaxSize;
    p=q[front];
    cout<<p->data<<' ';
    if(p->left!=NULL){
      rear=(rear+1)%MaxSize;
      q[rear]=p->left;
    }
    if(p->right!=NULL){
      rear=(rear+1)%MaxSize;
      q[rear]=p->right;
    }
  }
}


void InOrder_fdg(BTreeNode* T)
{
  Stack S;
  BTreeNode* p=T;
  InitStack(S);
  while(p!=NULL||!EmptyStack(S)){
    if(p!=NULL){
      Push(S,p);
      p=p->left;
    }
    else{
      p=Pop(S);
      cout<<p->data<<' ';
      p=p->right;
    }
  }
  ClearStack(S);
}

int ChangeBTree(BTreeNode *BT)
{
  BTreeNode* t;
  if(BT==NULL||(BT->left==NULL && BT->right==NULL))
    return 0;
  t=BT->left;
  BT->left=BT->right;
  BT->right=t;
  ChangeBTree(BT->left);
  ChangeBTree(BT->right);
  return 1;
}

int CountBTree(BTreeNode *BT)
{      
  int static count;
  if(BT!=NULL){
    count++;
    CountBTree(BT->left);
    CountBTree(BT->right);
  }
  return count;
}

BTreeNode * CopyBTree(BTreeNode *BT)
{

    if(BT==NULL) return NULL;
    else {
        BTreeNode* pt=new BTreeNode;  
        pt->data=BT->data;
        pt->left=CopyBTree(BT->left);
        pt->right=CopyBTree(BT->right);
        return pt;
    }
}

struct Stack{
    BTreeNode* *stack;    // 存栈元素
    int  top;                // 栈顶指示器
    int MaxSize;            // 栈的最大长度
};
void InitStack (Stack &S)    //构造一个空栈 S
{
  S.MaxSize=10;
  S.stack=new BTreeNode*[S.MaxSize];
  if(!S.stack){
    cerr<<"fail"<<endl;
    exit(1);
  }
  S.top=-1;
}

int EmptyStack (Stack S)   //若栈S为空栈返回1，否则返回0
{
  return S.top==-1;
}

void Push(Stack &S, BTreeNode* item)   //元素 item进栈
{
  if(S.top==S.MaxSize-1){
    int k=sizeof(BTreeNode*);
    S.stack=(BTreeNode**)realloc(S.stack,2*S.MaxSize*k);
    S.MaxSize=2*S.MaxSize;
  }
  S.top++;
  S.stack[S.top]=item;
}

BTreeNode* Pop(Stack &S)    //栈S的栈顶元素出栈并返回
{
  if(S.top==-1){
    cerr<<"Stack is empty!"<<endl;
    exit(1);
  }
  S.top--;
  return S.stack[S.top+1];
}

BTreeNode* Peek(Stack S)   //取栈S的当前栈顶元素并返回
{
  if(S.top==-1){
    cerr<<"Stack is empty!"<<endl;
    exit(1);
  }
  return S.stack[S.top];
}

void ClearStack (Stack &S)   //清除栈s，使成为空栈
{
  if(S.stack){
    delete []S.stack;
    S.stack=0;
  }
  S.top=-1;
  S.MaxSize=0;
}