Перемещение по дереву без рекурсии? [Дубликат]

Вам не хватает того, что после того, как узел выскочил, его правый ребенок все равно должен пройти:

  current = s.top();
  s.pop();
  cout << current->data << " ";
  current = current->right;

Если бы у вас были только данные в стеке, это было бы невозможно. Инвариант цикла состоит в том, что стек содержит те же узлы с непересекающимися правыми дочерними элементами.

Другой способ увидеть, что происходит, - это преобразование рекурсивного обхода в итеративный по алгебре:

traverse(node) {
  if (node) {
    traverse(node->left);
    visit(node);
    traverse(node->right);
  }
}

Сначала преобразуйте хвостовой вызов в итерацию. Мы делаем это, обновляя аргумент и заменяя рекурсивный вызов на goto на начало функции:

traverse(node) {
 start:
  if (node) {
    traverse(node->left);
    visit(node);
    node = node->right;
    goto start;
  }
}

goto и if такие же, как while, поэтому мы до сих пор

traverse(node) {
  while (node) {
    traverse(node->left);
    visit(node);
    node = node->right;
  }
}

Замена другого рекурсивного вызова требует, чтобы мы симулировали стек вызовов среды выполнения компилятора. Мы делаем это с явным стеком.

traverse(node) {
 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
    goto start;         // simulate the recursive call
                        // recursive call was here; it's gone now!
   recursive_return:    // branch here to simulate return from recursive call
    visit(node);
    node = node->right;
  }
  // simulate the recursive return: if stack has args, restore and go to return site
  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    goto recursive_return;
  }
}

Хотя это уродливо, это способ, который всегда работает для реализации итеративных версий рекурсивного кода. (Это сложнее, если есть несколько нерегулярных рекурсивных вызовов, но не много.) И я уверен, что вы можете видеть сходство с вашим кодом.

Мы даже можем избавиться от уродства с помощью более алгебра. Во-первых, нетрудно увидеть этот код:

 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
    goto start;         // simulate the recursive call

, когда исполнение, начинающееся с start, эквивалентно

  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
  }

Мы также можем заменить

  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    goto recursive_return;
  }

со следующим

  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    visit(node);
    node = node->right;
    goto start;
  }

Мы просто скопировали три команды после recursive_return: в тело if.

При этом не осталось никакого пути чтобы получить метку recursive_return, поэтому мы можем удалить ее вместе с двумя следующими утверждениями:

   // Dead code!  Delete me!
   recursive_return:
    visit(node);
    node = node->right;

Теперь мы имеем:

traverse(node) {
 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
  }
  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    visit(node);
    node = node->right;
    goto start;
  }
}

Мы можем избавиться от последний goto start, заменив его бесконечным циклом:

traverse(node) {
  loop {
    while (node) {
      stack.push(node);        // save the value of the argument
      node = node->left;       // redefine it the same way the recursive call would have
    }
    if (stack.empty()) break;  // original code returns, so does this!
    node = stack.pop();        // restore the saved parameter value
    visit(node);
    node = node->right;
  }
}

Обратите внимание, что мы возвращаемся при тех же условиях, что и предыдущий код: стек пуст!

позвольте вам доказать себе, что этот код делает то же, что и вы, но он немного эффективнее, потому что он избегает некоторых сравнений! Нам никогда не приходилось рассуждать о указателях и элементах стека. Это «просто случилось».