东锦资源再生施文东:交换二叉树所有节点的左右子树

//实验题目：已知二叉树以二叉链表作为存储结构，写一个算法来交换二叉树的所有节点的左右子树
//先建立二叉树的二叉链表存储结构，再完成算法，注意结果的输出形式

#include
#include
#include

#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
//定义二叉树数据类型
typedef char TElemtype;
typedef struct BiTNode
{
   
      TElemtype data;
      struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//-------二叉树基本操作-------
//初始化二叉树
bool InitBiTree(BiTree &T)
{
      T=(BiTree)malloc(sizeof(BiTNode));
      T->data=NULL;
      T->lchild=NULL;
      T->rchild=NULL;
      return true;
}
//创建二叉树
void CreateBiTree(BiTree &T)
{
     
     
     
    TElemtype c=' ';
      c=getchar();
      getchar();
      if(c==' ')
      {
            T=NULL;
      }
      else
      {
        InitBiTree(T);
            T->data=c;
            CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
      }
     
     
}
//操作函数---输出
bool Visit(TElemtype e)
{
      if(e!=NULL)
      {
       printf("%c ",e);
         return true;
      }
      else
      {
            return false;
      }

}
//先序遍历二叉树
bool PreOrderTraverse(BiTree T,bool Visit(TElemtype))
{
     if(T)
       {

             if(Visit(T->data))
             {
                   if (PreOrderTraverse(T->lchild,Visit))
                   {
                         if (PreOrderTraverse(T->rchild,Visit))
                         {
                               return true;
                         }
                   }
                  
             }
             return false;
       }
       else
       {
             return true;
       }
}
//----------------------------

//定义栈的数据类型
typedef struct
{
      TElemtype *base;
      TElemtype *top;
      int stacksize;
}SqStack;

//交换左右子树
void exchange(BiTree &rt){
 BiTree temp = NULL;
 if(rt->lchild == NULL && rt->rchild == NULL)
        return;
 else{
       temp = rt->lchild;
       rt->lchild = rt->rchild;
       rt->rchild = temp;
 }
 if(rt->lchild)
      exchange(rt->lchild);
 if(rt->rchild)
      exchange(rt->rchild);
}

//-------Main函数----
void main()
{
      BiTree T;
    MessageBox(NULL,"请按照先序遍历输入二叉树！","提示",MB_OK|MB_ICONWARNING);
      MessageBox(NULL,"请输入数据！(空格表示结束)","提示",MB_OK|MB_ICONWARNING);
      CreateBiTree(T);
      MessageBox(NULL,"输入结束！","提示",MB_OK|MB_ICONWARNING);
      printf("\n按先序输出\n");
      PreOrderTraverse(T,Visit);
      MessageBox(NULL,"输出结束！","提示",MB_OK|MB_ICONWARNING);
    printf("\n交换后\n");
      exchange(T);
    PreOrderTraverse(T,Visit);

}