Как выполнить обход BST по порядку без рекурсии или стека, но с использованием родительских указателей?

Вы можете сделать это, вам просто нужно помнить последний посещенный узел вместе с текущим узлом. Это не запрещено условием задачи: и флаг visited на каждом узле, и флаг stack равны (в худшем случае) O(n), если вспомнить, что последний узел просто < em>О(1).

В C# алгоритм может выглядеть так:

static void Walk(Node node)
{
    Node lastNode = null;
    while (node != null)
    {
        if (lastNode == node.Parent)
        {
            if (node.Left != null)
            {
                lastNode = node;
                node = node.Left;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Left)
        {
            Output(node);

            if (node.Right != null)
            {
                lastNode = node;
                node = node.Right;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Right)
        {
            lastNode = node;
            node = node.Parent;
        }
    }
}

Вот еще один способ сделать это. Я думаю, что это по сути эквивалентно ответу Свика, но избегает дополнительной переменной. Эта версия реализована на Python:

node=root
if node is not None:
  while node.left is not None:
    node=node.left
  while node is not None:
    output(node)
    if node.right is not None:
      node=node.right
      while node.left is not None:
        node=node.left
    else:
      while node.parent is not None and node.parent.right is node:
        node=node.parent
      node=node.parent

Какой бы узел вы ни посещали последним, определяет следующий узел, который вам нужно посетить. Если вы только что посетили узел X, вам нужно посетить самый левый узел справа от X. Если у X нет правого потомка, то следующий узел является первым предком, где узел X не появился справа сторона.

Используя правильную идею svick (см. его ответ), это протестированный код на C++ . Обратите внимание, что я не тестировал его код и даже не смотрел на него, я просто взял его идею и реализовал свою собственную функцию.

void in_order_traversal_iterative_with_parent(node* root) {
node* current = root;
node* previous = NULL;

while (current) {
    if (previous == current->parent) { // Traversing down the tree.
        previous = current;
        if (current->left) {
            current = current->left;
        } else {
            cout << ' ' << current->data;
            if (current->right)
                current = current->right;
            else
                current = current->parent;
        }
    } else if (previous == current->left) { // Traversing up the tree from the left.
        previous = current;
        cout << ' ' << current->data;
        if (current->right)
            current = current->right;
        else
            current = current->parent;
    } else if (previous == current->right) { // Traversing up the tree from the right.
        previous = current;
        current = current->parent;
    }
}

cout << endl;
}

Мое решение Java без добавления какого-либо флага в существующее ДЕРЕВО. И нет родительского указателя. Этот подход будет удерживать узлы до высоты дерева. Пожалуйста, посмотрите.

https://github.com/skanagavelu/Algorithams/blob/master/src/tree/InOrderTraversalIterative.java

Шаг 1: напишите функцию, которая возвращает преемника по порядку

Шаг 2. Начиная с крайнего левого узла, найдите преемника по порядку, пока не останется ни одного.

    public class TreeNode {
      int data;
      TreeNode left;
      TreeNode right;
      TreeNode parent;
    }

    public class TreeUtility {
      public void inorderNoRecursion(TreeNode root) {
        TreeNode current = leftmostNode(root);
        while(current != null) {
          System.out.println(current.data);
          current = inorderSuccessor(current);
        }
      }

      public TreeNode inorderSuccessor(TreeNode node) {
        if (node.right!=null) {
          return leftmostNode(node.right);
        }

        TreeNode p = node.parent;
        TreeNode c = node;
        while(p!=null && c != p.left) {
          c = p;
          p = p.parent;
        }
        return p;
      }

      private TreeNode leftmostNode(TreeNode node) {
        while (node.left != null) {
          node = node.left;
        }
        return node;
      }
    }

Ключом являются родительские указатели (или возможность видоизменять дерево), но вам нужно постоянное количество дополнительных состояний (например, программный счетчик следующей сопрограммы).

1. Установите v в корень.
2. Пока у v есть левый дочерний элемент, установите v в его левый дочерний элемент.
3. Урожайность v.
4. Если v является корнем, то возврат.
5. Установите p в родительский элемент v.
6. Если правым дочерним элементом p является v, установите v в p и перейдите к шагу 4.
7. Урожайность с.
8. Если у p есть правый дочерний элемент, установите v в правый дочерний элемент p и перейдите к шагу 2.
9. Установите v на p и перейдите к шагу 4.

Это на С++:

void InOrder(Node *r)
{
   if(r==NULL)
         return;

   Node *t=r;

   while(t!=NULL)
       t=t->left;

  while(t!=r)
  {
     if(t==(t->parent->left))
     {
        cout<<t->parent->data;
        t=t->parent->right;
       if(t!=NULL)
      {
       while(t!=NULL)
          t=t->left;
      } 
      if(t==NULL)
          t=t->parent;
     }
     if(t==t->parent->right)
     {
        t=t->parent;
     }
  }
}