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

"二叉树遍历的非递归C++实现代码，包括前序遍历和中序遍历的方法。" 二叉树遍历是数据结构中的基础操作，主要包含三种方式：前序遍历、中序遍历和后序遍历。这三种遍历方法在理解和实现上各有特点，递归方式简洁易懂，而非递归方式则需要借助额外的数据结构，如栈，来模拟递归的过程。 ### 前序遍历 前序遍历的顺序是“根-左-右”。递归实现时，我们首先访问根节点，然后递归地遍历左子树和右子树。非递归实现则需要使用栈来跟踪节点，具体步骤如下： 1. 访问根节点并将其压入栈中。 2. 如果当前节点不为空，就将其左子节点设为当前节点，并重复此步骤。如果当前节点为空但栈不空，说明已经处理完当前节点的左子树，此时弹出栈顶元素，将其右子节点设为当前节点。 ```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; } } } ``` ### 中序遍历 中序遍历的顺序是“左-根-右”。在递归实现中，我们首先遍历左子树，然后访问根节点，最后遍历右子树。非递归实现同样使用栈，但处理方式略有不同： 1. 当前节点不为空时，一直向下遍历左子树，同时将每个节点压入栈中。 2. 当遇到空节点且栈不空时，弹出栈顶元素（即当前节点的父节点），访问该节点，然后将父节点的右子节点设为当前节点。 ```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; } } } ``` 虽然前序和中序遍历的非递归实现相对简单，但后序遍历的非递归实现较为复杂，因为它要求“左-右-根”的顺序，需要在遍历过程中维护一个临时结果集来确保正确顺序。通常会使用两个栈或一个栈配合辅助变量来实现，这里没有给出具体的代码，但理解前序和中序的非递归实现对于理解后序遍历的非递归实现至关重要。 非递归遍历提供了另一种思考问题的角度，它要求对数据结构的特性有深入的理解，并能够利用额外的数据结构来模拟递归过程。这种能力对于解决更复杂的问题，如深度优先搜索（DFS）和其他树的遍历问题，都是非常有用的。