recursiva - programar un arbol binario de busqueda en java

Escriba un recorrido no recursivo de un árbol de búsqueda binaria usando espacio constante y tiempo de ejecución O(n)

Question

Esto no es tarea, esta es una pregunta de entrevista.

La trampa aquí es que el algoritmo debe ser un espacio constante. No tengo ni idea de cómo hacer esto sin una pila, publicaría lo que he escrito usando una pila, pero de todos modos no es relevante.

Esto es lo que he intentado: intenté hacer un recorrido de prepedido y llegué al nodo más a la izquierda, pero estoy atrapado allí. No sé cómo "recurse" una copia de seguridad sin un puntero de pila / padre.

Cualquier ayuda sería apreciada.

(Lo estoy etiquetando como Java, ya que es lo que me gusta usar, pero es bastante independiente del lenguaje, como es evidente).

Answer 1

¿Qué hay de Morris Inorder Tree Traversal? Se basa en la noción de árboles roscados y modifica el árbol, pero lo revierte cuando está hecho.

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

No usa ningún espacio extra.

Answer 2

Aquí hay una versión más corta de la respuesta original de iluxa. Ejecuta exactamente los mismos pasos de manipulación e impresión de nodos, exactamente en el mismo orden, pero de forma simplificada [1]:

void traverse (Node n) {
  while (n) {
    Node next = n.left;
    if (next) {
      n.left = next.right;
      next.right = n;
      n = next;
    } else {
      print(n);
      n = n.right;
    }
  }
}

[1] Además, incluso funciona cuando el nodo raíz del árbol no tiene ningún elemento secundario izquierdo.

Answer 3

El título de la pregunta no menciona la falta de un puntero "padre" en el nodo. Aunque no se requiere necesariamente para BST, muchas implementaciones de árbol binario tienen un puntero principal. Nodo de clase {Nodo * izquierda; Nodo * a la derecha; Nodo * padre; Datos de datos; };

Este es el caso, imaginando un diagrama del árbol sobre papel, y dibujando con un lápiz alrededor del árbol, subiendo y bajando, desde ambos lados de los bordes (cuando baja, se quedará del borde, y cuando suba, estará en el lado derecho). Básicamente, hay 4 estados:

1. Sudoeste: estás en el lado izquierdo del borde, yendo del padre al izquierdo
2. Nordeste: pasar de un niño de la izquierda a su padre
3. Sudeste: pasar de ser un padre a ser un niño adecuado
4. North West: pasar de ser un niño adecuado a su padre

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

Answer 4

Es un árbol de búsqueda binaria , por lo que se puede llegar a cada nodo mediante una serie de decisiones de derecha / izquierda. Describa esa serie como 0/1, bit menos significativo a más significativo. Entonces la función f (0) significa "el nodo encontrado tomando la rama derecha hasta que encuentre una hoja; f (1) significa tomar uno a la izquierda y el resto a la derecha; f (2) - es decir, binario 010 - - significa tomar a la derecha, luego a la izquierda, luego derechos hasta que encuentre una hoja. Iterar f (n) empezando en n = 0 hasta que haya tocado cada hoja. No eficiente (ya que debe comenzar en la parte superior del árbol cada tiempo) pero memoria constante y tiempo lineal.

Answer 5

Es un árbol de búsqueda, por lo que siempre puede obtener la siguiente clave / entrada

Necesitas algo así como (no probé el código, pero es tan simple como se pone)

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

para mayor claridad, esta es una entrada más higherEntry , por lo que no es recursiva. Ahí tienes :)

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 6

La respuesta aceptada necesita el siguiente cambio, de lo contrario no se imprimirá el árbol donde el BST solo tiene un nodo

if (current == NULL && root != NULL)
   print(root);

Answer 7

No lo pensé del todo, pero creo que es posible siempre y cuando estés dispuesto a arruinar tu árbol en el proceso.

Cada Nodo tiene 2 punteros, por lo que podría usarse para representar una lista doblemente vinculada. Supongamos que avanza de Root a Root.Left = Current. Ahora Root.Left pointer es inútil, así que asígnelo a Current.Right y proceda a Current.Left. Para cuando llegue al niño más a la izquierda, tendrá una lista vinculada con árboles que cuelgan de algunos nodos. Ahora itere sobre eso, repitiendo el proceso para cada árbol que encuentre a medida que avanza

EDITAR: lo pensé bien. Aquí está el algoritmo que imprime en orden:

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 8

Podemos atravesar el árbol binario sin modificar el árbol en sí (los nodos provistos tienen un puntero principal). Y se puede hacer en un espacio constante. Encontré este útil enlace para el mismo http://tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/

Answer 9

Si está utilizando un árbol basado en un puntero hacia abajo y no tiene un puntero principal o alguna otra memoria, es imposible recorrerlo en un espacio constante.

Es posible si su árbol binario está en una matriz en lugar de una estructura de objeto basada en puntero. Pero luego puedes acceder a cualquier nodo directamente. Que es un tipo de trampa ;-)

Answer 10

caso especial menor para la respuesta de iluxa arriba

if(current== null)
        {
            current = root;
            parent = current.Right;
            if(parent != null)
            {
                current.Right = parent.Left;
                parent.Left = current;
            }
        }