?注：本文采用隊(duì)列和遞歸的算法進(jìn)行創(chuàng)建和層次遍歷。同時不能采用BFS和DFS，因?yàn)樾枰旬?dāng)前根節(jié)點(diǎn)的左孩、右孩勾鏈并輸入才能遞歸下一個根節(jié)點(diǎn)；
隊(duì)列用于存儲此時應(yīng)該遞歸的根節(jié)點(diǎn)；
格式：每一行尾不能有空格；
| Description |
| 根據(jù)輸入利用二叉鏈表創(chuàng)建二叉樹，并將所有結(jié)點(diǎn)的左右孩子交換，并輸出。 說明： 輸入的第一行為根結(jié)點(diǎn);第二行以后每行的第二元為第一元的左孩子，第三元為第一元的右孩子, 0表示空。 輸出時按結(jié)點(diǎn)層次順序輸出。 |
| Sample Input |
| A A B C B 0 D C 0 E D 0 0文章來源：http://www.zghlxwxcb.cn/news/detail-759359.html E 0 0 |
| Sample Output |
| A C B C E 0 B D 0 E 0 0 D 0 0 |
| Hint |
| 說明：輸出有換行 |
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
typedef struct BiTnode{//二叉鏈表存儲結(jié)構(gòu)
char data;
BiTnode *lc;
BiTnode *rc;
}BiTnode,*BiTree;
void initTree(BiTree &T,char data='*'){//初始化樹
T=new BiTnode;
T->lc=NULL;
T->rc=NULL;
if(data=='*'){
cin>>T->data;//先輸入根節(jié)點(diǎn)
}
else{
T->data=data;
}
}
queue<BiTree>Q;
void creatTree(BiTree &T){//遞歸創(chuàng)建二叉樹
//不能是BFS和DFS 在遞歸前需要把當(dāng)前結(jié)點(diǎn)勾鏈并輸入左孩右孩
//同時運(yùn)用隊(duì)列來實(shí)現(xiàn)按照層次依次訪問每一個非葉子結(jié)點(diǎn)（也就是每次遞歸的根節(jié)點(diǎn)）
if(Q.empty()) return;//遞歸的終止條件
char ch;
int cnt=1;//計(jì)數(shù) 1左 2右
while(cin>>ch)//輸入此時根節(jié)點(diǎn)的左孩、右孩
{
if(T->data==ch) continue;
BiTnode *p=NULL;
if(ch!='0'){
initTree(p,ch);
}
if(cnt==1){
T->lc=p;
}
else{
T->rc=p;
}
if(p){
Q.push(p);
}
if(cnt==2) break;
cnt++;
}
Q.pop();
creatTree(Q.front());//遞歸
}
void Levelorder(BiTree T){//層次遍歷二叉樹
Q.push(T);
while(!Q.empty())//隊(duì)列不為空循環(huán)
{
cout<<Q.front()->data<<" ";
if(Q.front()->rc!=NULL){
cout<<Q.front()->rc->data<<" ";
Q.push(Q.front()->rc);//右孩子進(jìn)隊(duì)
}
else {
cout<<"0"<<" ";
}
if(Q.front()->lc!=NULL){
cout<<Q.front()->lc->data<<endl;
Q.push(Q.front()->lc);//左孩子進(jìn)隊(duì)
}
else {
cout<<"0"<<"\n";
}
Q.pop();
}
}
int main(){
BiTree Tree;//二叉鏈表
initTree(Tree);
Q.push(Tree);//先把根節(jié)點(diǎn)進(jìn)隊(duì)需要滿足判斷
creatTree(Tree);
Levelorder(Tree);
return 0;
}?文章來源地址http://www.zghlxwxcb.cn/news/detail-759359.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-二叉樹-二叉樹左右孩子交換（遞歸）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
