Comment le faire dans l'ordre de la traversée d'un BST sans récursivité et pile mais à l'aide de parent pointeurs?

Est-il possible de faire un processus itératif dans l'ordre-de la traversée sur un BST dont le nœud a un parent pointeur (le parent de la racine est null) sans l'aide d'un visited drapeau ou un stack?

J'ai googlé et n'ai pas trouvé une réponse. Le point est, comment puis-je savoir à un certain nœud - que je viens de vs, j'ai tout fini en dessous?

La récursivité? Si c'est une indirectes de l'utilisation de piles.
Cela ressemble à un de ces stupides questions de l'entrevue. La récursivité est le plus probable de la réponse attendue.
[@Shubham, @pablochan] Si vous lisez de nouveau la question, vous trouverez le mot itératif écrit explicitement.
Eh bien la réponse est non (sauf si vous pouvez enregistrer les nœuds visités quelque part)
êtes-vous sûr? Je pense que vous pouvez faire, voir ma réponse.

OriginalL'auteur OmarOthman | 2012-04-29

Vous pouvez le faire, vous avez juste besoin de se rappeler la dernière visite du nœud avec le nœud courant. Ce n'est pas rejetée par l'énoncé du problème: les deux visited drapeau sur chaque nœud et un stack sont (pire des cas) S(n), se souvenant de la dernière nœud est juste O(1).

En C#, l'algorithme pourrait ressembler à ceci:

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

Ce code est dans une boucle infinie. Lorsqu'il tente d'accéder à une feuille, après son entrée sur le côté gauche, le dernier nœud sera nulle, et lorsqu'il a l'intention de traverser vers le bas du côté droit, il va aller dans le (dernier == node.gauche) de la branche, et faire la même chose une fois de plus.
Non, il ne sera pas. Notez que la branche de droite est dans un if, pas else if. Si, Après son entrée sur le côté gauche (dans la lastNode == node.Left branche), il cherche immédiatement à droite (lastNode == node.Right) et seulement après qu'il passe en boucle sur.
Si vous avez besoin d'un parent pointeur, il est impossible de faire autrement?
vous pouvez également utiliser une tige filetée de l'arbre. Si vous voulez éviter la pile et de la mère de pointeurs.

OriginalL'auteur

10

Ici est une autre façon de faire. Je pense que c'est essentiellement équivalent à svick réponse, mais évite la variable supplémentaire. Cette version est implémenté en 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
```
Quel que soit le nœud que vous avez visité dernier détermine le nœud suivant que vous devez visiter. Si vous venez de visiter nœud X, alors vous avez besoin pour visiter les plus à gauche du nœud à droite de X. Si X n'a pas le droit de l'enfant, puis le nœud suivant est le premier ancêtre, où nœud X n'est pas venu de la droite.

Le code que Vaughn Cato n'est en effet traversée de l'arbre dans l'ordre, mais pour autant que je peux dire, il s'exécute dans une boucle infinie une fois qu'il atteint l'extrémité de l'arbre. Personne ne sait d'une façon de résoudre ce problème?
Je ne vois pas de boucle infinie dont vous parlez. Quand il traverse la plus à droite du nœud, puis la dernière boucle de le renvoyer à la racine, et enfin définir le nœud pour le parent de la racine, ce qui devrait être nul. L'extérieur tandis que la boucle serait alors à l'arrêt.
Agréable et propre de mise en œuvre +1
Testé un arbre binaire en tant que root = 2, left = 1 et la droite = 3. Il ne fonctionne pas et ne produisent que le nœud de gauche.
Je n'arrivais pas à reproduire le problème. Il semble fonctionner ok: codepad.org/njxp5tba

OriginalL'auteur

À l'aide de svick'idée correcte (voir son réponse), c'est le testé code en C++. Notez que je n'ai pas tester son code ou même de prendre un coup d'oeil, j'ai juste pris son idée et mis en place ma propre fonction.

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

OriginalL'auteur

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

Les réponses contenant du code, sans explication, ne sont pas très utiles.

OriginalL'auteur

0

Ma solution Java sans introduire aucun indicateur sur l'ARBRE existant. Et aucun parent ne pointeur. Cette approche permettra de tenir les nœuds jusqu'à la hauteur de l'arbre. Jetez un coup d'oeil.

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

OriginalL'auteur

Étape 1 : écrire une fonction qui retourne dans l'ordre successeur

Étape 2 : à Partir du nœud le plus à gauche, trouver le dans l'ordre successeur jusqu'à ce qu'il n'y a aucun

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

OriginalL'auteur

-1

La clé est la mère des pointeurs (ou la capacité de muter de l'arbre), mais vous avez besoin d'une quantité constante de supplémentaires de l'état (par exemple, le compteur de programme de la suite de coroutine).
1. Ensemble v de la racine.
2. Tandis que v a gauche de l'enfant, set v à gauche de son enfant.
3. Rendement v.
4. Si v est la racine, puis revenir.
5. Ensemble p de v parent.
6. Si p est un droit de l'enfant est v, puis définissez v à p et passez à l'étape 4.
7. Rendement p.
8. Si p est un droit de l'enfant, puis définissez v p droit de l'enfant et passez à l'étape 2.
9. Set v à p et passez à l'étape 4.
Votre code ne fonctionne pas trop de cas de test. J'ai traduit pour l'exacte spaghetti code en C++ et il a couru contre mon test de suite.

OriginalL'auteur

-2

C'est en C++:

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

OriginalL'auteur

Vous devez vous connecter pour publier un commentaire.