C++实现二叉树中序遍历算法（附代码示例）

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

本文将介绍如何使用C++实现二叉树的中序遍历算法，并提供完整的代码示例。

1. 问题描述

给定一个以1为根的树，输出树的中序遍历。

2. 输入格式

第一行输入一个整数 n 表示树有 n 个点。 后面 n 行每行输入三个数，num，ls 和 rs，分别表示第 num 个点、它的左儿子和右儿子，-1 表示空节点。

3. 输出格式

输出树的中序遍历。

4. 样例输入

5
1 2 3
2 4 5
3 -1 -1
4 -1 -1
5 -1 -1

5. 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;
}

6. 解题思路

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

• 递归遍历左子树。
• 访问根节点，将节点值加入结果数组。
• 递归遍历右子树。

7. 总结

本文介绍了使用 C++ 实现二叉树中序遍历算法，并提供了详细的代码示例和解题思路，希望对你有所帮助。