一、概要
二叉树的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历，具体定义如下：
前序遍历：先访问根节点，然后按照前序遍历的方式递归访问左子树和右子树。
中序遍历：先按照中序遍历的方式递归访问左子树，然后访问根节点，最后再按照中序遍历的方式递归访问右子树。
后序遍历：先按照后序遍历的方式递归访问左子树和右子树，最后访问根节点。
层序遍历：从上到下，从左到右依次访问每个节点。
其实我们应该看成这个样子：
然后让我们把它按照定义画出来：
左右子树和根通常指的是二叉树中的节点。在二叉树中，每个节点可以看作是一棵子树的根节点，其左子树和右子树分别为该节点的左子节点和右子节点所代表的子树。
举个例子，对于下面这棵二叉树：
1
/ \
2 3
/ \
4 5
1是根节点，它的左子树为2，右子树为3。3的左子树为4，右子树为5。节点2、4、5没有子节点，它们的左子树和右子树都为空。
二.代码实现
// 二叉树结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (!root) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (!root) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
// 层序遍历
void levelorderTraversal(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
auto node = q.front();
q.pop();
if (!node) continue;
cout << node->val << " ";
q.push(node->left);
q.push(node->right);
}
}
三、总结
二叉树的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历，这四种遍历方式分别从不同角度对二叉树进行遍历，可以用于寻找特定节点、比较树的结构等。
- 前序遍历
前序遍历按照根节点-左子树-右子树的顺序遍历二叉树。具体实现时，先输出当前节点的值，然后递归遍历左子树，最后递归遍历右子树。
2.中序遍历
中序遍历按照左子树-根节点-右子树的顺序遍历二叉树。具体实现时，先递归遍历左子树，然后输出当前节点的值，最后递归遍历右子树。
3.后序遍历
后序遍历按照左子树-右子树-根节点的顺序遍历二叉树。具体实现时，先递归遍历左子树，然后递归遍历右子树，最后输出当前节点的值。
4.层序遍历
层序遍历按照从上到下、从左到右的顺序遍历二叉树。具体实现时，使用一个队列来存储待遍历的节点，首先将根节点入队，然后依次从队列中取出节点，输出它的值，并将它的左右子节点依次入队。
在实际编程中，可以使用递归或迭代两种方式来实现二叉树的遍历。递归实现通常比较简单，但可能会导致栈溢出或效率较低；迭代实现需要借助辅助数据结构，如栈或队列，但效率较高且不易出错。
