非递归前中后序遍历二叉树

在二叉树的遍历中，有三种主要的方法：前序遍历、中序遍历和后序遍历，它们都是非递归实现的。以下是每种遍历方式的描述：

1. **前序遍历（Preorder Traversal）**：
- 先访问根节点（根-左-右）
- 非递归实现通常使用栈，将当前节点压入栈，然后访问当前节点，再将左子树（如果存在）和右子树（如果存在）依次压入栈。

2. **中序遍历（Inorder Traversal）**：
- 先访问左子树（左-根-右）
- 非递归实现同样用栈，但顺序不同：先遍历左子树，然后访问当前节点，最后访问右子树。

3. **后序遍历（Postorder Traversal）**：
- 先访问左子树和右子树（左-右-根）
- 这是相对复杂的一种，因为最后才访问根节点，所以需要两个栈。首先遍历左右子树，将节点压入栈，最后弹出栈元素并访问它们，直到栈为空。

对于非递归实现，核心思想是利用栈的数据结构来模拟递归过程中的调用栈。每一步都对应着递归调用中的压栈、访问和出栈操作。下面是基本步骤：
- 前序：`push(root); while (stack) { node = stack.pop(); visit(node); if (node->right) push(node->right); if (node->left) push(node->left); }`
- 中序：`if (root) { inorder_traversal(root->left); visit(root); inorder_traversal(root->right); }`
- 后序：`if (root) { stack.push(root); while (stack) { node = stack.top(); if (node->left == NULL && node->right == NULL) { visit(node); stack.pop(); } else if (node->right == NULL) { visit(node->left); stack.pop(); } else { visit(node->right); stack.pop(); } } }`