Итеративный обход после отправления без сохранения зарегистрированного флага

Question

Зачем нужен флаг посещения для итеративного обхода после ордера, а не для итеративного обхода порядка или предварительного заказа.

Возможно ли отслеживание по почте без посещения погодного флага?

Answer 1

Вот после заказа на сайте:

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

Он не использует никаких флагов. Почему, по-вашему, нужен флаг?

Возможно, я не понимаю фразу «итеративный обход после ордера». По симметрии, если вы считаете, что для «итеративного обхода предлога» не нужен флаг, Я утверждаю, что вам придется поверить, что «итеративный обход после похода» также является флагом бесплатно и наоборот.

EDIT: Плохо, должно быть, поздно ночью. «Итеративный» означает «реализовать без рекурсии». ОК, поэтому вы реализуете свой собственный набор узлов, и, вам нужно реализовать то, что составляет стек обратных адресов. Я думаю, что флаг имитирует эффект возврата адрес, зная, следует ли идти дальше к L1 или L2. И так как вам это нужно для почтового заказа, по симметрии вам это нужно для предварительного заказа.

EDIT Октябрь 2010: Мой плохой снова, предоставленный алгоритм не был пост-орденом. Перераб.

Answer 2

Я считаю, что алгоритм, показанный в предыдущей публикации для обхода порта, находится в том, что он «обрабатывает» узел перед посещением левого поддерева. Поперечное перемещение по порядку - это то же самое, что и обратная польская нотация, в которой операнды (листовые узлы или поддеревья) предшествуют оператору (следующий более высокий узел поддерева).

Исправленный postorder обход Алгоритм Построения будет:

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

Если мы начнем с простого рекурсивного алгоритма postorder,

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

можно измельчить функцию на три части «а», «б» и «с», а затем наивно переводить это в итеративный алгоритм с помощью эмуляции виртуального стека вызовов:

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] → […] 

Это означает, что:

• «а» может появиться только максимум один раз в верхней части стека, в то время как
• «б» и «в» и появляются любое количество раз в середине стека, возможно, чередуется.

Поэтому нам не нужно хранить «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 

Логический флаг на стопке «посетил флаг». В этом примере мы не храним флаг непосредственно на узлах, а внутри нашего стека, но сетевой эффект тот же. В некоторых вариантах алгоритма вместо этого используется переменная «последний посещенный узел», но для этого требуется способ сравнения узлов для «identity» (указатель/ссылочное равенство), которые мы здесь не предполагаем.

Этот флаг является частью алгоритма, поскольку, как отмечалось в нашем анализе ранее, записи «b» и «c» в стеке могут отображаться совершенно произвольно. Нам нужно вид информации, чтобы рассказать нам, следует ли нам перемещаться вправо или звонить по телефону f.