1. 简述
前序，根->左子树->右子树，中序，左子树->根->右子树，后序，左子树->右子树->根。
本文主要关注三种遍历方式的非递归实现。其中，中序和后序的实现来自参考中的“二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现”一文及其评论，前序比较简单，单独写了个实现与参考的文中实现不同。另外，对于中序和后序，实现是一样的，也没什么意思，加了几行注释，就这样了，实现主要是核心代码，完整代码在参考的文章中很详细。2. 前序非递归 首先，栈顶元素入栈，然后进入循环，每次把栈顶元素输出，元素出栈，将该元素的右孩子（如果存在）和左孩子（如果存在）依次入栈。 void PreOrder(Node * root) {
assert(NULL != root) stack < Node *> store; store.push(root); // 根结点入栈 while ( ! store.empty()) { root = store.top(); // 在循环中，root记录的是当前准备输出的结点 store.pop(); cout << root -> value << " " ; // 输出当前结点 if (root -> right_child) // 右孩子入栈 store.push(root -> right_child); if (root -> left_child) // 左孩子入栈 store.push(root -> left_child); }}
3. 中序非递归
前序中的Root主要作为中间变量使用。这里的Root的意义是下一个要进栈的结点，初始值为根结点。
while (Root不为空 || 栈不为空) { if(Root不为空) // 一路向左入栈 Root入栈 Root=Root->left_child。 else // 栈顶元素的左子树都输出过了 输出栈顶元素 Root=栈顶元素->right_child 栈顶元素出栈。}
void InOrder(Node * root) { assert(NULL != root); stack < Node *> store; while (root && ! store.empty()) { if (root != NULL) { // 只要不为空，就一路向左结点方向走去 store.push(root); root = root -> left_child; } else { // store.top()的左边都走过了 cout << store.top() -> value << " " ; // 输出当前结点 root = store.top() -> right_child; store.pop(); } }}
4. 后序非递归
Root表示下一个要处理的结点，初始化为根结点，Per表示上一次刚刚输出过的结点。
，Per的作用是对有孩子的结点进行判断，由于算法特性，每次到某个结点时，其左子树都输出过了，此时只要判断Pre是否是当前结点的右孩子，如果不是，那么说明其右子树没走过，那么Root=当前结点的右子树，否则就是刚刚输出了当前结点的右孩子，由于是后序，其右子树也必定都输出过了，此时只要输出当前结点，更新Pre就好了。 while(Root不为空 || 栈不为空) { if(Root不为空) // 一路向左 Root入栈 Root=Root->left_child else { // 此时栈顶元素的左子树都输出过了 Root = 栈顶元素 if(Root有右孩子 && Pre不等于Root的右孩子) // 此时栈顶元素的右子树还没输出 Root=Root->right else // 此时栈顶元素的左右子树都输出过了 输出栈顶元素 Pre = 栈顶元素 栈顶元素出栈 }}
void PostOrder(Node * root) { assert(NULL != root); Node * Pre = NULL; stack < Node *> store; while (root && ! store.empty()) { if (root != NULL) { // 一路向左 store.push(root); root = root -> left_child; } else { // stack.top()的左子树都输出完了 if (store.top() -> right_child != NULL && store.top() -> right_child != Pre) { // 右子树存在且没有输出过 root = root -> right_child; } else { // 左右子树都输出过了 cout << store.top() -> value << " " ; Pre = store.top(); store.pop(); } } }}
5. 参考
二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现