C二叉树的前序中序后序非递归怎么实现

前序遍历非递归实现

前序遍历非递归实现需要用到栈，首先将根节点压入栈中，然后进行如下操作：

• 从栈中弹出一个节点，并输出其值
• 将该节点的右子节点（如果有）压入栈中
• 将该节点的左子节点（如果有）压入栈中

重复以上步骤直到栈为空。

void preOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();
        cout<< node->val <<" ";
        if (node->right != nullptr) {
            nodeStack.push(node->right);
        }
        if (node->left != nullptr) {
            nodeStack.push(node->left);
        }
    }
}

中序遍历非递归实现

中序遍历非递归实现需要用到栈，首先将根节点压入栈中，然后进行如下操作：

• 从栈中弹出一个节点，并检查其左子节点是否为空
• 如果该节点的左子节点为空，则输出该节点的值，将从栈中弹出的节点设置为其右子节点，并继续遍历
• 如果该节点的左子节点不为空，则将该节点压入栈中，然后继续遍历该节点的左子节点

重复以上步骤直到栈为空。

void inOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack nodeStack;
    TreeNode* node = root;
    while (node != nullptr || !nodeStack.empty()) {
        while (node != nullptr) {
            nodeStack.push(node);
            node = node->left;
        }
        node = nodeStack.top();
        nodeStack.pop();
        cout<< node->val <<" ";
        node = node->right;
    }
}

后序遍历非递归实现

后序遍历非递归实现需要用到栈，首先将根节点压入栈中，然后进行如下操作：

• 从栈中弹出一个节点，并检查是否可以输出该节点
• 如果该节点的左右子节点均已输出，则可以输出该节点（将值存入vector等待遍历结束后输出）
• 否则将该节点的右、左子节点分别压入栈中（注意先压右子节点，再压左子节点）

重复以上步骤直到栈为空。

vector postOrderTraversal(TreeNode* root) {
    vector result;
    if (root == nullptr) {
        return result;
    }
    stack nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();
        result.insert(result.begin(), node->val);
        if (node->left != nullptr) {
            nodeStack.push(node->left);
        }
        if (node->right != nullptr) {
            nodeStack.push(node->right);
        }
    }
    return result;
}

总结

通过使用栈来模拟递归过程的调用堆栈，可以实现二叉树的三种遍历方式的非递归实现。其中，前序遍历和中序遍历的实现比较直接，而后序遍历的实现则需要根据输出顺序的不同而进行区分，需要将节点的值存入一个vector中，最终输出vector的值。