【数据结构-二叉树】二叉树3种遍历的2种实现

这篇文章介绍了二叉树的3种遍历：前序遍历、中序遍历和后序遍历，以及这3种遍历的2种实现：递归实现和迭代实现。代码使用c++编写。

3种遍历

前序遍历、中序遍历以及后序遍历这3种遍历的区别在于访问节点的顺序不同。具体为：

前序遍历：根节点->左子节点->右子节点；
中序遍历：左子节点->根节点->右子节点；
后续遍历：左子节点->右子节点->根节点；

可以看到，3种遍历中，左子节点的顺序一直在右子节点前面，而“前”、“中”、“后”指的是根节点的位置。

节点定义

二叉树中的节点定义如下：

struct Node{
    int val;
    Node* left;
    Node* right;

    Node(int x):val(x),left(nullptr),right(nullptr){}
};

递归实现

前序遍历

前序遍历中节点的访问顺序为：根节点->左子节点->右子节点，使用递归实现的代码如下：

void preOrder(Node* root){
    if(root==nullptr) return;

    cout<<root->val<<" ";
    preOrder(root->left);
    preOrder(root->right);
}

中序遍历

中序遍历类似于前序遍历，将输出的顺序调整一下即可。代码如下：

void inOrder(Node* root){
    if(root==nullptr) return;

    inOrder(root->left);
    cout<<root->val<<" ";
    inOrder(root->right);
}

后序遍历

后序遍历也是调整输出的顺序。代码如下：

void postOrder(Node* root){
    if(root==nullptr) return;

    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val<<" ";
}

迭代实现

前序遍历

使用迭代实现前序遍历需要用栈记录两个状态：当前节点curNode，当前节点是否被访问过hasVisit（hastVisit=1，表示该节点被访问过；hasVisit=0，表示该节点未被访问过）。使用两个栈nodeStack和visit分别记录curNode以及curNode是否被访问过。运行以下算法：

将root压入nodeStack，将0压入visit；
当nodeStack不为空，循环：
- 将nodeStack栈顶元素弹出为curNode，将visit栈顶元素弹出为curNode对应的状态hasVisit;
- 如果hasVisit==1，则输出curNode的值；
- 如果hasVisit==0，则按照前序遍历（根左右）的相反顺序（右左根）压入栈中，也就是将(curNode->right, 0)、(curNode->left, 0)以及(curNode, 1)分别压入nodeStack和visit中。

代码如下：

void preOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<Node*> nodeStack;
    stack<int> visit;
    nodeStack.push(root); visit.push(0);
    while(!nodeStack.empty()){
        Node* curNode = nodeStack.top(); nodeStack.pop();
        int hasVisit = visit.top(); visit.pop();
        if(hasVisit==0){    // 入栈顺序是右、左、中
            if(curNode->right!=nullptr){
                nodeStack.push(curNode->right); visit.push(0);
            }
            if(curNode->left!=nullptr){
                nodeStack.push(curNode->left); visit.push(0);
            }
            nodeStack.push(curNode); visit.push(1);
        }else{
            cout<<curNode->val<<" ";
        }
    }
}

上面的代码将两个状态分别放入两个栈中了，也可以使用stl中的pair将当前结点以及结点的状态组合起来放入一个栈中，代码如下：

void preOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<pair<Node* ,int>> s;
    s.push(make_pair(root, 0));
    while(!s.empty()){
        Node* curNode = s.top().first;
        int hasVisit = s.top().second;
        s.pop();
        if(hasVisit==0){    // 入栈顺序是右、左、中
            if(curNode->right!=nullptr){
                s.push(make_pair(curNode->right, 0));
            }
            if(curNode->left!=nullptr){
                s.push(make_pair(curNode->left, 0));
            }
            s.push(make_pair(curNode, 1));
        }else{
            cout<<curNode->val<<" ";
        }
    }
}

中序遍历

使用迭代进行中序遍历类似于前序遍历，将当hasVisit==0时的入栈顺序改为中序遍历顺序（左根右）的相反序列（右根左）即可。代码如下：

void inOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<Node*> nodeStack;
    stack<int> visit;
    nodeStack.push(root); visit.push(0);
    while(!nodeStack.empty()){
        Node* curNode = nodeStack.top(); nodeStack.pop();
        int hasVisit = visit.top(); visit.pop();
        if(hasVisit==0){    // 入栈顺序是右、左、中
            if(curNode->right!=nullptr){
                nodeStack.push(curNode->right); visit.push(0);
            }
            nodeStack.push(curNode); visit.push(1);
            if(curNode->left!=nullptr){
                nodeStack.push(curNode->left); visit.push(0);
            }
        }else{
            cout<<curNode->val<<" ";
        }
    }
}

后序遍历

后序遍历也是调整hasVisit==0时的入栈顺序：将入栈顺序设置为后序遍历顺序（左右根）的相反序列（根右左）即可。代码如下：

void postOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<Node*> nodeStack;
    stack<int> visit;
    nodeStack.push(root); visit.push(0);
    while(!nodeStack.empty()){
        Node* curNode = nodeStack.top(); nodeStack.pop();
        int hasVisit = visit.top(); visit.pop();
        if(hasVisit==0){    // 入栈顺序是根、右、左
            nodeStack.push(curNode); visit.push(1);
            if(curNode->right!=nullptr){
                nodeStack.push(curNode->right); visit.push(0);
            }
            if(curNode->left!=nullptr){
                nodeStack.push(curNode->left); visit.push(0);
            }
        }else{
            cout<<curNode->val<<" ";
        }
    }
}

总结

对于不同的遍历的迭代方法，只需要更改在hasVisit==0情况下，3个节点的入栈顺序即可：

先序的遍历顺序是中左右，入栈顺序为右左中；
中序的遍历顺序是左中右，入栈顺序为右中左；
后序的遍历顺序是左右中，入栈顺序为中右左；

完整代码

完整代码如下：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct Node{
    int val;
    Node* left;
    Node* right;

    Node(int x):val(x),left(nullptr),right(nullptr){}
};

// 先序构建二叉树，-1表示空节点
Node* createTree(vector<int> v, int& cur){
    if(cur>=v.size()) return nullptr;
    if(v[cur]==-1) return nullptr;

    Node* root = new Node(v[cur]);
    cur++;
    root->left = createTree(v, cur);
    cur++;
    root->right = createTree(v, cur);

    return root;
}

void preOrder(Node* root){
    if(root==nullptr) return;

    cout<<root->val<<" ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(Node* root){
    if(root==nullptr) return;

    inOrder(root->left);
    cout<<root->val<<" ";
    inOrder(root->right);
}

void postOrder(Node* root){
    if(root==nullptr) return;

    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val<<" ";
}

void preOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<Node*> nodeStack;
    stack<int> visit;
    nodeStack.push(root); visit.push(0);
    while(!nodeStack.empty()){
        Node* curNode = nodeStack.top(); nodeStack.pop();
        int hasVisit = visit.top(); visit.pop();
        if(hasVisit==0){    // 入栈顺序是右、左、中
            if(curNode->right!=nullptr){
                nodeStack.push(curNode->right); visit.push(0);
            }
            if(curNode->left!=nullptr){
                nodeStack.push(curNode->left); visit.push(0);
            }
            nodeStack.push(curNode); visit.push(1);
        }else{
            cout<<curNode->val<<" ";
        }
    }
}

/*void preOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<pair<Node* ,int>> s;
    s.push(make_pair(root, 0));
    while(!s.empty()){
        Node* curNode = s.top().first;
        int hasVisit = s.top().second;
        s.pop();
        if(hasVisit==0){    // 入栈顺序是右、左、中
            if(curNode->right!=nullptr){
                s.push(make_pair(curNode->right, 0));
            }
            if(curNode->left!=nullptr){
                s.push(make_pair(curNode->left, 0));
            }
            s.push(make_pair(curNode, 1));
        }else{
            cout<<curNode->val<<" ";
        }
    }
}*/

void inOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<Node*> nodeStack;
    stack<int> visit;
    nodeStack.push(root); visit.push(0);
    while(!nodeStack.empty()){
        Node* curNode = nodeStack.top(); nodeStack.pop();
        int hasVisit = visit.top(); visit.pop();
        if(hasVisit==0){    // 入栈顺序是右、左、中
            if(curNode->right!=nullptr){
                nodeStack.push(curNode->right); visit.push(0);
            }
            nodeStack.push(curNode); visit.push(1);
            if(curNode->left!=nullptr){
                nodeStack.push(curNode->left); visit.push(0);
            }
        }else{
            cout<<curNode->val<<" ";
        }
    }
}

void postOrderByIter(Node* root) {
    if(root==nullptr) return;

    stack<Node*> nodeStack;
    stack<int> visit;
    nodeStack.push(root); visit.push(0);
    while(!nodeStack.empty()){
        Node* curNode = nodeStack.top(); nodeStack.pop();
        int hasVisit = visit.top(); visit.pop();
        if(hasVisit==0){    // 入栈顺序是根、右、左
            nodeStack.push(curNode); visit.push(1);
            if(curNode->right!=nullptr){
                nodeStack.push(curNode->right); visit.push(0);
            }
            if(curNode->left!=nullptr){
                nodeStack.push(curNode->left); visit.push(0);
            }
        }else{
            cout<<curNode->val<<" ";
        }
    }
}

int main(){
    vector<int> v({1, 2, 3, -1, -1, 4, -1, -1, 5, -1, -1});    // 先序构建二叉树，-1表示空节点
    int cur = 0;
    Node* root = createTree(v, cur);
    preOrder(root);
    cout<<endl;

    inOrder(root);
    cout<<endl;

    postOrder(root);
    cout<<endl;

    preOrderByIter(root);
    cout<<endl;

    inOrderByIter(root);
    cout<<endl;

    postOrderByIter(root);
    cout<<endl;

    return 0;
}

上面代码构建的二叉树为：

输出为：