二叉树的遍历

二叉树的遍历是指按照某种顺序访问树中的每个节点，使得每个节点都被访问一次。二叉树的遍历主要有三种方式：前序遍历（Pre-order）、中序遍历（In-order）、后序遍历（Post-order）。此外，还有层序遍历（Breadth-first search, BFS）。

1. 前序遍历（Pre-order）：

   • 访问顺序：根节点 -> 左子树 -> 右子树
   • 首先访问根节点，然后递归地进行前序遍历左子树，最后递归地进行前序遍历右子树。

2. 中序遍历（In-order）：

   • 访问顺序：左子树 -> 根节点 -> 右子树
   • 首先递归地进行中序遍历左子树，然后访问根节点，最后递归地进行中序遍历右子树。
   • 对于二叉搜索树，中序遍历可以得到一个有序的节点序列。

3. 后序遍历（Post-order）：

   • 访问顺序：左子树 -> 右子树 -> 根节点
   • 首先递归地进行后序遍历左子树，然后递归地进行后序遍历右子树，最后访问根节点。

4. 层序遍历（Breadth-first search, BFS）：

   • 从根节点开始，逐层遍历树的节点。
   • 使用队列来实现，每次从队列中取出一个节点，访问它，然后将它的非空子节点加入队列。

下面是这四种遍历方式的简单实现（以C++为例）：

cpp

#include <iostream>
#include <queue>
#include <vector>using namespace std;// 定义二叉树的节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 前序遍历
void preOrder(TreeNode* root) {if (root == NULL) return;cout << root->val << " ";preOrder(root->left);preOrder(root->right);
}// 中序遍历
void inOrder(TreeNode* root) {if (root == NULL) return;inOrder(root->left);cout << root->val << " ";inOrder(root->right);
}// 后序遍历
void postOrder(TreeNode* root) {if (root == NULL) return;postOrder(root->left);postOrder(root->right);cout << root->val << " ";
}// 层序遍历
void levelOrder(TreeNode* root) {if (root == NULL) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();cout << node->val << " ";if (node->left != NULL) q.push(node->left);if (node->right != NULL) q.push(node->right);}
}int main() {// 构建一个简单的二叉树//       1//      / \//     2   3//    / \//   4   5TreeNode* 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 << "Pre-order: ";preOrder(root);cout << endl;cout << "In-order: ";inOrder(root);cout << endl;cout << "Post-order: ";postOrder(root);cout << endl;cout << "Level-order: ";levelOrder(root);cout << endl;return 0;
}

这段代码定义了一个简单的二叉树，并实现了前序、中序、后序和层序遍历。每种遍历方式都会按照特定的顺序输出节点的值。

复制再试一次分享