【數(shù)據(jù)結(jié)構(gòu)】二叉樹(前、中、后）序遍歷的遞歸與非遞歸算法

對(duì)于二叉樹，有前序、中序以及后序三種遍歷方法。因?yàn)闃涞亩x本身就是遞歸定義，因此采用遞歸的方法去實(shí)現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡(jiǎn)潔。而對(duì) 于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實(shí)現(xiàn)。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實(shí)現(xiàn)，非遞歸后序遍歷實(shí)現(xiàn)起來(lái)相對(duì)來(lái)說(shuō)要難一 點(diǎn)。

二叉樹前序：訪問(wèn)根節(jié)點(diǎn)->左子樹->右子樹

（1）遞歸寫法：

依次訪問(wèn)根節(jié)點(diǎn)、左子樹、右子樹，注意遞歸出口的結(jié)束。

void _PrevOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        cout << root->_data << "  ";
        _PrevOrder(root->_left);
        _PrevOrder(root->_right);
    }

（2）非遞歸寫法：

用棧模擬前序遍歷，棧是先進(jìn)后出的特點(diǎn)，則將無(wú)條件地入棧根節(jié)點(diǎn)，在彈出根節(jié)點(diǎn)之前依次將根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)和左孩子節(jié)點(diǎn)入棧……

void _PrevOrder(Node* root)
    {
        stack<Node*> s;
        if (root == NULL)
        {
            return;
        }

        s.push(root);
        while (!s.empty())
        {
            root = s.top();
            cout << root->_data << "  ";
            s.pop();
            if (root->_right)
            {
                s.push(root->_right);
            }
            if (root->_left)
            {
                s.push(root->_left);
            }
        }
    }

二叉樹中序：訪問(wèn)左子樹->根節(jié)點(diǎn)->右子樹

（1）遞歸寫法：

依次訪問(wèn)左子樹、根節(jié)點(diǎn)、右子樹，注意遞歸出口的結(jié)束。

void _InOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_data << "  ";
        _InOrder(root->_right);
    }

（2）非遞歸寫法：

1、借助棧實(shí)現(xiàn)，先順著二叉樹找到最左邊且最下邊的節(jié)點(diǎn)3（一邊找一邊入棧），此時(shí)入棧序列為1，2，3。

2、此時(shí)按照中序遍歷知道要彈出棧頂元素3，則彈出棧頂元素3。

3、下面該右子樹了，那我們就要判斷它的右子樹是否為空，

      若為空，往回返，該打印2了，那就彈出棧頂元素2。

      若不為空，該右子樹，指針指向右子樹節(jié)點(diǎn)，再重復(fù)之前的步驟1，2，3……

void _InOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        stack<Node*> s;
        Node* cur = root;
      
        while (cur || !s.empty())
        {
            while (cur)
            {            
                s.push(cur);                
                cur = cur->_left;
            }

            cur = s.top();    //將棧頂元素保存，以便于后面判斷它是否有右孩子
            cout << s.top()->_data << "  ";        
            s.pop();

            if (cur->_right == NULL)
            {
                cur = NULL;
            }
            else
            {
                cur = cur->_right;
            }
        }
    }

二叉樹后序：訪問(wèn)左子樹->右子樹->根節(jié)點(diǎn)

（1）遞歸寫法：

依次訪問(wèn)左子樹、右子樹、根節(jié)點(diǎn)，注意遞歸出口的結(jié)束。

void _PostOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _PostOrder(root->_left);
        _PostOrder(root->_right);
        cout << root->_data << "  ";
    }

（2）非遞歸寫法：

1、后序遍歷同樣借助棧實(shí)現(xiàn)，先找到最左邊且為最下面的節(jié)點(diǎn)3（一邊入棧一邊找）。

2、節(jié)點(diǎn)3若沒(méi)有右孩子，那此時(shí)就打印節(jié)點(diǎn)3了，之后就彈出棧頂節(jié)點(diǎn)3

3、節(jié)點(diǎn)3若有右孩子，則要去繼續(xù)遍歷它的右子樹，等遍歷結(jié)束才可打印3.遍歷重復(fù)步驟1，2，3……

void _PostOrderNon_R(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        Node* cur = root;
        Node* prev = NULL;
        stack<Node*> s;
        
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);                
                cur = cur->_left;                
            }
            
            cur = s.top();
            if (cur->_right == NULL ||cur->_right==prev )
            {
                cout << cur->_data << "  ";
                s.pop();
                prev = cur;
                cur = NULL;
            }
            else
            {
                cur = cur->_right;
            }
        }                
    }