C++实现二叉树的中序遍历算法

1. 算法介绍

中序遍历是一种常用的二叉树遍历算法，其访问顺序为：左子树 -> 根节点 -> 右子树。

2. 代码实现

以下是使用 C++ 实现二叉树中序遍历的代码示例：

#include <iostream>
#include <vector>

using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 中序遍历函数
void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left, result);
    result.push_back(root->val);
    inorderTraversal(root->right, result);
}

int main() {
    int n;
    cin >> n;
    vector<TreeNode*> nodes(n + 1, NULL);

    // 构建二叉树
    for (int i = 1; i <= n; i++) {
        int num, ls, rs;
        cin >> num >> ls >> rs;
        TreeNode* node = new TreeNode(num);
        nodes[num] = node;

        if (ls != -1) {
            node->left = nodes[ls];
        }
        if (rs != -1) {
            node->right = nodes[rs];
        }
    }

    // 中序遍历并输出结果
    vector<int> result;
    inorderTraversal(nodes[1], result);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << ' ';
        }
    }
    cout << endl;

    return 0;
}

3. 代码解释

• 代码首先定义了二叉树节点 TreeNode，包含节点值 val 以及指向左右子节点的指针 left 和 right。
• inorderTraversal 函数实现了中序遍历算法，它递归地访问左子树、根节点和右子树，并将节点值存储在 result 向量中。
• main 函数首先读取二叉树的节点信息，并构建二叉树。
• 然后，调用 inorderTraversal 函数进行中序遍历，并将结果存储在 result 向量中。
• 最后，遍历 result 向量并输出中序遍历的结果。

4. 总结

本代码示例演示了如何使用 C++ 实现二叉树的中序遍历算法。理解和掌握二叉树的遍历算法对于解决很多算法问题都非常有帮助。