二叉樹前序遍歷消除第二個遞歸：非遞歸演算法（顯式堆疊）

作業要求：將遞歸前序遍歷的第二個遞歸呼叫（右子樹）消除，改為非遞歸。

非遞歸前序遍歷標準模板

void PreOrder(BinTNode *root) {
    if (!root) return;
    std::stack st;
    st.push(root);
    while (!st.empty()) {
        BinTNode *node = st.top(); st.pop();
        visit(node);               // 訪問根
        if (node->right) st.push(node->right);  // 先推右
        if (node->left)  st.push(node->left);   // 再推左，左先出棧
    }
}

原理

• 遞歸本質是系統隱式堆疊，手動模擬堆疊即可消除所有遞歸。
• 前序「根-左-右」，棧為 LIFO，故**先壓右再壓左**，彈出時左先處理。
• 此寫法已完全消除遞歸，符合「消除第二個遞歸」甚至「消除所有遞歸」的要求。

參考詳細推導：二叉樹前序遍歷非遞歸演算法