//  binary tree

//  Last Modified: 2008-06-16

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct data
{
  int index;
  int key;
} data;


typedef struct node
{
  struct node *left;
  data datas;
  struct node *right;
} node, *tree;

int global_index = 0;
int nodes = 0;


void ergod(node *t);
void insert(tree t, char *msg);

void insert(tree t, char *msg)
{
  int i;
  extern int global_index;

  global_index++;

  printf("\n");
  printf("\n %s node %d: ", msg, global_index);

  printf("\n");
  printf("\n data: ");
  getchar();
  i = getchar();
  if (i != '#')
  {
    t = (node *)malloc(sizeof(node));
    if (t == NULL)
      printf("\n overflow ");

    t->datas.index = global_index;
    t->datas.key = i;

    insert(t->left, "left");
    insert(t->right, "right");
  }
  else
  {
    global_index--;
    //  depth--;
    t = NULL;
  }
}


void ergod(node *t)
{
  extern int global_index;

  if (global_index > 1 && t != NULL)
  {
    printf("\n %d -> %c ", t->datas.index, t->datas.key);
    ergod(t->left);
    ergod(t->right);
  }
}


int main(int argc, char** argv)
{
  int key;

  char *msg;
  msg = malloc(sizeof(char) * 128);

  tree t;

  printf("\n");
  printf("\n  Binary Tree ");

  printf("\n");
  printf("\n root ");


  while (1)
  {
    printf("\n");

    printf("\n 1. insert ");
    printf("\n");

    printf("\n 2. ergod ");

    printf("\n");

    printf("\n 0|q quit ");
    printf("\n");

    printf("\n   ");

    key = getchar();

    switch(key)
    {
      case '1':
        insert(t, "");
        printf("\n\n continue ");
        getchar();
        getchar();
        break;

      case '2':
        printf("\n\n ergod... ");
        ergod(t);
        printf("\n\n continue ");
        getchar();
        getchar();
        break;


      case 'q':
      case '0':
        goto QUIT_FLAG;
    }
  }


  QUIT_FLAG:

  return 0;
}

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
typedef int Status;
typedef int TElemType;

/*
定义结构及基本操作
*/
typedef struct BiTNode {
  TElemType data;
  struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

typedef BiTree SElemType;
typedef struct  {
  SElemType *base;
  SElemType *top;
  int stacksize;
} SqStack;

Status InitStack(SqStack &S) {
  S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  if(!S.base) return ERROR;
  S.top=S.base;
  S.stacksize=STACK_INIT_SIZE;
  return OK;
}

Status GetTop(SqStack S, SElemType &e) {
  if(S.top==S.base) return ERROR;
  e=* (S.top-1);
  return OK;
}

Status Push(SqStack &S,SElemType e) {
  if(S.top-S.base>=S.stacksize) {
          S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
      if(!S.base) return ERROR;
      S.top=S.base+S.stacksize;
      S.stacksize+=STACKINCREMENT;
  }
  *S.top++=e;
  return OK;
}

Status  Pop(SqStack &S,SElemType &e) {
  if(!S.top) return ERROR;
  e=*--S.top;
  return OK;
}

bool StackEmpty(SqStack s) {
  return s.base==s.top;
}


//创建二叉树
void CreateBiTree(BiTree &t) {
  int ch=getchar();
  if(ch==' ') t=NULL;
  else {
    if( !( t=(BiTNode*)malloc(sizeof(BiTNode))) ) exit(OVERFLOW);
    t->data=ch;
    CreateBiTree(t->lchild);
    CreateBiTree(t->rchild);
  }
}

//递归遍历二叉树
void PreOrderTraverse(BiTree t) {
  if(t) {
    /* 以先序方式遍历,若要以中序或后序遍历
    只需改变以下三句顺序*/
    printf("%c ",t->data);
    PreOrderTraverse(t->lchild);
    PreOrderTraverse(t->rchild);
  }
}

//非递归遍历二叉树(中序)
void InOrderTraverse(BiTree t) {
  SqStack s;
  BiTree p;
  InitStack(s);
  Push(s,t);
  while( !StackEmpty(s) ) {
    while( GetTop(s,p)&&p ) { Push(s,p->lchild); }
    Pop(s,p);
    if( !StackEmpty(s) ) {
        Pop(s,p);
        printf("%c ",p->data);
        Push(s,p->rchild);
    }
  }
}

//递归求二叉树叶子数
int Leaf(BiTree t) {
  if(t==NULL) return 0;
  if( t->lchild==NULL && t->rchild==NULL ) return 1;
  else {
    return Leaf(t->lchild)+Leaf(t->rchild);
  }
}
//非递归求二叉树叶子数
static  int counter=0;
int NumOfLeaf(BiTree t) {
  SqStack s;
  BiTree p;
  InitStack(s);
  Push(s,t);
  while( !StackEmpty(s) ) {
    while( GetTop(s,p)&&p ) { Push(s,p->lchild); }
    Pop(s,p);
    if( !StackEmpty(s) ) {
      Pop(s,p);
      if(p->lchild==NULL&&p->rchild==NULL) counter++;
      Push(s,p->rchild);
    }
  }
  return counter;
}

int max(int x,int y) {
   return x>y?x:y;
}
//递归求二叉树的高
int HeightOfBiTree(BiTree t) {
  if(t==NULL) return 0;
  if( t->lchild==NULL && t->rchild ) return 1;
  else {
    return  1+max( HeightOfBiTree(t->lchild) , HeightOfBiTree(t->rchild) );
  }
}

#include "stdio.h"
#include "stdlib.h"
#include "BiTree.h"

/*
 * http://shakesmin.javaeye.com/blog/43107
 */
/*
测试二叉树结构及相关算法
*/
int main() {
  BiTree t;
  printf("请按先序正确输入二叉树(空格为空树):\n");
  CreateBiTree(t);

  printf("先序历遍: ");
  PreOrderTraverse(t);

  printf("\n中序历遍: ");
  InOrderTraverse(t);

  printf("\n递归法求叶子数:%d\n",Leaf(t));
  printf("非递归法求叶子数:%d\n",NumOfLeaf(t));

  printf("二叉树高:%d\n",HeightOfBiTree(t));
  return 0;
}