遞回方式基本思想：
- 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;//回傳根結點
}
若有錯誤，歡迎指正
我們一起進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/536785.html
標籤：C