二叉树的先序,中序,后序遍历非递归

二叉树的先序，中序和后序遍历是二叉树中最基本的操作之一。在许多算法和数据结构中，这些遍历方法都有着广泛的应用。简单来说，先序遍历是指先访问根节点，再访问左子树，最后访问右子树；中序遍历是指先访问左子树，再访问根节点，最后访问右子树；后序遍历则是先访问左子树，再访问右子树，最后访问根节点。这三种遍历方式都可以使用递归来实现，但是递归实现的空间复杂度较高，因此本文将介绍二叉树的先序，中序，后序遍历的非递归实现方法。

一、先序遍历非递归

先序遍历可以使用“栈”来实现。具体的实现方法是：将根节点入栈，然后循环执行以下操作：

1. 如果栈为空，则结束遍历

2. 取出栈顶元素，并将其打印出来

3. 如果该元素有右子树，则将右子树入栈

4. 如果该元素有左子树，则将左子树入栈

代码实现如下：

```

void PreOrder(TreeNode* root) {

if (root == nullptr) return;

stack s;

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 s;

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, s2;

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);

}

}

```

综上所述，本文介绍了二叉树的先序，中序，后序遍历的非递归实现方法。其中先序遍历可以使用栈来实现，中序遍历需要在访问完左子树后回溯，而后序遍历则需要使用两个栈来实现。这些遍历方法为二叉树的操作提供了基础，它们在算法和数据结构中都有着广泛的应用。