Écrire une traversée non récursive d'un arbre de recherche binaire en utilisant un espace constant et un temps d'exécution O (n)

Question

Ce n'est pas de devoirs, c'est une question d'entrevue.

Le hic ici est que l'algorithme doit être constante de l'espace. Je suis assez désemparés sur la façon de le faire sans une pile, j'ai poster ce que j'ai écrit à l'aide d'une pile, mais il n'est pas pertinent de toute façon.

Voici ce que j'ai essayé: j'ai essayé de faire une pré-commande de la traversée et je suis arrivé à la partie gauche du nœud, mais je suis coincé là-bas. Je ne sais pas comment "récursif" sauvegarder sans pile/parent pointeur.

Toute aide serait appréciée.

(Je suis d'étiquetage comme Java puisque c'est ce que je suis à l'aise à l'aide, mais c'est plutôt la langue agnostique comme c'est évident.)

Answer 1

Je ne pense pas qu'il par entièrement, mais je pense que c'est possible aussi longtemps que vous êtes prêt à gâcher votre arbre dans le processus.

Chaque Nœud dispose de 2 pointeurs, de sorte qu'il pourrait être utilisé pour représenter une liste à double liaison. Supposons que vous l'avance de la Racine à la Racine.Gauche=Courant. Maintenant La Racine.À gauche du pointeur est inutile, donc assigner en Courant.À droite et passez à l'Actuel.De gauche. Au moment où vous atteignez la plus à gauche de l'enfant, vous aurez une liste liée avec des arbres pendaient de certains nœuds. Maintenant parcourir que, en répétant le processus pour chaque arbre vous rencontrez que vous allez

EDIT: réfléchi. Voici l'algorithme qui s'imprime dans l'ordre:

void traverse (Node root) {
  traverse (root.left, root);
}

void traverse (Node current, Node parent) {
  while (current != null) {
    if (parent != null) {
      parent.left = current.right;
      current.right = parent;
    }

    if (current.left != null) {
      parent = current;
      current = current.left;
    } else {
      print(current);
      current = current.right;
      parent = null;
    }
  }
}

Answer 2

Que diriez-vous de traversée d'arbres Morris Inorder? Il est basé sur la notion d'arborescence threadée et modifie l'arborescence, mais la rétablit lorsque l'opération est terminée.

Linkie: http://geeksforgeeks.org/?p=6358

N'utilise pas d'espace supplémentaire.

Answer 3

Si vous utilisez une arborescence basée sur un pointeur descendant et que vous n'avez pas de pointeur parent ou une autre mémoire, il est impossible de le parcourir dans un espace constant.

Cela est possible si votre arbre binaire est dans un tableau au lieu d'une structure d'objet basée sur un pointeur. Mais alors vous pouvez accéder directement à n’importe quel nœud. Ce qui est une sorte de triche ;-)

Answer 4

C'est un arbre de recherche, vous pouvez donc toujours obtenir la prochaine clé / entrée

Vous avez besoin de quelque chose comme (je n'ai pas testé le code, mais c'est aussi simple que cela devient)

 java.util.NavigableMap<K, V> map=...
for (Entry<K, V> e = map.firstEntry(); e!=null; e = map.higherEntry(e.getKey())) {
  process(e)
}
 

pour plus de clarté, il s'agit de higherEntry , de sorte que ce n'est pas récursif. Voilà :)

 final Entry<K,V> getHigherEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}
 

Answer 5

Le titre de la question ne parle pas de l'absence d'un "parent" pointeur sur le nœud. Bien qu'il n'est pas nécessairement requis pour la STB, de nombreux arbres binaires mises en œuvre n'ont un parent, un pointeur. la classe Node { Noeud* gauche; Noeud* droit; Noeud* parent; De DONNÉES; };

C'est le cas, l'imagerie d'un diagramme de l'arbre sur le papier, et dessiner avec un crayon autour de l'arbre, va en haut et en bas, des deux côtés de la bords (lors de la descente, vous serez à gauche de l'arête, et quand vous serez sur le côté droit). Fondamentalement, il y a 4 états:

1. Sud-ouest: Vous êtes sur le côté gauche de l'arête, en allant du parent gauche de son enfant
2. Nord-est: passer de l'une à gauche de l'enfant, de retour à son parent
3. Sud-est: à partir d'un parent à un enfant
4. Nord-ouest: à partir d'un droit de l'enfant, de retour à son parent

Traverse( Node* node )
{
    enum DIRECTION {SW, NE, SE, NW};
    DIRECTION direction=SW;

    while( node )
    {
        // first, output the node data, if I'm on my way down:
        if( direction==SE or direction==SW ) {
            out_stream << node->data;
        }

        switch( direction ) {
        case SW:                
            if( node->left ) {
                // if we have a left child, keep going down left
                node = node->left;
            }
            else if( node->right ) {
                // we don't have a left child, go right
                node = node->right;
                DIRECTION = SE;
            }
            else {
                // no children, go up.
                DIRECTION = NE;
            }
            break;
        case SE:
            if( node->left ) {
                DIRECTION = SW;
                node = node->left;
            }
            else if( node->right ) {
                node = node->right;
            }
            else {
                DIRECTION = NW;
            }
            break;
        case NE:
            if( node->right ) {
                // take a u-turn back to the right node
                node = node->right;
                DIRECTION = SE;
            }
            else {
                node = node->parent;
            }
            break;
        case NW:
            node = node->parent;
            break;
        }
    }
}