二叉樹迭代器算法

二叉樹(Binary Tree)的前序、中序和后續遍歷是算法和數據結構中的基本問題，基于遞歸的二叉樹遍歷算法更是遞歸的經典應用。

假設二叉樹結點定義如下：

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序遞歸遍歷算法：

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

前序和后序遍歷算法類似。

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

int sum(Iterator it)

鏈表作為一種線性結構，它的迭代器實現非常簡單和直觀，而二叉樹的迭代器實現則不那么容易，我們不能直接將遞歸遍歷轉換為迭代器。究其原因，這是因為二叉樹遞歸遍歷過程是編譯器在調用棧上自動進行的，程序員對這個過程缺乏足夠的控制。既然如此，那么我們如果可以自己來控制整個調用棧的進棧和出棧不是就達到控制的目的了嗎？我們先來看看二叉樹遍歷的非遞歸算法：

// C++
void inorder_traverse_nonrecursive(Node *node) {
    Stack stack;
    do {
        // node代表當前準備處理的子樹，層層向下把左孩子壓棧，對應遞歸算法的左子樹遞歸
        while (NULL != node) {
            stack.push(node);
            node = node->left;
        }
        do {
            Node *top = stack.top();
            stack.pop(); //彈出棧頂，對應遞歸算法的函數返回
            do_something(top);
            if (NULL != top->right) {
                node = top->right; //將當前子樹置為剛剛遍歷過的結點的右孩子，對應遞歸算法的右子樹遞歸
                break;
            }
        }
        while (!stack.empty());
    }
    while (!stack.empty());
}

通過基于棧的非遞歸算法我們獲得了對于遍歷過程的控制，下面我們考慮如何將其封裝為迭代器呢？ 這里關鍵在于理解遍歷的過程是由棧的狀態來表示的，所以顯然迭代器內部應該包含一個棧結構，每次迭代的過程就是對棧的操作。假設迭代器的接口為：

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

下面是一個二叉樹中序遍歷迭代器的實現：

//C++
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;
};

下面我們再來考察一下這個迭代器實現的時間和空間復雜度。很顯然，由于棧中最多需要保存所有的結點，所以其空間復雜度是O(n)的。那么時間復雜度呢？一次next()調用也最多會進行n次棧操作，而整個遍歷過程需要調用n次next()，那么是不是整個迭代器的時間復雜度就是O(n^2)呢？答案是否定的！因為每個結點只會進棧和出棧一次，所以整個迭代過程的時間復雜度依然為O(n)。其實，這和遞歸遍歷的時空復雜度完全一樣。

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

// 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區別的一種通俗解釋是yield返回時系統會保留函數調用的狀態，下次該函數被調用時會接著從上次的執行點繼續執行，這是一種與棧語義所完全不同的流程控制語義。我們知道Python的解釋器是C寫的，但是C并不支持yield語義，那么解釋器是如何做到對yield的支持的呢？ 有了上面把遞歸遍歷變換為迭代遍歷的經驗，相信你已經猜到Python解釋器一定是對yield代碼進行了某種變換。如果你已經能夠實現遞歸變非遞歸，不妨嘗試一下能否寫一段編譯程序將yield代碼變換為非yield代碼。

轉自：http://coolshell.cn/articles/9886.html