二叉树前序、中序、后序、层序遍历(递归、非递归、Morris遍历) C++语言实现
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
更多推荐






所有评论(0)