數據結構考研分類復習真題 第六章 答案 (五)[19]

　　 int Level(BiTree bt) //層次遍歷二叉樹並統計度為的結點的個數
　　{int num=; //num統計度為的結點的個數
　　if(bt){QueueInit(Q); QueueIn(Qbt)//Q是以二叉樹結點指針為元素的隊列
　　while(!QueueEmpty(Q))
　　{p=QueueOut(Q); printf(p>data);     //出隊訪問結點
　　if(p>lchild && !p>rchild ||!p>lchild && p>rchild)num++;//度為的結點
　　if(p>lchild) QueueIn(Qp>lchild); //非空左子女入隊
　　if(p>rchild) QueueIn(Qp>rchild); //非空右子女入隊
　　}  }//if(bt)
　　return(num); }//返回度為的結點的個數

　　 void exchange(BiTree bt)//將二叉樹bt所有結點的左右子樹交換
　　{if(bt){BiTree s
　　s=bt>lchild; bt>lchild=bt>rchild; bt>rchild=s; //左右子女交換
　　exchange(bt>lchild);  //交換左子樹上所有結點的左右子樹
　　exchange(bt>rchild);  //交換右子樹上所有結點的左右子樹
　　} }

　　[算法討論]將上述算法中兩個遞歸調用語句放在前面將交換語句放在最後則是以後序遍歷方式交換所有結點的左右子樹中序遍歷不適合本題下面是本題（）要求的非遞歸算法

　　（）void exchange(BiTree  t)   //交換二叉樹中各結點的左右孩子的非遞歸算法
　　{int top=; BiTree s[]p;   //s是二叉樹的結點指針的棧容量足夠大
　　if(bt)
　　{s[++top]=t;
　　while(top>)
　　{t=s[top];
　　if(t>lchild||t>rchild){p=t>lchild;t>lchild=t>rchild;t>rchild=p;}//交換左右
　　if(t>lchild) s[++top]=t>lchild; //左子女入棧
　　if(t>rchild) s[++top]=t>rchild; //右子女入棧
　　}//while(top>)
　　}//if(bt)   }// 結束exchange

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23719.html