C++语言树算法详解（从零开始掌握二叉树与常见操作）

C++中如何定义一棵二叉树？

在C++中，我们通常使用结构体（struct）或类（class）来定义树的节点。以下是一个简单的二叉树节点定义：

struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;        // 构造函数    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};  

二叉树的三种基本遍历方式

二叉树遍历是树算法中最基础的操作，主要有三种方式：

• 前序遍历（Pre-order）：根 → 左 → 右
• 中序遍历（In-order）：左 → 根 → 右
• 后序遍历（Post-order）：左 → 右 → 根

下面分别用递归方式实现这三种遍历：

// 前序遍历void preorder(TreeNode* root) {    if (root == nullptr) return;    cout << root->val << " ";    preorder(root->left);    preorder(root->right);}// 中序遍历void inorder(TreeNode* root) {    if (root == nullptr) return;    inorder(root->left);    cout << root->val << " ";    inorder(root->right);}// 后序遍历void postorder(TreeNode* root) {    if (root == nullptr) return;    postorder(root->left);    postorder(root->right);    cout << root->val << " ";}  

完整示例：构建并遍历一棵二叉树

下面我们构建如下二叉树，并输出三种遍历结果：

      1     / \    2   3   / \  4   5  

#include <iostream>using namespace std;struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};void preorder(TreeNode* root) {    if (!root) return;    cout << root->val << " ";    preorder(root->left);    preorder(root->right);}void inorder(TreeNode* root) {    if (!root) return;    inorder(root->left);    cout << root->val << " ";    inorder(root->right);}void postorder(TreeNode* root) {    if (!root) return;    postorder(root->left);    postorder(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 << "前序遍历: ";    preorder(root);    cout << endl;    cout << "中序遍历: ";    inorder(root);    cout << endl;    cout << "后序遍历: ";    postorder(root);    cout << endl;    return 0;}  

运行结果：

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

总结

通过本教程，你已经掌握了C++树算法的基础知识，包括二叉树的定义、节点结构、以及三种基本的二叉树遍历方法。这些是后续学习更复杂树结构（如二叉搜索树、AVL树、红黑树等）的基石。

记住，实践是最好的老师。建议你动手编写代码，尝试修改树的结构，观察遍历结果的变化。随着练习的深入，你会对C++数据结构有更深刻的理解。

如果你是编程小白，不要担心——只要循序渐进，每一个程序员都是从“Hello World”和简单的树的实现教程开始的！