二叉树的遍历按照根、左子树、右子树的访问先后顺序不同，一共有6种访问方案。但实际使用时，一般都固定先访问左子树再访问右子树，在这个前提下，根据根结点的访问顺序，一共有三种访问方案：前序遍历（中-左-右），中序遍历（左-中-右），后序遍历（左-右-中）。

接下来以下面这个二叉树定义来进行遍历：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

前序遍历

递归方式：

void preorder(TreeNode *root) {
    if(!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

非递归方式：

void preorder(TreeNode *root) {
    stack<TreeNode*> stk;
    TreeNode *cur = root;
    while(cur || !stk.empty()) {
        while(cur) {
            cout << cur->val << " ";
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        cur = cur->right;
    }
}

中序遍历

递归方式：

void inorder(TreeNode *root) {
    if(!root) return;
    preorder(root->left);
    cout << root->val << " ";
    preorder(root->right);
}

非递归方式：

void inorder(TreeNode *root) {
    stack<TreeNode*> stk;
    TreeNode *cur = root;
    while(cur || !stk.empty()) {
        while(cur) {
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        cout << cur->val << " ";
        cur = cur->right;
    }
}

后序遍历

递归方式：

void postorder(TreeNode *root) {
    if(!root) return;
    preorder(root->left);
    preorder(root->right);
    cout << root->val << " ";
}

非递归方式：

void postorder(TreeNode *root) {
    stack<TreeNode*> stk;
    TreeNode *cur = root;
    TreeNode *prev = nullptr;
    while(cur || !stk.empty()) {
        while(cur) {
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        if(cur->right && cur->right != prev) {
            cur = cur->right;
        } else {
            stk.pop();
            cout << cur->val << " ";
            prev = cur;
            cur = nullptr;
        }
    }
}

按层遍历

void levelorder(TreeNode *root) {
    if(!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        int size = q.size();
        for(int i = 0; i < size; i++) {
            TreeNode *node = q.front();
            q.pop();
            cout << node->val << " ";
            if(node->left) {
                q.push(node->left);
            }
            if(node->right) {
                q.push(node->right);
            }
        }
    }
}




  • 无标签