二叉树非递归遍历C++实现：前序、中序

二叉树遍历是计算机科学中处理树形结构数据时常用的一种操作，主要分为递归和非递归两种实现方式。在本问题中，我们关注的是非递归的C++实现，具体涉及到前序遍历和中序遍历。 1. 前序遍历 前序遍历的顺序是“根-左-右”。递归实现非常直观，从根节点开始，然后递归地访问左子树和右子树。非递归实现则利用栈来模拟递归过程。首先访问根节点，然后将其压入栈中。接着检查当前节点的左孩子，如果非空，则将左孩子作为新的当前节点继续处理，直到左子树为空。此时，栈顶的元素（即当前节点的父节点）完成了左子树的遍历，可以访问其右子树，或者如果栈顶元素的右子树为空，就弹出栈顶元素，继续处理栈中的下一个节点。这一过程持续到所有节点都被访问过且栈为空。 以下是非递归前序遍历的C++代码实现： ```cpp void preOrder2(BinTree* root) { stack<BinTree*> s; BinTree* p = root; while (p != NULL || !s.empty()) { while (p != NULL) { cout << p->data << ""; s.push(p); p = p->lchild; } if (!s.empty()) { p = s.top(); s.pop(); p = p->rchild; } } } ``` 2. 中序遍历 中序遍历的顺序是“左-根-右”。在非递归实现中，也需要用到栈来辅助。不同于前序遍历，中序遍历需要先遍历左子树，然后访问根节点，最后处理右子树。在遍历过程中，当遇到一个节点的左子树为空时，说明该节点的左子树已经被完全遍历，可以访问这个节点并将其右子树作为新的当前节点。如果右子树也为空，那么这个节点的父节点就可以从栈中弹出，继续处理父节点的右子树或栈中的下一个节点。 以下是非递归中序遍历的C++代码实现： ```cpp void inOrder2(BinTree* root) { stack<BinTree*> s; BinTree* p = root; while (p != NULL || !s.empty()) { while (p != NULL) { s.push(p); p = p->lchild; } if (!s.empty()) { p = s.top(); s.pop(); cout << p->data << ""; p = p->rchild; } } } ``` 3. 后序遍历 后序遍历的顺序是“左-右-根”，是最复杂的一种遍历方式，因为需要确保左右子树都访问完后才访问根节点。非递归实现通常需要用到两个栈，一个用于存储待访问的节点，另一个用于记录已访问过的节点。由于涉及到对访问顺序的控制，实现相对复杂，这里不再详述，但原理与前序和中序遍历类似，通过栈来模拟递归的过程。 总结来说，非递归遍历二叉树的关键在于使用栈来模拟递归调用的堆栈，通过适当的操作顺序（如前序中的“根-左-右”或中序中的“左-根-右”）来控制节点的访问。这种方法虽然比递归实现复杂，但可以避免深度递归可能导致的栈溢出问题，尤其在处理大型树结构时更具有优势。