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

　　TYPE bitreptr=^binode;
　　binode=RECORD data:ElemType; lchildrchlid:bitreptr END;
　　PROC PreOrder(bt:bitreptr);  //非遞歸前序遍列二叉樹
　　VAR S:ARRAY[max] OF bitreptr;    //max是棧容量足夠大
　　inits(S);//棧初始化
　　WHILE (bt<>NIL) OR (NOT empty(S)) DO
　　[WHILE (bt<>NIL )DO
　　[write(bt↑data); push(Sbt>rchild); bt:=bt↑lchild;]//訪問結點右子女進棧
　　WHILE (NOT empty(S) AND top(S)=NIL) bt:=pop(S);// 退棧
　　IF NOT empty(S) THEN bt:=pop(S);
　　] ENDP;

　　[算法討論]若不要求使用top(S)以上算法還可簡化

　　[題目分析]二叉樹采取順序結構存儲是按完全二叉樹格式存儲的對非完全二叉樹要補上虛結點由於不是完全二叉樹在順序結構存儲中對葉子結點的判定是根據其左右子女為葉子和雙親結點下標間的關系滿足完全二叉樹的性質

　　int Leaves(int h)  //求深度為h以順序結構存儲的二叉樹的葉子結點數
　　{int BT[]; int len=h count=; //BT是二叉樹結點值一維數組容量為h
　　for (i=;i<=len;i++) //數組元素從下標開始存放
　　if (BT[i]!=)      //假定二叉樹結點值是整數虛結點用填充
　　if(i*)>len) count++;                        //第i個結點沒子女肯定是葉子
　　else if(BT[*i]== && *i+<=len && BT[*i+]==) count++; //無左右子女的結點是葉子
　　return (count)
　　} //結束Leaves

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

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