第就章第21题(赶出来的作业) POWERBY KTL

//第九章第21题,交换左右子树;
//输入参考书本p194,图9-8,输入为ABCDEFG@@@@L@@@#;中序遍历结果应该为DBEALFCG;
//交换左右子树后进行中序遍历的结果应为:GCFLAEBD;
//可以用别的二叉树进行验证;若程序出错的话可能是没有设置好maxsize的值;
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define maxsize 15  //若二叉树深度为n,则设置为2^n-1;

typedef char datatype;

typedef struct node
{
 datatype data;
 struct node *lchild,*rchild;
}bitree;

bitree *root;

bitree * CreatTree(void)
{
 char ch;
 bitree * Q[maxsize];
 int front,rear;
 bitree *root,*s;
 root=NULL;
 front=1;
 rear=0;
 printf("请输入字符构造二叉树,#结束,@表示虚结点./n");
 while((ch=getche())!='#')
 {
  s=NULL;
  if(ch!='@')
  {
   s=(bitree*)malloc(sizeof(bitree));
   s->data=ch;
   s->lchild=NULL;
   s->rchild=NULL;
  }
  rear++;
  Q[rear]=s;
  if(rear==1)
   root=s;
  else
  {
   if(s&&Q[front])
    if(rear%2==0)
     Q[front]->lchild=s;
    else
     Q[front]->rchild=s;
    if(rear%2==1)
     front++;
  }
 }
 printf("创建二叉树完成.../n");
 return root;
}

bitree* Exchange(bitree * p)  //该算法的主要思想是把递归函数看成一个黑盒,作用是
{         //遍历,参考中序遍历函数,只要把printf的函数替换为
 bitree *temp;     //交换的函数即可;

 if(p!=NULL)
 {
  temp=p->lchild;
  p->lchild=p->rchild;
  p->rchild=temp;
  Exchange(p->lchild);
  Exchange(p->rchild);
 } 
 return p;
}

void inorder(bitree *p)
{
 if(p!=NULL)
 {
  inorder(p->lchild);
  printf("%c",p->data);
  inorder(p->rchild);
 }
 return;
}

int main()
{
 root=CreatTree();
 printf("交换前的二叉树进行中序排列/n");
 inorder(root);
 root=Exchange(root);
 printf("交换后的二叉树进行中序排列/n");
 inorder(root);
 printf("程序结束.../n");
 return 0;
}