#include <stack>
#include "iostream"
using namespace std;

// 假设二叉树节点定义如下
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

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

typedef TreeNode* BinTree;

void InOrder(BinTree T) {
    stack<BinTree> stack;
    BinTree current = T;

    while (current != nullptr || !stack.empty()) {
        // 不断访问左子节点，直到没有左子节点为止，沿途将节点压入栈中
        while (current != nullptr) {
            stack.push(current);
            current = current->left;
        }

        // 弹出栈顶元素并访问它
        current = stack.top();
        stack.pop();
        cout << current->value << " "; // 访问当前节点

        // 转向访问右子树
        current = current->right;
    }
}

// 示例：如何使用 InOrder 函数
int main() {
    // 构建一个简单的二叉树
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    BinTree 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);

    InOrder(root); // 输出: 4 2 5 1 3

    return 0;
}