c++ 先序遍历,中序遍历和后序遍历
时间: 2024-08-13 17:00:47 浏览: 96
在C++中,树和二叉树的遍历有三种基本方式:先序遍历、中序遍历和后序遍历,它们都是用于访问树的所有节点的一种顺序。
1. **先序遍历** (Preorder Traversal):
- 首先访问根节点;
- 然后递归遍历左子树;
- 最后递归遍历右子树。
示例(对于一个二叉树):`A -> B -> D -> E -> C -> F`(假设根节点为A)
2. **中序遍历** (Inorder Traversal):
- 首先递归遍历左子树;
- 然后访问根节点;
- 最后递归遍历右子树。
示例(对于一个二叉搜索树):`D -> B -> E -> A -> C -> F`(根节点数值排序后的顺序)
3. **后序遍历** (Postorder Traversal):
- 首先递归遍历左子树;
- 然后递归遍历右子树;
- 最后访问根节点。
示例(对于一个二叉树):`B -> D -> E -> F -> C -> A`
这三种遍历方式通常通过递归或迭代的方式实现,并通过调用函数来完成对每个节点的访问。递归方法更为简洁直观,但可能会消耗更多的栈空间;而迭代方法则需要维护额外的数据结构,如栈,以保存节点状态。
相关问题
c++ 先序中序后序遍历
在C++中,树的先序遍历(前序遍历)、中序遍历和后序遍历是三种基本的遍历方法,它们分别对应于在访问节点和子树时的不同顺序。
1. 先序遍历(Preorder Traversal):先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。遍历顺序为:根 -> 左 -> 右。
2. 中序遍历(Inorder Traversal):首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。遍历顺序为:左 -> 根 -> 右。
3. 后序遍历(Postorder Traversal):首先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。遍历顺序为:左 -> 右 -> 根。
下面是三种遍历方法的C++代码示例:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
int main() {
// 构建一棵树作为示例
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << "先序遍历结果: ";
preorderTraversal(root);
cout << endl;
cout << "中序遍历结果: ";
inorderTraversal(root);
cout << endl;
cout << "后序遍历结果: ";
postorderTraversal(root);
cout << endl;
// 注意:这里没有释放树节点所占用的内存,实际使用时应避免内存泄漏
return 0;
}
```
c++先序遍历,中序遍历,后序遍历代码
在C++中,实现二叉树的先序遍历、中序遍历和后序遍历通常使用递归的方法。以下是一个简单的示例代码,展示了如何分别实现这三种遍历方式:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历(根左右)
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " "; // 访问根节点
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
// 中序遍历(左根右)
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left); // 遍历左子树
cout << root->val << " "; // 访问根节点
inorderTraversal(root->right); // 遍历右子树
}
// 后序遍历(左右根)
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left); // 遍历左子树
postorderTraversal(root->right); // 遍历右子树
cout << root->val << " "; // 访问根节点
}
int main() {
// 创建一个简单的二叉树
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 执行遍历
cout << "Preorder traversal: ";
preorderTraversal(root);
cout << endl;
cout << "Inorder traversal: ";
inorderTraversal(root);
cout << endl;
cout << "Postorder traversal: ";
postorderTraversal(root);
cout << endl;
// 释放内存(在实际应用中,应当确保完全释放分配的内存)
delete root->left->left;
delete root->left->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
```
在这个示例中,我们首先定义了一个二叉树节点的结构体`TreeNode`,然后分别实现了三个遍历函数:`preorderTraversal`、`inorderTraversal`和`postorderTraversal`。每个函数都接收一个指向根节点的指针,并递归地访问和打印节点值。
阅读全文