二叉树中所有节点的左右子树相互交换 递归与非递归程序

//将二叉树中所有节点的左右子树相互交换

转自：http://blog.csdn.net/girlkoo/article/details/17605349

BiNode* Exchange(BiNode* T)
{
 BiNode* p;
 if(NULL==T || (NULL==T->lchild && NULL==T->rchild))
  return T;
 p = T->lchild;
 T->lchild = T->rchild;
 T->rchild = p;
 if(T->lchild)
 {
  T->lchild = Exchange(T->lchild);
 }
 if(T->rchild)
 {
  T->rchild = Exchange(T->rchild);
 }
 return T;
}

 

//将二叉树中所有节点的左右子树相互交换
//不使用递归

void NonRecursive_Exchange(BiNode* T)
{
 Stack s;
 BiNode* p;
 if(NULL==T)
  return;
 InitStack(&s);
 Push(&s,T);
 while(!isEmpty(&s))
 {
  T = Pop(&s);
  p = T->lchild;
  T->lchild = T->rchild;
  T->rchild = p;

  if(T->rchild)
   Push(&s,T->rchild);
  if(T->lchild)
   Push(&s,T->lchild);
 }
 DestroyStack(&s);
}