二叉树的前序、中序、后序遍历的C++实现

二叉树的前序、中序、后序 遍历属于深度优先搜索方式，本文使用递归法实现前序、中序、后序的遍历方法，代码如下：

#include <iostream>
#include <vector>struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(nullptr),right(nullptr){};
};//前序遍历
void preorderTraversal(TreeNode* root,std::vector<int>& vec)
{if(root == nullptr){return;}vec.emplace_back(root->val);preorderTraversal(root->left,vec);preorderTraversal(root->right,vec);
}//中序遍历
void inorderTraversal(TreeNode* root,std::vector<int>& vec)
{if(root == nullptr){return;}preorderTraversal(root->left,vec);vec.emplace_back(root->val);preorderTraversal(root->right,vec);
}//后序遍历
void postOrderTraversal(TreeNode* root,std::vector<int>& vec)
{if(root == nullptr){return;}preorderTraversal(root->left,vec);preorderTraversal(root->right,vec);vec.emplace_back(root->val);
}void deleteTree(TreeNode* root)
{if(root == nullptr){return;}deleteTree(root->left);deleteTree(root->right);delete root;root = nullptr;
}int main()
{//创建二叉树//        1//      /   \//     2     3//    / \   / \//   4  5  6   7//  / \// 8   9//前序遍历：中左右: 1 2 4 8 9 5 3 6 7//中序遍历：左中右: 2 4 8 9 5 1 3 6 7//后序遍历：左右中: 2 4 8 9 5 3 6 7 1TreeNode* 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);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);root->left->left->left = new TreeNode(8);root->left->left->right = new TreeNode(9);std::vector<int> vec;preorderTraversal(root,vec);printf("****************\n");for(int i =  0; i < vec.size();i++){printf("%d\t",vec.at(i));}printf("\n");std::vector<int>().swap(vec);inorderTraversal(root,vec);printf("****************\n");for(int i =  0; i < vec.size();i++){printf("%d\t",vec.at(i));}printf("\n");std::vector<int>().swap(vec);postOrderTraversal(root,vec);printf("****************\n");for(int i =  0; i < vec.size();i++){printf("%d\t",vec.at(i));}printf("\n");//    delete root->left->left->left;
//    delete root->left->left->right;deleteTree(root);std::vector<int>().swap(vec);return 0;
}

程序运行结果如下：

 

附加知识：

二叉树遍历的递归实现详解（先序、中序、后序和层次遍历） - violet-evergarden - 博客园 (cnblogs.com)

C++实现二叉树 前、中、后序遍历（递归与非递归）非递归实现过程最简洁版本_后序遍历的非递归算法-CSDN博客

 深度优先搜索（DFS）和广度优先搜索（BFS）-CSDN博客