非递归遍历二叉树

中序

void InOrderTraverseWithoutRecursion(BiTree T) {
    stack<BiTree> s;
    BiTree p = T;
    BiTree q = (BiTree) malloc(sizeof(BiNode));
    while (p != nullptr || !s.empty()) {
        if (p != nullptr) {
            s.push(p);
            p = p->left;
        } else {
            q = s.top();
            s.pop();
            cout << q->val << " ";
            p = q->right;
        }
    }
}

前序

void PreOrderTraverseWithoutRecursion(BiTree T) {
    stack<BiTree> s;
    BiTree p = T;
    while (p != nullptr || !s.empty()) {
        if (p != nullptr) {
            s.push(p);
            cout << p->val << " ";
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

后序

void PostOrderTraverseWithoutRecursion(BiTree T) {
    if (T == NULL) return;
    stack<BiTree> s1, s2; // 使用两个栈
    vector<int> result; // 存储遍历结果
    s1.push(T); // 根节点入栈
    while (!s1.empty()) {
        BiTree node = s1.top();
        s1.pop();
        s2.push(node); // 将节点压入第二个栈
        result.insert(result.begin(), node->val); // 记录结果
        // 先右孩子后左孩子入栈
        if (node->left) s1.push(node->left);
        if (node->right) s1.push(node->right);
    }
    // 输出结果
    for (int i: result) {
        cout << i << " ";
    }
}