二叉树后序遍历的非递归实现

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

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

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)实现遍历。试着想象一下二叉树的遍历过程。什么时候应该输出节点的值?留意在什么条件下会向上/向下遍历树。使用一个变量记录上一次访问的节点,这个辅助节点有什么用处?

Post-order traversal sequence

Post-order traversal sequence: A, C, E, D, B, H, I, G, F

解决方案:

我们使用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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. 豆花鱼 豆花鱼 发布于 2016年1月8日 03:49 #

    只有当cur是叶子节点或者当previous node是其子结点的时候才处理当前结点,其他情况直接先将cur->right push进来然后再push cur->left就可以了。代码比较简单一些,http://www.hihuyue.com/hihuyue/codepractise/leetcode/leetcode119-binary-tree-postorder-traversal

  2. 赤小侸 赤小侸 发布于 2016年2月19日 05:02 #

    最后一种方法应先把右子树push到s里?

  3. 在线疯狂 在线疯狂 发布于 2016年2月19日 18:11 #

    用一棵最简单的二叉树AB##C##测试下:
    A
    / \
    B C

  4. tst tst 发布于 2020年6月5日 10:54 #

    双栈没有什么神奇之处,就是 把 根,右,左 的前序变种进行输出,然后逆序

张贴您的评论