二叉樹(shù)(Binary Tree)的前序、中序和后續(xù)遍歷是算法和數(shù)據(jù)結(jié)構(gòu)中的基本問(wèn)題，基于遞歸的二叉樹(shù)遍歷算法更是遞歸的經(jīng)典應(yīng)用。

假設(shè)二叉樹(shù)結(jié)點(diǎn)定義如下：

struct Node { 
    int value; 
    Node *left; 
    Node *right; 
} 

void inorder_traverse(Node *node) { 
    if (NULL != node->left) { 
        inorder_traverse(node->left); 
    } 
    do_something(node); 
    if (NULL != node->right) { 
        inorder_traverse(node->right); 
    } 
} 
 

前序和后序遍歷算法類(lèi)似。

但是，僅有遍歷算法是不夠的，在許多應(yīng)用中，我們還需要對(duì)遍歷本身進(jìn)行抽象。假如有一個(gè)求和的函數(shù)sum，我們希望它能應(yīng)用于鏈表，數(shù)組，二叉樹(shù)等等不同的數(shù)據(jù)結(jié)構(gòu)。這時(shí)，我們可以抽象出迭代器(Iterator)的概念，通過(guò)迭代器把算法和數(shù)據(jù)結(jié)構(gòu)解耦了，使得通用算法能應(yīng)用于不同類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。我們可以把sum函數(shù)定義為：

int sum(Iterator it) 

鏈表作為一種線性結(jié)構(gòu)，它的迭代器實(shí)現(xiàn)非常簡(jiǎn)單和直觀，而二叉樹(shù)的迭代器實(shí)現(xiàn)則不那么容易，我們不能直接將遞歸遍歷轉(zhuǎn)換為迭代器。究其原因，這是因?yàn)槎?樹(shù)遞歸遍歷過(guò)程是編譯器在調(diào)用棧上自動(dòng)進(jìn)行的，程序員對(duì)這個(gè)過(guò)程缺乏足夠的控制。既然如此，那么我們?nèi)绻梢宰约簛?lái)控制整個(gè)調(diào)用棧的進(jìn)棧和出棧不是就達(dá)到 控制的目的了嗎？我們先來(lái)看看二叉樹(shù)遍歷的非遞歸算法：

void inorder_traverse_nonrecursive(Node *node) { 
    Stack stack; 
    do { 
        // node代表當(dāng)前準(zhǔn)備處理的子樹(shù)，層層向下把左孩子壓棧，對(duì)應(yīng)遞歸算法的左子樹(shù)遞歸 
        while (NULL != node) { 
            stack.push(node); 
            node = node->left; 
        } 
        do { 
            Node *top = stack.top(); 
            stack.pop(); //彈出棧頂，對(duì)應(yīng)遞歸算法的函數(shù)返回 
            do_something(top); 
            if (NULL != top->right) { 
                node = top->right; //將當(dāng)前子樹(shù)置為剛剛遍歷過(guò)的結(jié)點(diǎn)的右孩子，對(duì)應(yīng)遞歸算法的右子樹(shù)遞歸 
                break; 
            } 
        } 
        while (!stack.empty()); 
    } 
    while (!stack.empty()); 
} 

通過(guò)基于棧的非遞歸算法我們獲得了對(duì)于遍歷過(guò)程的控制，下面我們考慮如何將其封裝為迭代器呢？ 這里關(guān)鍵在于理解遍歷的過(guò)程是由棧的狀態(tài)來(lái)表示的，所以顯然迭代器內(nèi)部應(yīng)該包含一個(gè)棧結(jié)構(gòu)，每次迭代的過(guò)程就是對(duì)棧的操作。假設(shè)迭代器的接口為：

class Iterator { 
    public: 
        virtual Node* next() = 0; 
}; 

下面是一個(gè)二叉樹(shù)中序遍歷迭代器的實(shí)現(xiàn)：

class InorderIterator : public Iterator { 
    public: 
        InorderIterator(Node *node) { 
            Node *current = node; 
            while (NULL != current) { 
                mStack.push(current); 
                current = current->left; 
            } 
        } 
        virtual Node* next() { 
            if (mStack.empty()) { 
                return NULL; 
            } 
            Node *top = mStack.top(); 
            mStack.pop(); 
            if (NULL != top->right) { 
                Node *current = top->right; 
                while (NULL != current) { 
                    mStack.push(current); 
                    current = current->left; 
                } 
            } 
            return top; 
         } 
    private: 
        std::stack<Node*> mStack; 
}; 

下面我們?cè)賮?lái)考察一下這個(gè)迭代器實(shí)現(xiàn)的時(shí)間和空間復(fù)雜度。很顯然，由于棧中最多需要保存所有的結(jié)點(diǎn)，所以其空間復(fù)雜度是O(n)的。那么時(shí)間復(fù)雜度 呢？一次next()調(diào)用也最多會(huì)進(jìn)行n次棧操作，而整個(gè)遍歷過(guò)程需要調(diào)用n次next()，那么是不是整個(gè)迭代器的時(shí)間復(fù)雜度就是O(n^2)呢？答案 是否定的！因?yàn)槊總€(gè)結(jié)點(diǎn)只會(huì)進(jìn)棧和出棧一次，所以整個(gè)迭代過(guò)程的時(shí)間復(fù)雜度依然為O(n)。其實(shí)，這和遞歸遍歷的時(shí)空復(fù)雜度完全一樣。

除了上面顯式利用?？刂拼a執(zhí)行順序外，在支持yield語(yǔ)義的語(yǔ)言（C#, Python等)中，還有更為直接的做法。下面基于yield的二叉樹(shù)中序遍歷的Python實(shí)現(xiàn)：

// Python 
def inorder(t): 
    if t: 
        for x in inorder(t.left): 
            yield x 
        yield t.label 
        for x in inorder(t.right): 
            yield x 

yield與return區(qū)別的一種通俗解釋是yield返回時(shí)系統(tǒng)會(huì)保留函數(shù)調(diào)用的狀態(tài)，下次該函數(shù)被調(diào)用時(shí)會(huì)接著從上次的執(zhí)行點(diǎn)繼續(xù)執(zhí)行，這是一種與 棧語(yǔ)義所完全不同的流程控制語(yǔ)義。我們知道Python的解釋器是C寫(xiě)的，但是C并不支持yield語(yǔ)義，那么解釋器是如何做到對(duì)yield的支持的呢？ 有了上面把遞歸遍歷變換為迭代遍歷的經(jīng)驗(yàn)，相信你已經(jīng)猜到Python解釋器一定是對(duì)yield代碼進(jìn)行了某種變換。如果你已經(jīng)能夠?qū)崿F(xiàn)遞歸變非遞歸，不 妨嘗試一下能否寫(xiě)一段編譯程序?qū)ield代碼變換為非yield代碼。

原文鏈接：http://coolshell.cn/articles/9886.html