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

　　．int Count (BiTree  bt) // 非遞歸遍歷求二叉樹上的葉子結點個數
　　{int num=;
　　BiTree s[]; //s是棧棧中元素是二叉樹結點指針棧容量足夠大
　　whlie(bt!=null || top>)
　　{while(bt!=null) {push(sbt)bt=bt>lchild}  //沿左分支向下
　　if(!StackEmpty(s))
　　{bt=pop(s)if(bt>lchild==null && bt>rchild==null) num++//葉子結點
　　bt=bt>rchild
　　}
　　} return(num);
　　}//結束Count

　　[題目分析]對二叉樹的某層上的結點進行運算采用隊列結構按層次遍歷最適宜

　　int LeafKlevel(BiTree bt int k) //求二叉樹bt 的第k(k>) 層上葉子結點個數
　　{if(bt==null || k<) return();
　　BiTree p=btQ[];            //Q是隊列元素是二叉樹結點指針容量足夠大
　　int front=rear=leaf=;  //front 和rear是隊頭和隊尾指針 leaf是葉子結點數
　　int last=level=; Q[]=p; //last是二叉樹同層最右結點的指針level 是二叉樹的層數
　　while(front<=rear)
　　{p=Q[++front];
　　if(level==k && !p>lchild && !p>rchild) leaf++; //葉子結點
　　if(p>lchild) Q[++rear]=p>lchild;                //左子女入隊
　　if(p>rchild) Q[++rear]=p>rchild;               //右子女入隊
　　if(front==last) {level++;       //二叉樹同層最右結點已處理層數增
　　last=rear; }   //last移到指向下層最右一元素
　　if(level>k) return (leaf);               //層數大於k 後退出運行
　　}//while  }//結束LeafKLevel

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

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