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

以下是用 C++ 实现树的中序遍历算法的代码：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
};

// 中序遍历
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr != NULL || !st.empty()) {
        while (curr != NULL) {
            st.push(curr);
            curr = curr->left;
        }

        curr = st.top();
        st.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }

    return 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]);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << ' ';
        }
    }
    cout << endl;

    return 0;
}

希望对你有所帮助！