树-前中后序遍历的非递归实现

前、中、后序遍历是对树进行的基础操作，当使用递归来实现时代码非常简单。但是由于递归时会不断将当前状态保存下来，因此空间复杂度较高。下面就介绍一下用非递归的方式如何来实现这些操作。

二叉树的数据结构定义如下：

• 前序遍历：非递归遍历通过栈来实现，并且有两种不同的实现方式。思路一是先将根节点压入栈，然后当栈不为空的时候，先将栈顶元素出栈并访问这个节点，然后依次将该节点的右孩子和左孩子入栈。代码如下：
  
  void preOrder(TreeNode *root) { if(root == NULL) { return; } stack<struct TreeNode *> s; s.push(root); while(! s.empty()) { TreeNode *node = s.top(); s.pop(); cout << node->val << endl; if (node->right) { s.push(node->right); } if (node->left) { s.push(node->left); } } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  void preOrder(TreeNode *root) {     if(root == NULL) {         return;     }     stack<struct TreeNode *> s;     s.push(root);     while(! s.empty()) {         TreeNode *node = s.top();         s.pop();         cout << node->val << endl;         if (node->right) {             s.push(node->right);         }         if (node->left) {             s.push(node->left);         }     } }

思路二则是使用回溯，先遍历完左子树，然后回溯遍历右子树。

• 中序遍历：和前序遍历的实现非常类似，只不过访问节点的时机不同。
  
  void inOrder(TreeNode *root) { if (root == NULL) { return; } stack<TreeNode *> s; TreeNode *ptr = root; while(ptr != NULL || ! s.empty()) { if (ptr != NULL) { s.push(ptr); ptr = ptr->left; } else { ptr = s.top(); s.pop(); cout << ptr->val << endl; ptr = ptr->right; } } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  void inOrder(TreeNode *root) {     if (root == NULL) {         return;     }     stack<TreeNode *> s;     TreeNode *ptr = root;     while(ptr != NULL || ! s.empty()) {         if (ptr != NULL) {             s.push(ptr);             ptr = ptr->left;         } else {             ptr = s.top();             s.pop();             cout << ptr->val << endl;             ptr = ptr->right;         }     } }

• 后序遍历：后序遍历是这几种遍历方式中比较麻烦的一种。前面的算法的规律是，当一个节点的左子树已经访问完了后，会将当前节点从栈中直接弹出并访问这个节点，然后再遍历它的右子树。但是后序遍历时，当访问完一个节点的左子树后，先得从栈顶获得这个节点，得到它的右子树并访问右子树，当右子树访问之后，再从栈顶获得这个节点，然后去访问这个节点自身，然后将该节点出栈。可以看出，访问该节点的过程发生了两次，但是只有访问了它的右子树后才可以将这个节点从栈中弹出。因此我们需要标记该节点是否被访问过。代码如下：
  
  void postOrder(TreeNode *root) { if (root == NULL) { return; } stack<TreeNode *> s; TreeNode *p,*q; p = root; do { while (p) { s.push(p); p = p->left; } q = NULL; while (! s.empty()) { p = s.top(); s.pop(); if (p->right == q) { cout << p->val << endl; q = p; } else { s.push(p); p = p->right; break; } } } while (! s.empty()); }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

  void postOrder(TreeNode *root) {     if (root == NULL) {         return;     }     stack<TreeNode *> s;     TreeNode *p,*q;     p = root;     do {         while (p) {             s.push(p);             p = p->left;         }         q = NULL;         while (! s.empty()) {             p = s.top();             s.pop();             if (p->right == q) {                 cout << p->val << endl;                 q = p;             } else {                 s.push(p);                 p = p->right;                 break;             }         }     } while (! s.empty()); }

• 层序遍历：作为树的遍历方式的一种，虽然不如前面三种方式常见，但是也是非常有必要了解的。与前面三种方式不同的是，层序遍历使用了队列而不是栈这种结构。思路是：先将根节点入队，当队列不为空的时候，从队列头出队一个元素并访问它，然后将它的左右孩子依次入队。
  
  void levelOrder(TreeNode *root) { if (root == NULL) { return NULL; } queue<TreeNode *> que; que.push(root); while (! que.empty()) { TreeNode *node = que.front(); que.pop(); cout << node->val << endl; if (node->left) { que.push(node->left); } if (node->right) { que.push(node->right); } } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  void levelOrder(TreeNode *root) {     if (root == NULL) {         return NULL;     }     queue<TreeNode *> que;     que.push(root);     while (! que.empty()) {         TreeNode *node = que.front();         que.pop();         cout << node->val << endl;         if (node->left) {             que.push(node->left);         }         if (node->right) {             que.push(node->right);         }     } }