Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Algoritmia » PREorden Interativo

Algoritmia - PREorden Interativo

Volver
Nuevo Tema
<<>>
 
Vista:

PREorden Interativo

Publicado por Marco Antonio (1 intervención) el 23/07/2001 22:09:11
Hola amigos estoy estudiando arboles binarios y me preguntaba si se puede hacer un preorden iterativo,es decir, recorrer un arbol sin utilizar llamadas recursivas a otro arbol, es decir, sin poder llamar a hijo izquierdo ni a hijo derecho
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:PREorden Interativo

Publicado por hectorito (2 intervenciones) el 27/07/2001 12:51:18
Si se puede. Simplemente necesitas una pila donde se almacecen los nodos que vas recorriendo. Para entender el pseudocodigo que t pongo necesitaras saber como funciona una pila y los punteros.

La idea es mas o menos.

nodo=raiz
hacer
---Si nodo != NULL //esto avanza por los hijos derechos
------mostrar(nodo)
------apilar(nodo)
------nodo = nodo->HijoIzq
---Sino si PilaNoVacia() //esto retrocede y avanza por el hijo derecho
------Desapilar() //desapilamos el ultimo q no sirve para nada
------nodo = Desapilar() //De este ya cogemos el hijo derecho
------nodo = nodo->HijoDer
mientras PilaNoVacia

Espero que el pseudocodigo sea lo suficientemente expresivo
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:PREorden Interativo

Publicado por Andres (1 intervención) el 06/10/2015 04:28:49
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void BST::preordenIterativo(nodet *r){
 
    stack<nodet *> pila;
    nodet *aux = r;
 
    do{
        if(aux != NULL){
            cout<<aux->getData()<<" ";
            pila.push(aux);
            aux = aux->getLeft();
        }else if(!pila.empty()){
            aux = pila.top();
            pila.pop();
            aux = aux->getRight();
        }
    }while(!pila.empty() || aux != NULL);
 
}
 
void BST::inordenIterativo(nodet *r){
 
    stack<nodet *> pila;
    nodet *aux = r;
 
    do{
        if(!pila.empty() && aux == NULL){
            cout<<pila.top()->getData()<<" ";
        }
 
        if(aux != NULL){
            pila.push(aux);
            aux = aux->getLeft();
        }else if(!pila.empty()){
            aux = pila.top();
            pila.pop();
            aux = aux->getRight();
        }
    }while(!pila.empty() || aux != NULL);
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:PREorden Interativo

Publicado por Emilio (5 intervenciones) el 29/07/2001 10:20:57
Si, hay varios algoritmos. Pero el que mas se usa es el que todos los hijos dejechos que son NULL en vez de ser NULL apuntan a su padre derecho y asi podemos programar todo lo que queremos sin usar recursion.
Ejemplo:

.....................1
................/............\
............./..................\
.........2.......................3
...../.......\.............../..........\
4.............5..........6............7

el hijo derecho del 4 apunta al 2, el hijo derecho del 5 apunta al 1 el hijo derecho del 6 apunta al 3 y el hijo derecho del 7 apunta a un nodo que es de ayuda donde sabemos que terminamos de pasar a todo el arbol, de la misma forma para un arbol mas grande. Si quieres algunas funciones de este tipo de arbol escribeme un e-mail.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:PREorden Interativo

Publicado por newbie (1 intervención) el 19/07/2007 00:46:12
no seas nulo!!! si no usas izquierdo o derecho por lo mismo tendras que usar un nodo->izquierdo o un nodo->derecho xD! acaso quieres destruir el orden de las cosas?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar