1. 四种遍历方式简单介绍

在这里插入图片描述

2. 实例说明

在这里插入图片描述

3. 树结构定义

struct TreeNode {
    int val;
    TreeNode *left, *right;	// 左右孩子指针
    // 构造函数
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
    TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
};

4. 层次遍历

  • 层次遍历使用队列来实现,也可以理解为对二叉树从根节点进行广度优先搜索。
  • 时间复杂度O(n), 借助队列来进行遍历,空间复杂度O(n)

基本流程如下

1. 将根结点 root 加入队列q
2. 取出队首结点,访问它。
3. 如果该结点有左孩子,将左孩子入队。
4. 如果该结点有右孩子,将右孩子入队。
5. 队列为空时停止。

代码实现:

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right; // 左右孩子指针
    // 构造函数
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
    TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
};

// 二叉树的创建, 按先序次序输入二叉树中结点的值,-1表示空
TreeNode *buildBiTree() {
    int val
    cin >> val;
    if (val == -1) return nullptr;
    return new TreeNode(val, buildBiTree(), buildBiTree());
}

vector<int> arr;  // 存放遍历结果

void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);   // 根节点入队
    while (!q.empty()) {    // 队列不为空
        TreeNode *cur = q.front();  // 取出队头元素
        q.pop();    // 弹出、千万不要忘记!
        arr.push_back(cur->val);  // 保存节点值
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

// 输入:1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
int main() {
    TreeNode* root = buildBiTree();  // 创建二叉树
    levelOrder(root);   // 层次遍历
    for (int x : arr) cout << x << ' ';  // 输出遍历结果
    return 0;
}

5. 先、中、后序递归遍历

  • 递归实现代码比较简单,关键是何时保存节点的值。先序遍历:保存节点的值在遍历左、右子树之前; 中序遍历:保存节点的值在遍历左、右子树中间; 后序遍历 保存节点的值在遍历左、右子树之后。

  • 时间复杂度O(n), 递归过程中需要使用栈空间,空间复杂度O(n)

代码实现

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right; // 左右孩子指针
    // 构造函数
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
    TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
};

vector<int> arr;  // 存放遍历结果

// 二叉树的创建, 按先序次序输入二叉树中结点的值,-1表示节点位空
TreeNode *buildBiTree() {
    int val;
    cin >> val;
    if (val == -1) return nullptr;
    return new TreeNode(val, buildBiTree(), buildBiTree());
}

// 前序遍历二叉树
void preOrder(TreeNode *root) {
    if (root == nullptr) return;
    arr.push_back(root->val);  // 保存节点的值在前
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历二叉树
void inOrder(TreeNode *root) {
    if (root == nullptr) return;
    inOrder(root->left);
    arr.push_back(root->val);  // 保存节点的值在中间
    inOrder(root->right);
}

// 后序遍历二叉树
void postOrder(TreeNode *root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    arr.push_back(root->val);  // 保存节点的值在后
}


// 输入:1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
int main() {
    TreeNode* root = buildBiTree();
    preOrder(root);
    for (int x : arr) cout << x << ' ';
    cout << endl; arr.clear();
    
    inOrder(root);
    for (int x : arr) cout << x << ' ';
    cout << endl; arr.clear();

    postOrder(root);
    for (int x : arr) cout << x << ' ';
    return 0;
}

6. 先、中、后序迭代遍历

迭代遍历需要使用栈来模拟递归的过程,实现稍微复杂一点。

先序遍历:入栈前保存节点值。
中序遍历:出栈后保存节点值。
后序遍历实现麻烦一点,以下介绍两种方式

  • 方式1. 使用一个指针变量指向当前正在遍历节点的前一个节点。
  • 方式2. 先求根、右、左的遍历序列,然后反转,得到 左、右、根的遍历序列。与先序遍历递归类似,只需交换遍节时访问左右节点的次序。>时间复杂度 O(n), 空间复杂度O(n)

代码实现

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right; // 左右孩子指针
    // 构造函数
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
    TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
};

vector<int> arr;  // 存放遍历结果

// 二叉树的创建, 按先序次序输入二叉树中结点的值,-1表示空树
TreeNode *buildBiTree() {
    int val;
    cin >> val;
    if (val == -1) return nullptr;
    return new TreeNode(val, buildBiTree(), buildBiTree());
}


// 先序遍历二叉树-迭代
void preOrder(TreeNode *root) {
    stack<TreeNode *> stk;
    while (root || !stk.empty()) {
        while (root) {  // 以root为根的树,不断向左直到为空
            arr.push_back(root->val);     // 入栈前保存节点值
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        root = root->right;   // 遍历右子树
    }
}

// 中序遍历二叉树-迭代
void inOrder(TreeNode *root) {
    stack<TreeNode *> stk;
    while (root || !stk.empty()) {
        while (root) {  // 以root为根的树,不断向左直到为空
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        arr.push_back(root->val);  // 出栈后保存节点值
        root = root->right;   // 遍历右子树
    }
}

// 先按照根、右、左遍历,然后反转, (与先序遍历类似,只需左右交换下顺序)
void postOrder(TreeNode* root) {
    stack<TreeNode*> stk;
    while (root || !stk.empty()) {
        while (root) {
            arr.push_back(root->val);
            stk.push(root);
            root = root->right;  // 注意! 这里是先访问右侧节点
        }
        root = stk.top();
        stk.pop();
        root = root->left;	// 这里顺序也发生改变, 遍历左子树
    }
    reverse(arr.begin(), arr.end());
}

// 后序遍历二叉树-迭代,使用栈模拟
void postOrder2(TreeNode *root) {
    stack<TreeNode *> stk;
    TreeNode *prev = nullptr;
    while (root || !stk.empty()) {
        while (root) {  // 以root为根的树,不断向左直到为空
            stk.push(root);
            root = root->left;
        }
        root = stk.top();   // 取出栈顶元素
        stk.pop();
        if (!root->right || root->right == prev) {  // 右子树已经遍历过
            arr.push_back(root->val);
            prev = root;
            root = nullptr;  // 设置位空, 下次访问新的栈顶元素
        } else {   // 右子树没有被访问,先访问右子树
            stk.push(root);
            root = root->right;
        }
    }
}

// 输入: 1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
int main() {
    TreeNode* root = buildBiTree();
    preOrder(root);
    for (int x : arr) cout << x << ' ';
    cout << endl; arr.clear();
    
    inOrder(root);
    for (int x : arr) cout << x << ' ';
    cout << endl; arr.clear();

    postOrder(root);
    for (int x : arr) cout << x << ' ';
    cout << endl; arr.clear();

    postOrder2(root);
    for (int x : arr) cout << x << ' ';

    return 0;
}

6. 先、中、后序 morris遍历

以上几种方式的时间复杂度均为O(n), 空间复杂度也位O(n), 而 morris遍历算法 时间复杂度也为O(n), 但空间复杂度为O(1)。当数据量比较大时,morris遍历可以节省许多的内存空间。

算法流程

(1)定义一个遍历指针 cur,指向二叉树的根节点

(2)判断 cur 的左孩子是否为空

  • 如果 cur 的左孩子为空,那么 cur右移(cur = cur.right)
  • 如果 cur 的左孩子不为空,则 cur 存在左子树,找出该左子树上最右节点记为 mostRight
    • 如果mostRight 的右孩子为空,那就让其指向 cur ( mostRight.right = cur ),并左移 cur ( cur = cur.left )
    • 如果mostRight 的右孩子不为空(第二次访问cur, cur的左子树已经遍历完成), 那么让 cur 右移( cur = cur.right ),并将 mostRight 的右孩子置空

(3)重复步骤(2),直到 cur 为空

示例:

在这里插入图片描述

若节点node的左孩子不为空,则node会被访问两次,否则node被访问一次。

  • 先序遍历:节点cur左子树不为空,第1次访问节点cur,保存节点值;左子树为空时保存节点值

  • 中序遍历:节点cur左子树不为空,第2次访问节点cur,保存节点值;左子树为空时保存节点值

  • 后序遍历:实现复杂一点,以下代码的 后序遍历 首先得到 根、右、左遍历序列,然后将遍历结果反转,得到 根、左、右遍历序列。

代码实现:

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right; // 左右孩子指针
    // 构造函数
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
    TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
};

vector<int> arr;  // 存放遍历结果

// 二叉树的创建, 按先序次序输入二叉树中结点的值,-1表示空树
TreeNode *buildBiTree() {
    int val;
    cin >> val;
    if (val == -1) return nullptr;
    return new TreeNode(val, buildBiTree(), buildBiTree());
}

// morris先序遍历二叉树
void preOrder(TreeNode* root) {
    TreeNode *cur = root, *p = nullptr;
    while (cur) {
        if (cur->left) {    // 若左子树不为空, 找到左子树的最右侧节点
            p = cur->left;
            while (p->right != nullptr && p->right != cur) {
                p = p->right;
            }
            if (p->right == nullptr) {
                arr.push_back(cur->val);	// 先序:cur左子树不为空,第1次访问节点cur,保存节点值
                p->right = cur;
                cur = cur->left;
            } else {    // p->right == cur
                p->right = nullptr;
                cur = cur->right;
            }
        } else {    // 左子树为空
            arr.push_back(cur->val);	// 保存节点值
            cur = cur->right;
        }
    }
}

// morris中序遍历二叉树
void inOrder(TreeNode* root) {
    TreeNode *cur = root, *p = nullptr;
    while (cur) {
        if (cur->left) {    // 若左子树不为空, 找到左子树的最右侧节点
            p = cur->left;
            while (p->right != nullptr && p->right != cur) {
                p = p->right;
            }
            if (p->right == nullptr) {
                p->right = cur;
                cur = cur->left;
            } else {    // p->right == cur
                arr.push_back(cur->val);	// 中序:cur左子树不为空,第2次访问节点cur,保存节点值
                p->right = nullptr;
                cur = cur->right;
            }
        } else {    // 左子树为空
            arr.push_back(cur->val);  // 保存节点值
            cur = cur->right;
        }
    }
}

// morris后序遍历二叉树, 先求 (根、右、左)遍历次序,然后反转就到的 (左、右、根)
void postOrder(TreeNode* root) {	// 此处代码与先序遍历相反,先右子树、再左子树
    TreeNode *cur = root, *p = nullptr;
    while (cur) {
        if (cur->right) {    // 若左子树不为空, 找到左子树的最右侧节点
            p = cur->right;
            while (p->left != nullptr && p->left != cur) {
                p = p->left;
            }
            if (p->left == nullptr) {
                arr.push_back(cur->val);	// cur右子树不为空,第1次访问节点cur,保存节点值
                p->left = cur;
                cur = cur->right;
            } else { 
                p->left = nullptr;
                cur = cur->left;
            }
        } else {
            arr.push_back(cur->val);
            cur = cur->left;
        }
    }
    reverse(arr.begin(), arr.end());	// 将结果反转、得到 左、右、根遍历序列
}

// 输入:1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
int main() {
    TreeNode* root = buildBiTree();
    preOrder(root);
    for (int x : arr) cout << x << ' ';
    cout << endl; arr.clear();
    
    inOrder(root);
    for (int x : arr) cout << x << ' ';
    cout << endl; arr.clear();

    postOrder(root);
    for (int x : arr) cout << x << ' ';

    return 0;
}

运行结果

在这里插入图片描述

7. 参考文章链接

https://zhuanlan.zhihu.com/p/101321696

https://leetcode.cn/problems/binary-tree-postorder-traversal/solution/morrisbian-li-suan-fa-jie-xi-qian-xu-bia-dt2x/

https://www.cnblogs.com/wyb666/p/10335726.html

更多推荐