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

Ответ 1

Вы можете это сделать, вам просто нужно запомнить последний посещенный node вместе с текущим node. Выполнение этого не запрещено выражением проблемы: оба флага visited для каждого node и a stack являются (наихудший случай) O (n), помня последний node является просто O (1).

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

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;
        }
    }
}

Ответ 2

Вот еще один способ сделать это. Я думаю, что это по сути эквивалентно ответу svick, но избегает дополнительной переменной. Эта версия реализована в 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

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

Ответ 3

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

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;
}

Ответ 4

public void inorderNoStack() {
    if (root == null) {
        return;
    }

    // use the previous to always track the last visited node
    // helps in deciding if we are going down/up
    Node prev = null;

    Node curr = root;

    while (curr != null) {
        // going down
        if (prev == null || prev.left == curr || prev.right == curr) {
            if (curr.left != null) {
                prev = curr;
                curr = curr.left;
                continue;
            } else {

                visitn(curr);

                if (curr.right != null) {
                    prev = curr;
                    curr = curr.right;
                    continue;
                } else {
                    // swap states
                    prev = curr;
                    curr = prev.parent;
                }
            }
        }

        // going up after left traversal
        if (curr != null && prev == curr.left) {

            visitn(curr);

            if (curr.right != null) {
                prev = curr;
                curr = curr.right;
                continue;
            } else {
                // swap states
                prev = curr;
                curr = prev.parent;
            }
        }

        // going up after right traversal
        if (curr != null && prev == curr.right) {
            // swap states
            prev = curr;
            curr = prev.parent;
        }
    }
}

Ответ 5

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

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

Ответ 6

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

Шаг 2: начиная с самого левого node, найдите преемника в порядке до тех пор, пока не будет

    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;
      }
    }

Ответ 7

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

• Установите v в корневой каталог.
• Пока v имеет левый дочерний элемент, установите v в его левый дочерний элемент.
• Выход v.
• Если v является корнем, верните.
• Установите p для родителя v.
• Если p right child равно v, установите v в p и перейдите к шагу 4.
• Доходность
• Если p имеет правильный дочерний элемент, установите v в p справа и перейдите к шагу 2.
• Установите v в p и перейдите к шагу 4.

Ответ 8

Это в С++:

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;
     }
  }
}