pop(s,p);
if(!stackempty(s))
} }
2)中序遍歷
a)遞迴方式
void inorder_recursive(bitree t) /* 中序遍歷二叉樹的遞迴演算法 */
}b)非遞迴方式
void inorder_nonrecursive(bitree t)
}}3)後序遍歷
a)遞迴方式
void postorder_recursive(bitree t) /* 中序遍歷二叉樹的遞迴演算法 */
}b)非遞迴方式
typedef struct mark;
} pmtype; /* 有mark域的結點指標型別 */
void postorder_nonrecursive(bitree t) /* 後續遍歷二叉樹的非遞迴演算法 */
); /* 根結點入棧 */
while(!stackempty(s)) ); /* 訪問左子樹 */
break;
case 1:
push(s,); /* 修改mark域 */
if(>rchild)
push(s,); /* 訪問右子樹 */
break;
case 2:
visit( /* 訪問結點 */
} }
}三、實現遞迴與非遞迴的換轉原理和例子
一）原理分析
通常，乙個函式在呼叫另乙個函式之前，要作如下的事情：a)將實在引數，返回位址等資訊傳遞給被呼叫函式儲存; b)為被呼叫函式的區域性變數分配儲存區;c)將控制轉移到被調函式的入口。
從被呼叫函式返**用函式之前，也要做三件事情：a)儲存被調函式的計算結果;b)釋放被調函式的資料區;c)依照被調函式儲存的返回位址將控制轉移到呼叫函式。所有的這些，不論是變數還是位址，本質上來說都是」資料」，都是儲存在系統所分配的棧中的。
ok，到這裡已經解決了第乙個問題：遞迴呼叫時資料都是儲存在棧中的，有多少個資料需要儲存就要設定多少個棧，而且最重要的一點是：控制所有這些棧的棧頂指標都是相同的，否則無法實現同步。
下面來解決第二個問題：在非遞迴中，程式如何知道到底要轉移到哪個部分繼續執行?回到上面說的樹的三種遍歷方式，抽象出來只有三種操作：
訪問當前結點，訪問左子樹，訪問右子樹。這三種操作的順序不同，遍歷方式也不同。如果我們再抽象一點，對這三種操作再進行乙個概括，可以得到：
a)訪問當前結點：對目前的資料進行一些處理;b)訪問左子樹：變換當前的資料以進行下一次處理;c)訪問右子樹：
再次變換當前的資料以進行下一次處理(與訪問左子樹所不同的方式)。
下面以先序遍歷來說明：
void preorder_recursive(bitree t) /* 先序遍歷二叉樹的遞迴演算法 */
}visit(t)這個操作就是對當前資料進行的處理， preorder_recursive(t->lchild)就是把當前資料變換為它的左子樹，訪問右子樹的操作可以同樣理解了。
現在回到我們提出的第二個問題：如何確定轉移到**繼續執行?關鍵在於一下三個地方：
a)確定對當前資料的訪問順序，簡單一點說就是確定這個遞迴程式可以轉換為哪種方式遍歷的樹結構;b)確定這個遞迴函式轉換為遞迴呼叫樹時的分支是如何劃分的，即確定什麼是這個遞迴呼叫樹的」左子樹」和」右子樹」c)確定這個遞迴呼叫樹何時返回，即確定什麼結點是這個遞迴呼叫樹的」葉子結點」。
二）兩個例子
好了上面的理論知識已經足夠了，下面讓我們看看幾個例子，結合例子加深我們對問題的認識。即使上面的理論你沒有完全明白，不要氣餒，對事物的認識總是曲折的，多看多想你一定可以明白(事實上我也是花了兩個星期的時間才弄得比較明白得)。
1)例1：
f(n) = n + １; (n <２)
= f[n/2] + f[n/4](n >= 2);
這個例子相對簡單一些，遞迴程式如下：
int f_recursive(int n)
{ int u1, u2, f;
if (n < 2)
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...
資料結構與演算法信
美國uiuc大學博士生梅俏竹 資料結構是美國所有一流計算機系的本科核心課程之一，上承計算引論與初級程式設計，下啟高階演算法和計算理論，向來是計算機本科教學的重中之重。我在北大上過的諸多本科基礎課中，無論從課程內容和老師教學下的功夫來看，張銘老師的 資料結構與演算法 課程都是首屈一指的。可以說，將北大...