二叉树的先序,中序,后序遍历非递归
二叉树的先序，中序和后序遍历是二叉树中最基本的操作之一。在许多算法和数据结构中，这些遍历方法都有着广泛的应用。简单来说，先序遍历是指先访问根节点，再访问左子树，最后访问右子树；中序遍历是指先访问左子树，再访问根节点，最后访问右子树；后序遍历则是先访问左子树，再访问右子树，最后访问根节点。这三种遍历方式都可以使用递归来实现，但是递归实现的空间复杂度较高，因此本文将介绍二叉树的先序，中序，后序遍历的非递归实现方法。
一、先序遍历非递归
先序遍历可以使用“栈”来实现。具体的实现方法是：将根节点入栈，然后循环执行以下操作：
1. 如果栈为空，则结束遍历
2. 取出栈顶元素，并将其打印出来
3. 如果该元素有右子树，则将右子树入栈
4. 如果该元素有左子树，则将左子树入栈
代码实现如下：
```
void PreOrder(TreeNode* root) {
if (root == nullptr) return;
stack
s.push(root);
while (!s.empty()) {
TreeNode* cur = s.top();
s.pop();
printf("%d ", cur->val);
if (cur->right) s.push(cur->right);
if (cur->left) s.push(cur->left);
}
}
```
二、中序遍历非递归
中序遍历非递归的实现需要模拟递归过程中的“回溯”。具体来说，需要在访问完当前节点的左子树后，将其出栈，并访问其右子树。代码实现如下：
```
void InOrder(TreeNode* root) {
if (root == nullptr) return;
stack
TreeNode* cur = root;
while (!s.empty() || cur != nullptr) {
while (cur != nullptr) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
printf("%d ", cur->val);
cur = cur->right;
}
}
```
三、后序遍历非递归
后序遍历非递归的实现比前面两种稍微复杂一些。可以使用两个栈来实现。具体过程如下：
1. 将根节点入栈s1
2. 循环执行以下操作：
1) 取出栈s1的栈顶元素，并将其压入栈s2
2) 如果该元素有左子树，则将左子树压入栈s1
3) 如果该元素有右子树，则将右子树压入栈s1
3. 当s1为空时，逆序输出栈s2中的元素
代码实现如下：
```
void PostOrder(TreeNode* root) {
if (root == nullptr) return;
stack
s1.push(root);
while (!s1.empty()) {
TreeNode* cur = s1.top();
s1.pop();
s2.push(cur);
if (cur->left) s1.push(cur->left);
if (cur->right) s1.push(cur->right);
}
while (!s2.empty()) {
TreeNode* cur = s2.top();
s2.pop();
printf("%d ", cur->val);
}
}
```
综上所述，本文介绍了二叉树的先序，中序，后序遍历的非递归实现方法。其中先序遍历可以使用栈来实现，中序遍历需要在访问完左子树后回溯，而后序遍历则需要使用两个栈来实现。这些遍历方法为二叉树的操作提供了基础，它们在算法和数据结构中都有着广泛的应用。
