#include <stdio.h>
#define OVERFLOW 0
#define MaxSize 100
typedef char ElemType;

typedef struct BiTNode{
   ElemType data;
   struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct
{
  BiTree tree[MaxSize];
  int top;   
}SqStack;

void InitStack(SqStack *s)
{
   s->top=-1;   
}

void ClearStack(SqStack *s)
{
   free(s);   
}
int StackLength(SqStack *s)
{
   return(s->top+1);
}
int StackEmpty(SqStack *s)
{
   if(s->top==-1)
    return 1;   
}
int Push(SqStack *s,BiTree T)
{
  if(s->top==MaxSize-1)
    return 0;
  s->top++;
  s->tree[s->top]=T;
  return 1;
}
BiTree Pop(SqStack *s,BiTree T)
{
   if(s->top==-1)
      return 0;
   T=s->tree[s->top];
   s->top--;
   return T;
}
BiTree GetTop(SqStack *s,BiTree T)
{
   if(s->top==-1)
      return ;
   T=s->tree[s->top];
   return T;
}

BiTree CreateBiTree(){
  ElemType ch;
  BiTree T;
  scanf("%c",&ch);
  if(ch=='#')  T=NULL;
  else {
      if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
      T->data=ch;              /*生成根结点*/
      T->lchild=CreateBiTree(); /*构造左子树*/
      T->rchild=CreateBiTree(); /*构造右子树*/
      }
  return T;
}

/*中序遍历二叉树递归算法*/
void Inorder(BiTree T){
  if(T!=NULL)
   {
     Inorder(T->lchild);
     printf("%c",T->data);
     Inorder(T->rchild);
   }
}

/*中序遍历二叉树非递归算法*/
void Inorderf(BiTree T){
   BiTree p;
   SqStack *S;
   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); /*扫描右子树*/
         }
    }
 }

/*先序遍历*/
 void preorder(BiTree t)
 {
   if(t!=NULL)
   { 
     printf("%c",t->data);
     preorder(t->lchild);
     preorder(t->rchild);
   }
 }

/*后序遍历*/
void postorder(BiTree t)
{
   if(t!=NULL)
   {
     postorder(t->lchild);
     postorder(t->rchild);
     printf("%c",t->data);
   }
}

/*先序遍历二叉树非递归算法*/
void Preorder(BiTree T){
  SqStack *S;
  BiTree p;
  InitStack(S);
  Push(S,T);
  while(!StackEmpty(S)){
    Pop(S,p);
    if(T!=NULL){
      printf("%c",p->data);  /*访问结点*/
      Push(S,p->rchild);     /*右子树入栈*/
      Push(S,p->lchild);     /*左子树入栈*/
    }
  }
}
/*求二叉树中叶子结点的数目*/
void CountLeaf(BiTree T,  int *count){
   if (T) {
      if ((!T->lchild)&& (!T->rchild))
        *count++;
      CountLeaf( T->lchild, count);  
      CountLeaf( T->rchild, count); 
   }
  }

/*求二叉树的深度*/
int  BiTreeDepth(BiTree T ){
   int depthval,depthLeft,depthRight;
   if ( !T )    depthval = 0;
   else   {
              depthLeft =BiTreeDepth( T->lchild );
              depthRight= BiTreeDepth( T->rchild );
              depthval = 1 + (depthLeft > depthRight  ?
                               depthLeft : depthRight);
   } 
   return depthval;
}

/*交换所有结点的左右子树*/
void Bitree_Revolute(BiTree T)
{ BiTree p;
  if(T){
  p=T->lchild;
  T->lchild=T->rchild;
  T->rchild=p;          /*交换左右子树*/
  if(T->lchild) 
      Bitree_Revolute(T->lchild); 
  if(T->rchild) 
      Bitree_Revolute(T->rchild); /*左右子树再分别交换各自的左右子树*/
  }
}
main(){
  BiTree T;
  int *n,count=0;
  n=&count;
  printf("建立二叉树\n");
  T=CreateBiTree();
  printf("\n先序遍历二叉树\n");
  preorder(T);
  printf("\n中序遍历二叉树\n");
  Inorder(T);
  printf("\n后序遍历二叉树\n");
  postorder(T);
  printf("\n非递归先序遍历二叉树\n");
  preorder(T);
  printf("\n非递归中序遍历二叉树\n");
  Inorderf(T);
  printf("\n交换左右子树后中序遍历\n");
  Bitree_Revolute(T);
  Inorder(T);
  CountLeaf(T,n);
  printf("\nleaf:%d",*n);
  printf("\ndepth:%d",BiTreeDepth(T));
  getch();
  }
这个程序的非递归先序遍历和非递归中序遍历总不对，还有叶子数总是０