#include "math.h"  
#include "malloc.h"  
#include "stdio.h"  
#include "conio.h"  
#include "stdlib.h"  
#include <queue>  
  
#define stackinitsize 100  
#define OK 1  
#define ERROR 0   
char prelist[stackinitsize];  
char inlist[stackinitsize];  
  
typedef int TElemType ;  
typedef int Status;  
  
  
  
  
       //一一一一一二叉树的二叉链表存储表示一一一一一  
typedef struct  BiTNode{              //二叉树结构体  
     char   data;  
     struct  BiTNode  *lchild,*rchild,*node;   //左右孩子指针  
   }BiTNode,*SElemType,*BiTree;  
  
  
  
typedef struct{  
  //该堆栈的元素是指针类型的  
  //base和top均是指向指针的指针  
  SElemType *base;  
  SElemType *top;  
  int stacksize;  
}sqstack;//堆栈结构  
  
Status InitStack(sqstack &s)//初始化堆栈  
 {  
  s.base=(SElemType*)malloc(100*sizeof(SElemType));  
  if(!s.base) return NULL;  
  s.top=s.base;  
  s.stacksize=100;  
  return OK;  
 }  
  
int StackEmpty(sqstack &s) //栈空判别  
 {return(s.top==s.base); }  
  
Status Pop(sqstack &s,SElemType &e)//弹栈(若栈不为空，删除栈顶元素，用e返回其值)  
 {  if(s.top==s.base)  return ERROR;   
 e=*--s.top;   return OK;}  
  
Status GetTop(sqstack &s,SElemType &e)    //若栈不为空，用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+10)*sizeof(SElemType));
  if(!s.base) exit (OVERFLOW);  //存储分配失败  
  s.top=s.base+s.stacksize;  
  s.stacksize+=10;  
 }  
 *s.top++ =e;  
 return OK;  
 }  
  
Status  PrintElement(TElemType  e)                                       //应用函数  
       {   //输出元素e的值  
           printf("%2c",e);         
           return  OK;  
 }  
  
  
  
StatusPreOrderCreateBiTree(BiTree&T){     //按先序 次序构造二叉树
  
    //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。  
    //构造二叉链表表示的二叉树T.  
    char ch;  
   
    ch=getchar();   
    if(ch==' ') T=NULL;  
     else{  
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit (OVERFLOW);  
        T->data=ch;             //生成根结点  
        PreOrderCreateBiTree(T->lchild);//构造左子树  
        PreOrderCreateBiTree(T->rchild);//构造右子树  
   
    }  
      return  OK;  
    }//CreateBiTree  
  
  
  
BiTNode *preintotree(char pre[100],char in[100],int i,int j,int k,int l)   //已知前序、后序序列恢复二叉树  
{  
  int m;  
  BiTNode *p;  
  p=(BiTNode*)malloc(sizeof(BiTNode));  
  p->data=pre[i];  
  m=k;  
  while(in[m]!=pre[i])  
        m++ ;  
       if (m==k)p->lchild=NULL;  
           else p->lchild=preintotree(pre,in,i+1,i+m-k,k,m-1);  
       if (m==j)p->rchild=NULL;  
           else p->rchild=preintotree(pre,in,i+m-k+1,j,m+1,l);  
       return p;  
}  
  
  
  
Status  PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e))                      //先序遍历  
       //采用二叉链表存储结构，visit是对数据元素操作的应用函数，  
       //先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。  
        
  
  {  
       if(T)  
       { if (Visit(T->data))  
         if (PreOrderTraverse(T->lchild,Visit))  
             if  (PreOrderTraverse(T->rchild,Visit)) return  OK;  
             return  ERROR;  
       }  
    else  return  OK;  
  
 }//preOrderTraVerse  
   
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))                    //中序遍历  
       //采用二叉链表存储结构，visit是对数据元素操作的应用函数，  
       //中序遍历二叉树T的递归算法，对每个数据元素调用函数visit。  
   {  
      if(T){  
             if (InOrderTraverse(T->lchild,Visit))  
             if (Visit(T->data))  
                 if (InOrderTraverse(T->rchild,Visit))   return  OK;  
                 return  ERROR;
      }  
     else  return  OK;  
//    printf("\n");  
      }//preOrderTraVerse  
  
Status  PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e))                   //后序遍历  
       //采用二叉链表存储结构，visit是对数据元素操作的应用函数，  
       //后序遍历二叉树T的递归算法，对每个数据元素调用函数visit。  
   {  
       if(T){  
             if (PostOrderTraverse(T->lchild,Visit))  
             if (PostOrderTraverse(T->rchild,Visit))  
                 if (Visit(T->data)) return  OK;  
                 return  ERROR;  
       }  
    else  return  OK;  
//    printf("\n");  
    }//preOrderTraVerse  
  
  
  
void LevelOrderTranslever(BiTNode *T)            //层序遍历  
{  
    struct node  
    {   
        BiTNode *vec[20];  
        int f,r;                //r为队尾，f为队头  
    }queue;  
    BiTNode *p;  
    p=T;  
    queue.f=0;  
    queue.r=0;  
    if(T)  
        printf("%c ", p->data);  
    queue.vec[queue.r]=p;  
    queue.r=queue.r+1;  
    while(queue.f<queue.r)  
    {  
        p=queue.vec[queue.f];  
        queue.f=queue.f+1;  
        if(p->lchild)  
        {  
            printf("%c ",p->lchild->data);  
            queue.vec[queue.r]=p->lchild;  
            queue.r=queue.r+1;  
        }  
        if(p->rchild)  
        {  
            printf("%c ",p->rchild->data);  
            queue.vec[queue.r]=p->rchild;  
            queue.r=queue.r+1;  
        }  
    }  
    printf("\n");  
}  
  
  
  
Status  Exchange(BiTNode *t)             //交换左右子树  
{  
    BiTNode *temp;  
    if(t)  
    {  
        Exchange(t->lchild);  
        Exchange(t->rchild);  
        temp=t->lchild;  
        t->lchild=t->rchild;  
        t->rchild=temp;      return OK;  
    }  
 return ERROR;  
}   
Status  Leaves_Num(BiTNode *t)                                           //计算叶子结点个数  
 { if(t){ if(t->lchild==NULL && t->rchild==NULL)return OK;  
          return (Leaves_Num(t->lchild)+Leaves_Num(t->rchild));
}
          else return ERROR;  
 }  
  
int a=0;  
void  Branch_Num(BiTNode *t)                                              //计算分支结点个数  
 {   
  if(t){   
   if(t->lchild!=NULL || t->rchild!=NULL)a++,Branch_Num(t->lchild),Branch_Num(t->rchild) ;  
   }  
 }  
  
Status height(BiTNode *t)                                                //二叉树的高度  
 { if(!t) return ERROR;  
   int hl=height(t->lchild );  
   int hr=height(t->rchild );  
   if(hl>hr)return ++hl;  
   else return ++hr;  
 }  
  
/*BiTNode  *Search(BiTNode *T,char i)    //查询结点  
 { if(T!=NULL)  
   { if(T->contents==i)return 1;  
     if(T->lchild !=NULL)  
          if(T->lchild ->contents ==i)return 2;  
     if(T->rchild !=NULL)  
          if(T->rchild ->contents ==i)return 3;  
     Search(T->lchild,i);  
     Search(T->rchild,i);  
   }  
 }  
BiTNode   *   Search(BiTNode *T,int i)              //按给定值在二叉排序树中查询   
{   
 BiTNode   *   p;   
 if   (T   ==   NULL) p=NULL;   
 else { if   (i   ==   T-> data) p   =   T;   
    else   if   (i >   T-> data) p = Search(i, T-> rchild);   
      else p=Search(i, T-> lchild);   
       return   p;   
   }
  
void Search_bst(BiTNode *T)  
{int s;  
 BiTNode *p;  
 char[5];  
 printf("\n");  
 printf( "请输入要查询的结点值: ");   
scanf( "%d ",&s);   
if  (   s!=   0)   
    {p=Search(T,s);  
     if(p=NULL)printf( "该结点值不存在!\n ");  
     else printf( "该结点值存在!\n ");   
    }  
}           
           
           
/* { if(!T) return ERROR;  
     else if(elem==T->data)return OK;  
             else if(elem%2==0) Search(T->rchild,elem,T,p);  
                     else Search(T->rchild,elem,T,p);  
   
 }*/  
  
/*Status Insert(BiTNode *T,char i,TElemType e)                    //插入结点  
 {   
  BiTNode *s;  
  if(!s)  
  { s=(BiTNode *)malloc(sizeof(BiTNode));  
    s->node->contents =e;s->lchild=s->rchild=NULL;  
    if(Search(T,i)==1)T->node =s;  
    if(Search(T,i)==2)T->lchild=s;  
       else if(Search(T,i)==3)T->rchild=s;  
    return OK;  
  }  
  else return ERROR;  
 }  
  
  
/*void Delete(BiTNode *T,char i)//删除结点  
 { if(T)  
        if(T->node==i)  
           {delete node;node=NULL;printf("已删除结点,当前树为空");}  
 }     
   
 BiTree q,s;
 if(!p->rchild)  
 { q=p;  
   p=p->lchild;  
   free(q);  
  }  
  else if(!p->lchild)  
 {  
  q=p;  
  p=p->rchild;  
  free(q);  
 }  
  else {  
  
    q=(*p);  
    s=(*p)->l;  
    while(s->r) {q=s; s=s->r;}  
    (*p)->data=s->data;  
    if(q!=(*p) ) q->r=s->l;  
    else q->l=s->l;  
    free(s);  
      
  
    q=s=p->lchild;  
    while(s->rchild) s=s->rchild;  
    s->rchild=p->rchild;  
    free (p);  
    p=q;  
  
  }  
}*/  
  
  
/*Status DeleteBST(BiTNode *T,TElemType elem)//删除树  
{  
  if (!T){return ERROR;}  
  else{  
       if  (elem==T->data) Delete(T);  
        else if ( elem<T->data) DeleteBST( T->lchild, elem);  
            else DeleteBST( T->rchild,elem);  
       return OK;  
  }  
}*/  
  
  
  
Status  InorderTraverseNoRecursion(BiTree T,Status(*Visit)(TElemType e))       //中序非递归算法-------1  
           
    //采用二叉链表存储结构，visit是对数据元素操作的应用函数。  
    //中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。  
   {sqstack s;  
    BiTree p;  
    InitStack(s);p=T;   
    while(p||!StackEmpty(s))  
      {  
        if(p){ Push(s,p);p=p->lchild;}//根指针进栈，遍历左子树  
               else{       //根指针退栈，访问根结点，遍历右子树  
                    Pop(s,p);  
                    if(!Visit(p->data))  return  ERROR;  
                       p=p->rchild;  
               }//else  
    }//while  
   return  OK;  
 }//InorderTraVerse1  
  
/*Status  InorderTraverseNoRecursion2(BiTree T,Status(*Visit)(TElemType e))      ////中序非递归算法 -------2  
           
    //采用二叉链表存储结构，visit是对数据元素操作的应用函数。  
    //中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。  
   {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(!Visit(p->data))  return  ERROR;  
       Push(s,p->rchild);  
                           }//if  
      }//while  
    return  OK;  
  }//InorderTraVerse1  
*/  
  
void Disptree(BiTNode *T)                                //输出二叉树  
{  
    if(T)  
    {  
        printf("%c",T->data);      
        if(T->lchild || T->rchild)  
        {  
            printf("(");  
            Disptree(T->lchild);  
            if(T->rchild)  
                printf(",");  
            Disptree(T->rchild);  
            printf(")");  
        }  
    }  
}  
  
  
  
  
void main()  
{  
  BiTree t;  
  int i,n;  
grade:while(1)  
  {   
    printf("\n\n");   
    printf("        ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");  
    printf("        ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");  
    printf("        ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");  
    printf("        ★★★                                            ★★★\n");  
    printf("        ★★★      2.按先序次序构造二叉树                ★★★\n");  
    printf("        ★★★      3.先序遍历、中序遍历、后序遍历        ★★★\n");  
    printf("        ★★★      4.层序遍历                            ★★★\n");  
    printf("        ★★★      5.非递归中序遍历                      ★★★\n");  
    printf("        ★★★      6.二叉树高度                          ★★★\n");  
    printf("        ★★★      7.二叉树叶子结点个数                  ★★★\n");  
    printf("        ★★★      8.二叉树分支结点个数                  ★★★\n");  
    printf("        ★★★      9.二叉树中所有结点的左右子树交换      ★★★\n");  
    printf("        ★★★      r.返回主菜单                          ★★★\n");  
    printf("        ★★★      0.退出程序                            ★★★\n");  
    printf("        ★★★                                            ★★★\n");  
    printf("        ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");  
    printf("        ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    printf("        ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");  
    while(1){  
    printf("\n请输入您的操作序号:  ");  
    char d=getche();  
    switch(d)  
    { case '0':printf("\n    程序运行结束，按任意键退出!\n\n");exit(0);break;  
      case '1':printf("\n请输入前序序列：\n");
               getch();  
                    for(n=0;;n++)//prelist[n]=getchar();  
                    {  
                      scanf("%c",&prelist[n]);  
                      if(prelist[n-1]=='#') break;  
                    }  
               printf("\n请输入中序序列：");  
                     for(n=0;;n++)//inlist[n]=getchar();  
                    {  
                      scanf("%c",&inlist[n]);  
                      if(prelist[n-1]=='#') break;  
                    }  
               t=preintotree(prelist,inlist,0,strlen(prelist)-1,0,strlen(inlist)-1);  
               printf("\n恢复后的后序序列为：");  
               PostOrderTraverse(t,PrintElement);  
  
               break;  
      case '2':printf("\n请按先序遍历输入二叉树（当左右子树为空时用空格输入）\n");PreOrderCreateBiTree(t);break;  
      case '3':printf("\n 该二叉树的先序遍历为：");PreOrderTraverse(t,PrintElement);  
               printf("\n    该二叉树的中序遍历为： ");InOrderTraverse(t,PrintElement);//Disptree(t);  
               printf("\n 该二叉树的后序遍历为：");PostOrderTraverse(t,PrintElement);  
               printf("\n    该二叉树的树状形态为：");Disptree(t);printf("\n");break;  
      case '4':printf("\n    该二叉树的层序遍历为：");LevelOrderTranslever(t);break;  
      case '5':printf("\n    该二叉树的中序遍历为(用非递归调用)：");InorderTraverseNoRecursion(t,PrintElement);printf("\n");break;  
      case '6':printf("\n    该二叉树的高度为：%d",height(t));printf("\n");break;  
      case '7':printf("\n    该二叉树的叶子结点个数为：%d",Leaves_Num(t));printf("\n");break;  
      case '8':Branch_Num(t);printf("\n    该二叉树的分支结点个数为：%d",a);printf("\n");break;  
      case '9':Exchange(t);printf("\n    该二叉树左右子树交换后的先序遍历为：");  
                 PreOrderTraverse(t,PrintElement);printf("\n    该二叉树的树状形态为：");Disptree(t);printf("\n");break;  
      case 'r':goto grade;  
      default:printf("    输入无效，请重新选择操作!\n");  
    }  
}  
}   
}

定义

StatusPreOrderCreateBiTree(BiTree&T)//这里