给定一棵二叉树，不使用递归，迭代地后序遍历并输出树中的元素

 二叉树的后序遍历很容易采用递归方式实现：

void postOrderTraversal(BinaryTree *p) {
  if (!p) return;
  postOrderTraversal(p->left);
  postOrderTraversal(p->right);
  cout << p->data;
}

后序遍历是二叉树三种遍历的非递归算法中最难实现的一种，在做这道题目之前可以首先尝试一下这一题，因为它相对简单一些：Binary Search Tree In-Order Traversal Iterative Solution。

三种遍历的非递归实现中最容易的是先序遍历。

后序遍历是一种非常有用的树操作，例如它可以被用于下面的场景：

树的删除。为了释放树结构的内存，某节点在被释放以前，其左右子树的节点首先应当被释放掉。
后缀表示法（逆波兰表示法）

如果在遍历树时维护一个visited标记，问题可以比较直观地解决。在此不详细讨论该方法，可以参阅Wikipedia的描述：Tree Traversal。

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        /* if right child exists AND traversing node from left child, move right */
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop() 

在此我们讨论一种不使用visited标记的算法，看起来比较有挑战性。

提示：

通常情况下，如果树节点中没有指向父节点的指针，就必须借助于栈（Stack）实现遍历。试着想象一下二叉树的遍历过程。什么时候应该输出节点的值？留意在什么条件下会向上/向下遍历树。使用一个变量记录上一次访问的节点，这个辅助节点有什么用处？

解决方案：

我们使用prev变量跟踪上一次访问的节点。假设栈顶元素是curr。当prev是curr的父节点时，我们正在向下遍历树。此时，优先遍历curr的左孩子（将左孩子压入栈）。如果没有左孩子，再看右孩子。如果左右孩子都不存在（curr是叶节点），就输出curr的值并弹出栈顶元素。

如果prev是curr的左孩子，我们正在从左子树向上遍历。我们看一下curr的右孩子。如果可以，就从右孩子向下遍历（将右孩子压入栈），否则打印curr的值并弹出栈顶元素。

如果prev是curr的右孩子，我们正在从右子树向上遍历。打印curr的值并弹出栈顶元素。

void postOrderTraversalIterative(BinaryTree *root) {
  if (!root) return;
  stack<BinaryTree*> s;
  s.push(root);
  BinaryTree *prev = NULL;
  while (!s.empty()) {
    BinaryTree *curr= s.top();
    // we are traversing down the tree
    if (!prev || prev->left == curr|| prev->right == curr) {
      if (curr->left) {
        s.push(curr->left);
      } else if (curr->right) {
        s.push(curr->right);
      } else {
        cout << curr->data << " ";
        s.pop();
      }
    } 
    // we are traversing up the tree from the left
    else if (curr->left == prev) {
      if (curr->right) {
        s.push(curr->right);
      } else {
        cout << curr->data << " ";
        s.pop();
      }
    }
    // we are traversing up the tree from the right
    else if (curr->right == prev) {
      cout << curr->data << " ";
      s.pop();
    }
    prev = curr;  // record previously traversed node
  }
}

上面的代码比较容易理解，但是包含冗余代码。我们可以对代码进行重构，使之更加简洁。观察一下curr值的打印代码是怎样重构成单个else块的。不用担心迭代时会漏掉curr的打印过程，因为它可以确保在下一次迭代时一定会进入else分支。

void postOrderTraversalIterative(BinaryTree *root) {
  if (!root) return;
  stack<BinaryTree*> s;
  s.push(root);
  BinaryTree *prev = NULL;
  while (!s.empty()) {
    BinaryTree *curr= s.top();
    if (!prev || prev->left == curr|| prev->right == curr) {
      if (curr->left)
        s.push(curr->left);
      else if (curr->right)
        s.push(curr->right);
    } else if (curr->left == prev) {
      if (curr->right)
        s.push(curr->right);
    } else {
      cout << curr->data << " ";
      s.pop();
    }
    prev = curr;
  }
}

另一种解法：

另一种解法是使用两个栈。试着在纸上写一下代码。我认为这种解法非常的神奇而优美。你可能觉得这很不可思议，但实际上它做的是反向的先序遍历。亦即遍历的顺序是：节点 -> 右子树 -> 左子树。这生成的是后根遍历的逆序输出。使用第二个栈，再执行一次反向输出即可得到所要的结果。

下面是它的实现步骤：

将根节点压入第一个栈
从第一个栈中弹出一个元素，压入第二个栈
然后分别将该节点的左右孩子压入第一个栈
重复步骤2和步骤3直到第一个栈为空
执行结束，第二个栈中就保存了所有节点的后序遍历输出结果。依次将元素从第二个栈中弹出即可。

void postOrderTraversalIterativeTwoStacks(BinaryTree *root) {
  if (!root) return;
  stack<BinaryTree*> s;
  stack<BinaryTree*> output;
  s.push(root);
  while (!s.empty()) {
    BinaryTree *curr= s.top();
    output.push(curr);
    s.pop();
    if (curr->left)
      s.push(curr->left);
    if (curr->right)
      s.push(curr->right);
  }
  while (!output.empty()) {
    cout << output.top()->data << " ";
    output.pop();
  }
}

复杂度分析：

双栈法的空间复杂度高于第一个解法。实际上，第一个解法的空间复杂度是O(h)，其中h是树的最大高度。而双栈法的空间复杂度是O(n)，其中n是节点的总个数。

原文链接：Binary Tree Post-Order Traversal Iterative Solution

本文链接：http://bookshadow.com/weblog/2015/01/19/binary-tree-post-order-traversal/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码