浅谈二叉树的递归和非递归遍历

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。二叉树的遍历也分为递归遍历和非递归遍历。

一、二叉树的递归遍历

二叉树的递归遍历相对于非递归遍历比较简单，具体实现如下：

// 递归版

// 先序遍历

void printPreorder1(TreeNode* head){

    if (head == nullptr){

        return;

    }

    cout << head->value << " ";

    printPreorder1(head->left);

    printPreorder1(head->right);

}

// 中序遍历

void printInorder1(TreeNode* head){

    if (head == nullptr){

        return;

    }

    printInorder1(head->left);

    cout << head->value << " ";

    printInorder1(head->right);

}

// 后序遍历

void printPostorder1(TreeNode* head){

    if (head == nullptr){

        return;

    }

    printPostorder1(head->left);

    printPostorder1(head->right);

    cout << head->value << " ";

}

二、二叉树的非递归遍历

首先我们要清楚，任何算法的递归版本都可以改成非递归版本，因为函数递归调用其实质就是压栈的过程，那么我们完全可以使用堆栈来模拟这个过程！

1.先序遍历

我们将数的每个节点压入栈中，由于是先序遍历，首先压入的是根节点，然后弹出（弹出节点时打印信息，且一个循环弹出一个节点），接着是压入右子树节点，最后压入左子树节点。为什么要这样呢？由于堆栈是“先进后出”结构，我们想要先打印左子树，因此最后压入左子树，循环这个过程，就达到了我们的目的。

// 迭代版

void printPreorder2(TreeNode* head){

    cout << "Pre Order:" << endl;

    if (head != nullptr){

        stack<TreeNode*> *sta = new stack<TreeNode*>;

        sta->push(head);

        TreeNode* cur = head;

        while(!sta->empty()){

            cur = sta->top();

            sta->pop();

            cout << cur->value << " ";

            if (cur->right != nullptr){

                sta->push(cur->right);

            }

            if (cur->left != nullptr){

                sta->push(cur->left);     // 先压右边节点，再压左边节点，这与栈的特性有关

            }

        }

    }

    cout << endl;

}

2.中序遍历

中序时，我们首先去遍历二叉树的左分支，并将节点压入栈中，只到找到最左边的叶节点，接着弹出（并打印节点），并看其有没右分支，如果没有，栈再弹出一个节点（根节点），看其有没有右分支。每次弹出，都要观察其是否有右分支，也就是说每个节点都遍历了两次！

void printInorder2(TreeNode* head){

     cout << "In Order:" << endl;

     if(head != nullptr){

         stack<TreeNode*>* sta = new stack<TreeNode*>;

         TreeNode* cur = head;

         while(!sta->empty() || cur != nullptr){

             if(cur != nullptr){

                sta->push(cur);

                cur = cur->left;

             }else{

                cur = sta->top();

                sta->pop();

                cout << cur->value << " ";

                cur = cur->right;

             }

         }

     }

     cout << endl;

}

3.后序遍历

后序遍历在意思上和前序遍历相近，而前序遍历的压栈顺序为：根、右、左。那么如果我们使用两个堆栈，第一个压栈顺序为：根、左、右，但是在（先序遍历时）弹出根节点时将根节点压入第二个堆栈，为什么这里压栈顺序要为左右呢？很简单，在第一个堆栈中最后压入右子树，那么右子树会最先压入第二个堆栈，相应的，当第二个堆栈弹出时，右子树会在左子树的后面弹出（先进后出）。注意：根节点是最先被压入第一个栈中的，同时也是最先被压入第二个栈中的！

void printPostorder2(TreeNode* head){

    cout << "Post Order:" << endl;

    if (head != nullptr){

        stack<TreeNode*>* sta1 = new stack<TreeNode*>;

        stack<TreeNode*>* sta2 = new stack<TreeNode*>;

        TreeNode* cur = head;

        sta1->push(cur);

        while(!sta1->empty()){

            cur = sta1->top();

            sta1->pop();      // 弹出的是最晚被压入栈的数据

            sta2->push(cur);

            if(cur->left != nullptr){

                sta1->push(cur->left);

            }

            if(cur->right != nullptr){

                sta1->push(cur->right);

            }

        }

        while(!sta2->empty()){

            cur = sta2->top();

            sta2->pop();

            cout << cur->value << " ";

        }

    }

    cout << endl;

}

以上的内容就是关于二二叉树递归遍历和非递归遍历，总的来说，二叉树的递归遍历中，先序遍历、中序遍历、后序遍历的模式都是相同的，而在二叉树非递归遍历中则有所区别。想要深入学习二叉树的小伙伴，可以收藏本站的数据结构和算法教程，里面对二叉树的讲解十分透彻，让我们 学起二叉树来可以事半功倍。