二叉树三种遍历方式——前序、中序、后序（C++）

以下是使用C++实现的二叉树前序、中序和后序遍历的递归方法示例：

1. #include <iostream>
3. using namespace std;
5. // 二叉树节点结构体
6. struct TreeNode {
7.     int val;
8.     TreeNode* left;
9.     TreeNode* right;
10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11. };
13. // 前序遍历
14. void preOrder(TreeNode* root) {
15.     if (root == nullptr) return;
16.     cout << root->val << " ";
17.     preOrder(root->left);
18.     preOrder(root->right);
19. }
21. // 中序遍历
22. void inOrder(TreeNode* root) {
23.     if (root == nullptr) return;
24.     inOrder(root->left);
25.     cout << root->val << " ";
26.     inOrder(root->right);
27. }
29. // 后序遍历
30. void postOrder(TreeNode* root) {
31.     if (root == nullptr) return;
32.     postOrder(root->left);
33.     postOrder(root->right);
34.     cout << root->val << " ";
35. }
37. int main() {
38.     // 构建示例二叉树
39.     //       1
40.     //     /   \
41.     //    2     3
42.     //   / \   /
43.     //  4   5 6
44.     TreeNode* root = new TreeNode(1);
45.     root->left = new TreeNode(2);
46.     root->right = new TreeNode(3);
47.     root->left->left = new TreeNode(4);
48.     root->left->right = new TreeNode(5);
49.     root->right->left = new TreeNode(6);
51.     // 输出遍历结果
52.     cout << "前序遍历: ";
53.     preOrder(root);
54.     cout << endl;
56.     cout << "中序遍历: ";
57.     inOrder(root);
58.     cout << endl;
60.     cout << "后序遍历: ";
61.     postOrder(root);
62.     cout << endl;
64.     // 释放内存（简单示例中省略，实际使用时应注意内存管理）
65.     return 0;
66. }

复制代码

输出效果：

1. 前序遍历: 1 2 4 5 3 6
2. 中序遍历: 4 2 5 1 6 3
3. 后序遍历: 4 5 2 6 3 1

复制代码

代码阐明：

• 二叉树结构界说：使用TreeNode结构体表现二叉树的节点，包罗值val和左右子节点指针。
  
• 递归遍历函数：
  
  
  
  • 前序遍历：先访问根节点，然后递归遍历左子树，末了递归遍历右子树。
    
  • 中序遍历：先递归遍历左子树，然后访问根节点，末了递归遍历右子树。
    
  • 后序遍历：先递归遍历左子树，然后递归遍历右子树，末了访问根节点。
    
  
  
• 示例二叉树的构建：手动创建了一个包罗6个节点的二叉树，用于演示遍历效果。
  
• 内存管理：示例中未显式开释内存，实际应用中应根据必要添加delete使用。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。