二叉树及其应用：从基础到实践（C++ 版本）-EW帮帮网

二叉树是一种常见且重要的数据结构，在计算机科学中具有广泛的应用。本文将以简单易懂的方式，通过 C++ 实现二叉树的基础操作及其实际应用，帮助初学者理解和掌握二叉树。

一、二叉树的基本概念

1. 什么是二叉树？

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为 左子节点 和 右子节点。二叉树的特性如下：

根节点 是树的起点；
叶子节点 没有子节点；
高度是树中从根节点到叶子节点最长路径的边数。

2. 二叉树的常见类型

完全二叉树：除了最后一层，其他层都被完全填满，最后一层的节点从左到右依次排列。
满二叉树：每个节点要么没有子节点，要么有两个子节点，且所有叶子节点在同一层。
二叉搜索树（BST）：满足左子树的所有节点小于根节点，右子树的所有节点大于根节点。

二、二叉树的表示

1. 二叉树的链式存储

在 C++ 中，二叉树通常通过链式存储实现，每个节点包含一个值和指向其左、右子节点的指针。

struct TreeNode {
    int val;           // 节点值
    TreeNode* left;    // 左子节点
    TreeNode* right;   // 右子节点

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. 示例二叉树结构

我们创建以下二叉树：

实现代码如下：

TreeNode* createTree() {
    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);
    return root;
}

三、二叉树的基本操作

1. 遍历二叉树

深度优先遍历

深度优先遍历包括 前序遍历、中序遍历 和 后序遍历。

前序遍历（根 → 左 → 右）：

void preorderTraversal(TreeNode* root) {
    if (root) {
        cout << root->val << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

中序遍历（左 → 根 → 右）：

void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }
}

后序遍历（左 → 右 → 根）：

void postorderTraversal(TreeNode* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        cout << root->val << " ";
    }
}

广度优先遍历（层次遍历）

使用队列实现层次遍历：

#include <queue>

void levelOrderTraversal(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

2. 示例输出

完整代码如下：

int main() {
    TreeNode* root = createTree();

    cout << "前序遍历：";
    preorderTraversal(root); // 输出: 1 2 4 5 3
    cout << endl;

    cout << "中序遍历：";
    inorderTraversal(root); // 输出: 4 2 5 1 3
    cout << endl;

    cout << "后序遍历：";
    postorderTraversal(root); // 输出: 4 5 2 3 1
    cout << endl;

    cout << "层次遍历：";
    levelOrderTraversal(root); // 输出: 1 2 3 4 5
    cout << endl;

    return 0;
}

四、二叉树的应用

应用场景 1：表达式树

表达式树是一种特殊的二叉树，用于表示数学表达式：

叶子节点表示操作数；
内部节点表示操作符。

例如，表达式 (3 + 5) * 2 可表示为：

通过后序遍历，可以轻松计算表达式的值。

应用场景 2：二叉搜索树（BST）

二叉搜索树（BST）支持高效的查找、插入和删除操作。

插入节点

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) {
        root->left = insertIntoBST(root->left, val);
    } else {
        root->right = insertIntoBST(root->right, val);
    }
    return root;
}

查找节点

TreeNode* searchBST(TreeNode* root, int val) {
    if (!root || root->val == val) return root;
    if (val < root->val) return searchBST(root->left, val);
    return searchBST(root->right);
}

示例

int main() {
    TreeNode* bst = nullptr;
    bst = insertIntoBST(bst, 5);
    bst = insertIntoBST(bst, 3);
    bst = insertIntoBST(bst, 7);
    bst = insertIntoBST(bst, 2);
    bst = insertIntoBST(bst, 4);

    cout << "中序遍历BST：";
    inorderTraversal(bst); // 输出: 2 3 4 5 7
    cout << endl;

    int searchVal = 4;
    TreeNode* found = searchBST(bst, searchVal);
    if (found) {
        cout << "找到节点：" << found->val << endl;
    } else {
        cout << "未找到节点：" << searchVal << endl;
    }

    return 0;
}

五、总结

本文介绍了二叉树的基本概念、常见操作及其应用场景，通过 C++ 代码详细实现了二叉树的创建、遍历、二叉搜索树的插入与查找操作。二叉树是一种高效且灵活的数据结构，其应用广泛，学习和掌握它是编程进阶的重要一步。如果有疑问，欢迎留言讨论！

二叉树及其应用：从基础到实践（C++ 版本）