Question

二叉树，如何设计一个算法，使得交换左右子树。要求非递归算法。

Answer 1

不是很简单吗？
childtype x=a.lchild;
a.lchild=a.rchild;
a.rchild=x;

Answer 2

　　递归算法：
　　void exchange(BitTree T){
　　 BitNode p;
　　if(T->lchild==null && T->rchild==null)
　　 return;
　　 else{
　　 p=T->lchild;
　　 T->lchild=T->rchild;
　　 t->rchild=P;
　　 }
　　if(T->lchild){
　　exchange(T->lchild);
　　}
　　if(T->rchild){
　　exchange(T->rchild);
　　}
　　}
　　非递归算法
　　使用栈作为存储结构
　　void exchange(BitTree T){
　　定义并初始化栈
　　Stack s；
　　InitStack(s);
　　BitNode p,temp;
　　p=T;
　　while(p && !EmptyStack(s)){
　　if(p){
　　push(p);
　　p=p->lchild;
　　}
　　else{
　　temp=p->lchild;
　　p->lchild=p->rchild;
　　p->rchild=temp;
　　p=p->lchild;
　　}
　　}
　　}