面试题集锦_8

将二叉树的两个孩子换位置，即左变右，右变左。不能用递归
实现代码：
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef struct BiTNode{
  4 char data;
  5 struct BiTNode *lchild,*rchild;
  6 }BiTNode,*BiTree;
  7 
  8 typedef struct QNode{
  9 BiTree t;
 10 struct QNode *next;
 11 }QNode,*QueuePtr;
 12 typedef struct{
 13 QueuePtr front;//队头指针
 14 QueuePtr rear;//队尾指针
 15 }LinkQueue;
 16 
 17 void InitQueue(LinkQueue &Q)
 18 {
 19     //构造一个空队列Q
 20     Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//头结点
 21     if(!Q.front)
 22         exit(0);
 23     Q.front->next=NULL;
 24 }
 25 bool Empty(LinkQueue Q)
 26 {
 27     if(Q.front==Q.rear)
 28         return true;
 29     else
 30         return false;
 31 }
 32 void EnQueue(LinkQueue &Q, BiTree t)
 33 {
 34    QueuePtr p;
 35    p=(QueuePtr)malloc(sizeof(QNode));
 36    if(!p)
 37        exit(0);
 38    p->t=t;
 39    p->next=NULL;
 40    Q.rear->next=p;
 41    Q.rear=p;//插入的t为Q的新的队尾元素
 42 }
 43 
 44 void DeQueue(LinkQueue &Q,BiTree &t)
 45 {
 46     QueuePtr p;
 47     if(Q.front==Q.rear)
 48     {
 49       printf("队列为空！");
 50       exit(0);
 51     }
 52     p=Q.front->next;
 53     t=p->t;
 54     Q.front->next=p->next;
 55     if(Q.rear==p)//只有一个元素的情况下，出去一个元素就变成空队列
 56         Q.rear=Q.front;
 57     free(p);
 58 }
 59 void change_Q(BiTree &T)//非递归
 60 {
 61   LinkQueue q;
 62   InitQueue(q);
 63   BiTree t,temp;
 64   EnQueue(q,T);//根结点入队列
 65   while(!Empty(q))
 66   {
 67     DeQueue(q,t);
 68     temp=t->lchild;
 69     t->lchild=t->rchild;
 70     t->rchild=temp;
 71     if(t->lchild!=NULL)
 72     EnQueue(q,t->lchild);//体会这里的妙处，原来交换过来了，想象入队列的情况
 73     if(t->rchild!=NULL)
 74     EnQueue(q,t->rchild);
 75   }
 76 
 77 }
 78 void change(BiTree &T)//递归
 79 {
 80     if(T)
 81     {
 82     BiTNode *temp;
 83     temp=T->lchild;
 84     T->lchild=T->rchild;
 85     T->rchild=temp;
 86     change(T->lchild);
 87     change(T->rchild);
 88     }
 89 }
 90 void CreateBiTree(BiTree &T)
 91 {
 92     char ch;
 93     //scanf("%c",&ch);
 94     if((ch=getchar())=='\n')
 95         T=NULL;
 96     else
 97     {
 98         if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
 99             exit(0);
100         T->data=ch;
101         CreateBiTree(T->lchild);
102         CreateBiTree(T->rchild);
103     }
104 }
105 void PreOrderTraverse(BiTree T)
106 {
107     if(T)
108     {
109       printf("%c",T->data);
110       PreOrderTraverse(T->lchild);
111       PreOrderTraverse(T->rchild);
112     }
113 }
114 int main()
115 {
116   BiTree T;
117   CreateBiTree(T);
118   PreOrderTraverse(T);
119   printf("\n");
120   change_Q(T);
121   PreOrderTraverse(T);
122 }
View Code
非递归算法参考自：http://hi.baidu.com/liuhuaxi2009/item/fe5b2f3af7878fc3392ffac4