二叉树

#define TRUE 1
#define FALSE 0

//---------二叉树链式表示-----------
typedef int Status;
typedef struct BiTNode
{
 char data;
 struct BiTNode * lchild, * rchild;
}BiTNode,* BiTree;
typedef struct Stack
{
 BiTree * top, * base;
}Stack;
#include "iostream"
#include "cstdio"
#include "cstdlib"
//----------栈的函数的定义-----------
void InitStack(Stack &S)
{
 S.base = S.top  = (BiTree *)malloc(sizeof(BiTree) * 100);
}
Status StackEmpty(Stack S)
{
 if(S.top == S.base) return TRUE;
 else return FALSE;
}
void Push(Stack &S,BiTree e)
{
 * S.top ++ = e;
}
void Pop(Stack &S,BiTree &e)
{
 e = *( --S.top );
}
BiTree GetTop(Stack S)
{
 return *(S.top-1);
}
//----------二叉树的函数定义----------
void CreateBiTree(BiTree &T)
{//按先序次序输入二叉树中结点的值(一个字符),# 代表空树 ,如:ABC##DE#G##F###
//则前序遍历:ABCDEGF  中序遍历:CBEGDFA  后序遍历:CGEFDBA
 char ch = getchar();
 if(ch == '#') T = NULL;
 else {
  if(!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
  T->data = ch;    //生成根结点
  CreateBiTree(T->lchild); //构造左子树
  CreateBiTree(T->rchild); //构造右子树
 }
}//CreateBiTree
void Visit(char c)
{
 printf("%c",c);
}
void PreOrderTraverse(BiTree T)
{//先序遍历二叉树,递归
 if(T){
  Visit(T->data);
  PreOrderTraverse(T->lchild);
  PreOrderTraverse(T->rchild);
 }
}
void PostOrderTraverse(BiTree T)
{//先序遍历二叉树,递归
 if(T){
  PostOrderTraverse(T->lchild);
  PostOrderTraverse(T->rchild);
  Visit(T->data);
 }
}
void InOrderTraverse(BiTree T)
{//中序遍历二叉树,非递归
 
 
 Stack S;InitStack(S);
 BiTree p = T;
    while( p || !StackEmpty(S)) {
  //printf("\n%%%%%%%%%%%%调试%%%%%%%%%%%%%%%%%%%%\n");
  //PreOrderTraverse(p);
  //PreOrderTraverse(GetTop(S));
  //printf("\n%%%%%%%%%%%%调试%%%%%%%%%%%%%%%%%%%%\n");
  if(p) {Push(S,p);   p = p->lchild;}
  if( p == NULL && !StackEmpty(S)) {
  // printf("dddd\n");
   Pop(S,p);//空指针退栈
   Visit(p->data);
   p = p->rchild; 
  }//else
 }//while
}
void CountLeaf (BiTree T,  int& count){
   if ( T ) {
      if ((!T->lchild)&& (!T->rchild))
         count++;     // 对叶子结点计数
      CountLeaf( T->lchild, count); 
      CountLeaf( T->rchild, count);
   } // if
} // CountLeaf
int Depth (BiTree T ){ // 返回二叉树的深度
 int depthval,depthLeft,depthRight;
 if ( !T )    depthval = 0;
 else  {
  depthLeft = Depth( T->lchild );
  depthRight= Depth( T->rchild );
  depthval = 1 + ( depthLeft > depthRight ? depthLeft : depthRight);
  
 return depthval;
}


int main()
{
 BiTree T;
 int count = 0;

 int num,init=0;
    int door=1;//控制是否退出最外层while循环
 while( door )
 
  printf("-----------------------------------------------------------------\n");
  printf("\n       如要对二叉树进行操作,请输入各项前面相应的数字\n");
  printf("          ************************************\n");
  printf("         1、创建二叉树                |\n");
  printf("         2、先序遍历(递归)          |\n");
  printf("         3、中序遍历(非递归)        |\n");
  printf("         4、后序遍历(递归)          |\n");
  printf("         5、求叶子节点个数            |\n");
  printf("         6、求树的深度                |\n");
  printf("         0、退出                      |\n");
  printf("          ************************************\n");

  printf(" 请输入数字进行操作:");
  scanf("%d",&num);
  if(num==0||num==1||num==2||num==3||num==4||num==5||num==6)
  {
   printf("\n-----------------------------------------------------------------\n");
   switch( num )
   {
    case 0:
      door = 0;
      break;
    case 1:
      printf("请按先序次序输入二叉树的结点(以A、B、C等代表结点,# 代表空),如ABC##DE#G##F###\n");
      getchar();//清屏函数
      CreateBiTree(T);
      init=1;
      break;  
    case 2:
      if(init){
       printf("先序遍历为:");  PreOrderTraverse (T);  printf("\n"); break;
      }
      else{ printf("请先创建二叉树!\n"); break;}
    case 3:
      if(init){
       printf("中序遍历为:");   InOrderTraverse(T);   printf("\n"); break;
      }
      else{ printf("请先创建二叉树!\n"); break;}
     
    case 4:
      if(init){
       printf("后序遍历为:");   PostOrderTraverse(T);  printf("\n"); break;
      }
      else{ printf("请先创建二叉树!\n"); break;}
     
    case 5:
      if(init){
       CountLeaf(T,count); printf("叶子结点个数为:%d\n",count); break;
      }
      else{ printf("请先创建二叉树!\n"); break;}

    case 6:
      if(init){
       printf("树的深度为:%d\n",Depth(T)); break;
      }
      else{ printf("请先创建二叉树!\n"); break;}
  
   }//switch
  }//if
  else {printf("输入不正确请重新输入!\n");continue;}
 }//while
 return 0;
}