二叉樹交換左右子樹遞歸以及非遞歸演算法

遞歸方式基本思想：

• 1、當待處理節點非空時，判斷其左右孩子是否不同時為空：若是，轉到2、否則分別遞歸調用左右子樹進行操作。
• 2、新建一個輔助結點，執行交換操作。
• 3、遞歸調用非空的左右子樹進行操作。

BiTree *exchangeChild(BiTree *&T){
	if(T==null) return null;//當結點為null直接return null
	if(T->lchild!=null||T->rchild!=null){//當待處理結點左右孩子不同時為空時交換
		BiTNode *temp=T->lchild;//輔助結點，用於交換
		T->lchild=T->rchild;
		T->rchild=temp;
	}
	//遞歸交換左右子樹
	exchangeChild(T->lchild);
	exchangeChild(T->rchild);
	return T;
}

非遞歸方式基本思想：

需要利用隊列進行操作：

• 1、當待處理結點非空時入隊。
• 2、當隊非空時，轉到3、，否則代表操作完成，直接return 根結點。
• 3、隊頭元素出隊，判斷其左右孩子是否不同時為空：若是，轉到4、否則將非空的左右孩子依次入隊，執行2、。
• 4、新建一個輔助結點，執行交換操作。並將非空的左右孩子依次入隊，執行2、。

BiTree *exchangeChild(BiTree *&T){
	BiTNode *temp;              //輔助結點，用於交換結點
	InitQueue(Q);               //利用隊列實現，初始化隊列
	if(T!=null) EnQueue(Q,T);   //當結點不為空時入隊
	while(!IsEmpty(Q)){         //當隊非空時
		DeQueue(Q,T);       //隊首元素出隊
		if(T->lchild!=null||T->rchild!=null){//當隊首元素的左右孩子不同時為空時執行交換操作
			temp=T->lchild;
			T->lchild=T->rchild;
			T->rchild=temp;
		}
		//對非空的孩子結點入隊，繼續執行上述操作
		if(T->lchild!=null){
			EnQueue(Q,T->lchild);
		}
		if(T->rchild!=null){
			EnQueue(Q,T->rchild);
		}
	}
	return T;//返回根結點
}

                             若有錯誤，歡迎指正
                              我們一起進步！