迭代後的順序遍歷沒有保持訪問標誌

Question

爲什麼有必要保持訪問標誌的迭代後序遍歷，而不是中序或預順序迭代遍歷。

是否可以在不保留訪問標誌的情況下進行後續遍歷？

Answer 1

這裏有一個訂單後，請訪問：

postordervisit(t) 
{ if not(leaf(t)) 
    { postordervisit(left(t); 
     postordervisit(right(t)); 
    } 
L1: process(t); 
     L2: 
} 

它不使用任何標誌。你爲什麼認爲一面旗子是必要的？

也許我不明白這句話，「迭代後序遍歷」。 通過對稱性，如果你認爲「迭代預遍歷」不需要一個標誌，我認爲你不得不相信「迭代後序遍歷」也是 標誌免費，反之亦然。

編輯：我的壞，一定是在深夜。 「迭代」意思是「沒有遞歸實現」。 好吧，所以你實現自己的堆棧節點，和你必須實現什麼總數堆棧的返回地址。我認爲國旗正在模擬返回 地址的效果，知道是否接下來要去L1或L2。而且由於您需要這個後期訂單，通過對稱，您需要預訂。

編輯2010年10月：我又壞了，提供的算法不是後序。修訂。

Answer 2

我相信在前一篇文章中顯示的端口順序遍歷算法是在它訪問左子樹之前「處理」節點。 Postorder Traversal與Reverse Polish Notation基本相同，其中操作數（葉節點或子樹）位於運算符（下一個更高的子樹節點）之前。

一個修正後序遍歷algorith是：

postordervisit(t) 
{ if null(t) return;  
    postordervisit(right(t)); 
    postordervisit(left(t); 
    process(t); 
} 

這將參觀子樹的根之前訪問葉子或子樹節點。

Answer 3

後序遍歷迭代版本可以在不使用訪問標誌的情況下實現，但實現起來更加困難。

請參閱此處，瞭解不使用任何訪問標誌的迭代後序遍歷的兩種解決方案。

http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html

Answer 4

在我的用戶1337c0d3r的溶液中發現的一個問題：它是一個簡單的前序相反的順序。我的解決方案使用「活動列表」來標記堆棧中的節點。

（您可以將標記標記存儲在堆棧中，將單獨發佈該解決方案。）

void print_postorder(Nodes const& roots) 
{ 
    typedef std::set<Node const*> ActiveList; 
    ActiveList activeNodes; 
    vector<Nodes::const_iterator> stack(1, roots.begin()); 

    while(stack.empty() == false) 
    { 
     Nodes::const_iterator node = stack.back(); 
     ActiveList::iterator activeEntry = activeNodes.find(&*node); 

     if(activeEntry == activeNodes.end()) 
     { 
      // This node is now active. 
      activeNodes.insert(&*node); 
      // Plan to visit each child. 
      for(Nodes::const_reverse_iterator rchild = node->children.rbegin(); 
       rchild != node->children.rend(); ++rchild) 
      { 
       Nodes::const_reverse_iterator rchild2 = rchild; 
       Nodes::const_iterator child = (++rchild2).base(); 
       stack.push_back(child); 
      } 
     } 
     else 
     { 
      // Post-order visit the node. 
      std::size_t depth = activeNodes.size(); 
      for(std::size_t i = 0; i < 4 * depth; ++i) 
       cout << ' '; // Indent 
      cout << node->name << endl; 
      // We're finished with this node. 
      activeNodes.erase(activeEntry); 
      stack.pop_back(); 
     } 
    } 
} 

// Try this for yourself! Tree representation: 

#include <vector> 
#include <set> 

struct Node; 
typedef std::vector<Node> Nodes; 
struct Node 
{ 
    std::string name; 
    Nodes children; 
}; 

Answer 5

如果我們先從簡單的遞歸後序算法，

def postorder1(node, f): 
    # a: 
    if node is None: 
     return None 
    postorder1(node.left, f) 
    # b: 
    postorder1(node.right, f) 
    # c: 
    f(node) 

我們可以砍的功能分爲三個部分「A」，「B」和「C」，然後天真地翻譯它爲通過模擬一個虛擬調用堆棧迭代算法：

def postorder2(node, f): 
    stack = [("a", node)] 
    while stack: 
     go, node = stack.pop() 
     if go == "a": 
      if node is not None: 
       stack.append(("b", node)) 
       stack.append(("a", node.left)) 
     elif go == "b": 
      stack.append(("c", node)) 
      stack.append(("a", node.right)) 
     elif go == "c": 
      f(node) 

由此我們觀察到堆棧只能通過以下三種方式之一修改：

[…, a] → […, b, a] 
[…, b] → […, c, a] 
[…, c] → […] 

這意味着：

• 「一個」只能在堆棧的頂部出現最多一次，而
• 「b」和「c」和出現任意次數在堆棧的中間，可能是交錯的。

因此，我們並不需要在堆棧中存儲「a」 - 存儲「a」的單個變量就足夠了。這讓我們天真的迭代算法簡化爲更傳統的形式：

def postorder3(node, f): 
    stack = [] 
    while True: 
     if node: 
      stack.append((True, node)) 
      node = node.left 
     elif stack: 
      left, top = stack.pop() 
      if left: 
       stack.append((False, top)) 
       node = top.right 
      else: 
       f(top) 
     else: 
      break 

堆棧上的布爾標誌是「已訪問標記」。在這個例子中，我們不直接將標誌存儲在節點上，而是存儲在我們的堆棧中，但是淨效果是相同的。該算法的一些變體使用「最後訪問的節點」變量，但這需要一種方法來比較「身份」（指針/引用相等）的節點，我們在此不假設。

該標誌是必不可少的算法的一部分，因爲正如我們在前面的分析中指出的那樣，堆棧中的「b」和「c」條目可以以完全任意的方式出現。我們需要的一些信息來告訴我們是否應該向右移動或者撥打f。