Re: [問題] 用迴圈來寫後序式運算

看板C_and_CPP (C/C++)作者Makoto0813 (火紅的燃燒吧!妹控魂!)時間16年前 (2010/04/12 18:19)推噓1(1推 0噓 2→)

留言3則, 2人參與討論串2/2 (看更多)

※ 引述《Makoto0813 (火紅的燃燒吧!妹控魂!)》之銘言： : ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 ) : ( 未必需要依照此格式，文章條理清楚即可 ) : 遇到的問題： (題意請描述清楚) : 課本的習題，試用迴圈來完成二元樹的後序式走訪 : #define MAX_SIZE 100; : typedef struct bintree *tree_pointer; : typedef struct bintree{ : int data; : tree_pointer leftchild; : tree_pointer rightchild; : }; : 大致上會用到的全域變數是這些 : 這裡列出前序式的迴圈寫法或許可供參考如下: : void pre_order(tree_pointer node) : { : int top=-1; : tree_pointer stack[MAX_SIZE]; : for(;;){ : for(;node;node=node->leftchild){ : if(node) printf("%d",node->data); : add(&top,node);} : node=delete(&top); : if(!node)break; : node=node->rightchild; : } : } : 爬過板上雖有相關的問題卻沒看到回答，這題我生了一個下午了還是出不來 : 在知識家看到有人提到可以用堆疊和佇列來做，只是他提的演算法 : 要改成程式碼還是霧煞煞@@，節錄演算法內容供參考... : # 如果node(樹根)是NULL, 那表示這樹沒東西. 直接return就行 : # 把node給push進queue裡 : # 用個do…while迴圈(用for或while也行). do…while迴圈從這開始 : # 把queue裡的一個數pop出並存入node裡 : # 如果node的right_c不是NULL的話就把node的right_c給push進queue裡. : # 如果node的left_c不是NULL的話就把node的left_c給push進queue裡. : # 把node給push進stack裡 : # do…while迴圈由此結束. 此迴圈要繼續執行直到queue裡沒東西了. 所以while裡的條件是要檢查queue是否沒東西了. : # 用個迴圈把stack裡的東西一一pop並顯示出來 : 對不起可以求程式碼嗎... 試著照演算法寫了點程式，追過幾次似乎沒辦法求到符合後序追蹤的答案 poste_order(treepointer node){ int top=-1; treepointer stack[SIZE]; int rear,front=0; treepointer queue[SIZE]; if(!node) return(0); else addq(front,&rear,node); while(front!=rear){ node=deleteq(&front,rear); if(node->rightchild) addq(front,&rear,node->rightchild); if(node->leftchild) addq(front,&rear,node->leftchild); add(&top,node);}/*end while*/ while(top>-1){ node=delete(&top) printf("%d",node);} 請問是我理解錯誤還是演算法有少了什麼呢? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.74.232.161