Recorrido y busqueda en arboles

Recorrido y búsqueda en arboles

Según el libro de T. Parajan nos dice que:
El recorrido de un árbol es el proceso para recorrer (desplazarse a lo largo) un árbol de manera sistemática a fin de que cada vértice se visite y procese exactamente una vez .Hay tres métodos para recorrer un árbol binario a saber recorridos de preorden , de inorden y de posorden.
Según el libro de JOHNSONBAUGH Richard pag. 415 nos dice que :
La búsqueda a lo ancho y la búsqueda a profundidad proporcionan formas de recorrer un arbol , es decir de recorrerlo de manera sistemática de modo que cada vértice sea visitado exactamente una vez.
Recorrido preorden :
Para recorrer un árbol binario no vació en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raiz:
1.Visite la raíz
2.Atraviese el sub-arbol izquierdo
3.Atraviese el sub-arbol derecho

Preorden: ABDGEHICFJK

Recorrido inorden :
Para recorrer un arbol binario no vació en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.Atraviese el sub-arbol izquierdo
2.Visite la raíz
3.Atraviese el sub-arbol derecho

Inorden: GDBHEIACJKF

Recorrido posorden :
Para recorrer un árbol binario no vació en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.Atraviese el sub-arbol izquierdo
2.Atraviese el sub-arbol derecho
3.Visite la raíz

Postorden: GDHIEBKJFCA

Búsqueda en Arboles

Esto implica examinar cada parte del árbol hasta que el vértice o la arista deseada sea encontrada. Podríamos profundizar moviéndonos a un vértice siempre que sea posible o podríamos des plegarnos comprobando todos los vertices en un nivel antes de pasar al siguiente.
Búsqueda en profundidad:
La idea básica de la búsqueda en profundidad es penetrar tan profundamente como sea posible antes de desplegarse a otros vértices .Esto se consigue al tomar el nuevo vértice adyacente al ultimo de los posibles vértices anteriores.

Búsqueda en anchura:
La idea básica de la búsqueda en anchura es desplegarse a tantos vértices como sea posible antes de penetrar en profundidad dentro de un árbol. Esto significa que visitaremos todos los vértices adyacentes a uno dado antes de cambiar de nivel.

Comentarios

Publicar un comentario

Entradas populares de este blog

2.2.3 Triplos.

2.2.3 Triplos.  En la historia de los compiladores han sido utilizadas una amplia variedad de representaciones intermedias como lo es la siguiente clase de representación de código intermedio de un árbol de 3 direcciones,2 para los operandos y una para la ubicación del resultado. esta clase incluye un amplio número de representaciones diferentes entre las cuales encontramos cuadruplos y triples. la principal diferencia entre estas notaciones y la notación postfija es que ellos incluyen referencias explicitas para los resultados de los cálculos intermedios, mientras que la notación posfija los resultados son implícitos al representarlos en una pila. §      La diferencia entre triples y cuadruplos es que con los triples es referenciado el valor intermedio hacia el número del triple que lo creo, pero en los cuádruplos requiere que ellos tengan nombres implícitos. §      Los triples tienen una ventaja obvia de ser más consistente, pero...
Leer más

¿Por qué los registros de 32 bits se llaman EAX, EBX, ECX, EDX, etc.

¿Por qué los registros de 32 bits se llaman EAX, EBX, ECX, EDX, etc. Esta es realmente una historia interesante, En los días en que teníamos procesadores de 8 bits (los procesadores de 8 bits significan que los registros en los procesadores podrán contener datos de 8 bits), los registros se llamaban como, AL, BL Entonces, cuando nos mudamos a procesadores de 16 bits, los nombramos como, AX, BX .. (AX puede dividirse en AH y AL Del mismo modo, cuando pasamos a procesadores de 32 bits, nombramos registros como, EAX, EBX, ECX, EDX. ¿Crees que en los procesadores de 64 bits tendremos otro nombre para los registros? Sí, tiene toda la razón, tenemos diferentes nombres para los registros. Se les llama, RAX, RBX, RCX, RDX, etc. (PD: Tenemos 8 registros más en procesadores x64 llamados R8, R9, R10 ... hasta R15) No todos los procesadores de 8 bits usaban AL, BL, etc. Por ejemplo, el Motorola 6800 usaba A, B, X, SP, PC y CCR para las ba...
Leer más

Unidad II. Notaciones Prefija,Infija y Posfija

 Notaciones Prefija,Infija y Posfija. Forma especial en la que se pueden expresar una expresión matemática en tres formas: Infija, Prefija y Posfija. Prefija: Nos indica que el operador va antes de los operandos sus características principales son: Los operandos conservan el mismo orden que la notación infija equivalente. -No requiere de paréntesis para indicar el orden de precedencia de operadores ya que el es una operación. -Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos. -Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando. Se repite este hasta que nos quede un solo resultado. Notación prefija:  El orden es operador, primer operando, segundo. Infija : Es la forma más común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operandos. La notación infija puede estar completamente par...
Leer más