二叉树交换左右子树递归以及非递归算法

递归方式基本思想：

• 1、当待处理节点非空时，判断其左右孩子是否不同时为空：若是，转到2、否则分别递归调用左右子树进行操作。
  
• 2、新建一个辅助结点，执行交换操作。
  
• 3、递归调用非空的左右子树进行操作。
  

1. BiTree *exchangeChild(BiTree *&T){
2.         if(T==null) return null;//当结点为null直接return null
3.         if(T->lchild!=null||T->rchild!=null){//当待处理结点左右孩子不同时为空时交换
4.                 BiTNode *temp=T->lchild;//辅助结点，用于交换
5.                 T->lchild=T->rchild;
6.                 T->rchild=temp;
7.         }
8.         //递归交换左右子树
9.         exchangeChild(T->lchild);
10.         exchangeChild(T->rchild);
11.         return T;
12. }

复制代码

非递归方式基本思想：
需要利用队列进行操作：

• 1、当待处理结点非空时入队。
  
• 2、当队非空时，转到3、，否则代表操作完成，直接return 根结点。
  
• 3、队头元素出队，判断其左右孩子是否不同时为空：若是，转到4、否则将非空的左右孩子依次入队，执行2、。
  
• 4、新建一个辅助结点，执行交换操作。并将非空的左右孩子依次入队，执行2、。
  

1. BiTree *exchangeChild(BiTree *&T){
2.         BiTNode *temp;              //辅助结点，用于交换结点
3.         InitQueue(Q);               //利用队列实现，初始化队列
4.         if(T!=null) EnQueue(Q,T);   //当结点不为空时入队
5.         while(!IsEmpty(Q)){         //当队非空时
6.                 DeQueue(Q,T);       //队首元素出队
7.                 if(T->lchild!=null||T->rchild!=null){//当队首元素的左右孩子不同时为空时执行交换操作
8.                         temp=T->lchild;
9.                         T->lchild=T->rchild;
10.                         T->rchild=temp;
11.                 }
12.                 //对非空的孩子结点入队，继续执行上述操作
13.                 if(T->lchild!=null){
14.                         EnQueue(Q,T->lchild);
15.                 }
16.                 if(T->rchild!=null){
17.                         EnQueue(Q,T->rchild);
18.                 }
19.         }
20.         return T;//返回根结点
21. }

复制代码

[code]                             若有错误，欢迎指正