Diferencia entre revisiones de «Árbol binario»

Línea 1: Línea 1:
{{ Normalizar }}
 
 
{{Definición
 
{{Definición
 
|nombre= Árbol binario
 
|nombre= Árbol binario
 
|imagen= Árbol_binario1.png
 
|imagen= Árbol_binario1.png
 
|tamaño= 7 KB
 
|tamaño= 7 KB
|concepto= En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").
+
|concepto= En ciencias de la [[computación]], un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").
 
}}
 
}}
==Árbol binario==
+
'''Árbol binario'''. A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
 
  
 
La representación gráfica de un árbol binario es la siguiente:
 
La representación gráfica de un árbol binario es la siguiente:
  
 
[[Archivo:Árbol_binario.jpg]]
 
[[Archivo:Árbol_binario.jpg]]
==Representación en Memoria==
+
==Representación en memoria==
 
Hay dos formas tradicionales de representar un árbol binario en memoria:
 
Hay dos formas tradicionales de representar un árbol binario en memoria:
Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
+
 
Por medio de arreglos.
+
*Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
+
*Por medio de arreglos.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
+
*Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
 +
*Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
 +
 
 
==El algoritmo de creación de un árbol binario ==
 
==El algoritmo de creación de un árbol binario ==
 
Procedimiento crear (q:nodo)
 
Procedimiento crear (q:nodo)
Línea 43: Línea 43:
 
*crear(p)
 
*crear(p)
 
*FIN
 
*FIN
==Clasificación de Árboles Binarios==
+
 
 +
==Clasificación ==
 
Existen cuatro tipos de árbol binario:.
 
Existen cuatro tipos de árbol binario:.
 
*A. B. Distinto.
 
*A. B. Distinto.
Línea 49: Línea 50:
 
*A. B. Equivalentes.
 
*A. B. Equivalentes.
 
*A. B. Completos.
 
*A. B. Completos.
==A. B. DISTINTO==
+
 
 +
==A. B. distinto==
 
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.  
 
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.  
  
Línea 55: Línea 57:
  
 
[[Archivo:Extructura_diferente.jpg]]
 
[[Archivo:Extructura_diferente.jpg]]
==A. B. SIMILARES==
+
==A. B. similares==
 
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.  
 
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.  
  
Línea 61: Línea 63:
  
 
[[Archivo:Similar.jpg]]
 
[[Archivo:Similar.jpg]]
==A. B. EQUIVALENTES==
+
==A. B. equibalentes==
 
Son aquellos árboles que son similares y que además los nodos contienen la misma información.  
 
Son aquellos árboles que son similares y que además los nodos contienen la misma información.  
  
Línea 68: Línea 70:
 
[[Archivo:Equivalente_.jpg]]
 
[[Archivo:Equivalente_.jpg]]
  
==A. B. COMPLETOS==
+
==A. B.completos==
 
Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.
 
Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.
 
==Recorrido de un Árbol Binario==
 
==Recorrido de un Árbol Binario==
 
Hay tres maneras de recorrer un árbol: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:
 
Hay tres maneras de recorrer un árbol: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:
==INORDEN==
+
==Inorden==
 
*Recorrer el subarbol izquierdo en inorden.
 
*Recorrer el subarbol izquierdo en inorden.
 
*Examinar la raíz.
 
*Examinar la raíz.
 
*Recorrer el subarbol derecho en inorden.
 
*Recorrer el subarbol derecho en inorden.
==PREORDEN==
+
==Preorden==
 
*Examinar la raíz.
 
*Examinar la raíz.
 
*Recorrer el subarbol izquierdo en preorden.
 
*Recorrer el subarbol izquierdo en preorden.
 
*recorrer el subarbol derecho en preorden.
 
*recorrer el subarbol derecho en preorden.
==POSTORDEN==
+
==Posorden==
 
*Recorrer el subarbol izquierdo en postorden.
 
*Recorrer el subarbol izquierdo en postorden.
 
*Recorrer el subarbol derecho en postorden.
 
*Recorrer el subarbol derecho en postorden.
 
*Examinar la raíz.
 
*Examinar la raíz.
 
Ejemplo de los diferentes recorridos en un árbol binario.
 
Ejemplo de los diferentes recorridos en un árbol binario.
 
  
 
[[Archivo:Recorrido2.jpg ‎]]
 
[[Archivo:Recorrido2.jpg ‎]]
Línea 92: Línea 93:
 
*Preorden: ABDGEHICFJK
 
*Preorden: ABDGEHICFJK
 
*Postorden: GDHIEBKJFCA
 
*Postorden: GDHIEBKJFCA
 +
 
==Arboles Enhebrados==
 
==Arboles Enhebrados==
 
Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha.
 
Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha.
Línea 98: Línea 100:
  
 
*ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor.
 
*ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor.
*ARBOL ENHEBRADO A LA IZQUIERDA. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden
+
*ARBOL ENHEBRADO A LA IZQUIERDA. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden.
 +
 
 
==Árboles en Montón==
 
==Árboles en Montón==
 
Esta sección consiste en transformar un bosque en un árbol binario. Entenderemos como bosque a un conjunto normalmente ordenado de dos o más árboles generales.
 
Esta sección consiste en transformar un bosque en un árbol binario. Entenderemos como bosque a un conjunto normalmente ordenado de dos o más árboles generales.
Línea 106: Línea 109:
 
*Enlazar verticalmente el nodo padre con el hijo que se encuentra más a la izquierda. Además debe eliminarse el vínculo de ese padre con el resto de sus hijos.
 
*Enlazar verticalmente el nodo padre con el hijo que se encuentra más a la izquierda. Además debe eliminarse el vínculo de ese padre con el resto de sus hijos.
 
*Debe rotarse el diagrama resultante aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.
 
*Debe rotarse el diagrama resultante aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.
 +
 
==Fuente==
 
==Fuente==
 
*[https://www.monografias.com/trabajos92/arboles-binario/arboles-binario.shtml]
 
*[https://www.monografias.com/trabajos92/arboles-binario/arboles-binario.shtml]
Línea 111: Línea 115:
 
*[https://www.utm.mx/~rruiz/cursos/ED/material/ABB.pdf]
 
*[https://www.utm.mx/~rruiz/cursos/ED/material/ABB.pdf]
  
==Enlaces Externos==
+
==Enlaces externos==
https://es.wikipedia.org/wiki/Árbol_binario
+
*[https://es.wikipedia.org/wiki/Árbol_binario/ es.wikipedia.org].
[[Category: Definición]]
+
[[Category:Informática]]

Revisión del 15:10 16 oct 2019

Árbol binario
Información sobre la plantilla
7 KB
Concepto:En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").

Árbol binario. A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

La representación gráfica de un árbol binario es la siguiente:

Árbol binario.jpg

Representación en memoria

Hay dos formas tradicionales de representar un árbol binario en memoria:

  • Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
  • Por medio de arreglos.
  • Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
  • Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.

El algoritmo de creación de un árbol binario

Procedimiento crear (q:nodo)

  • inicio
  • mensaje("Rama izquierda?")
  • lee(respuesta)
  • si respuesta = "si" entonces
  • new(p)
  • q(li) <-- nil
  • crear(p)
  • en caso contrario
  • q(li) <-- nil
  • mensaje("Rama derecha?")
  • lee(respuesta)
  • si respuesta="si" entonces
  • new(p)
  • q(ld)<--p
  • crear(p)
  • en caso contrario
  • q(ld) <--nil
  • fin
  • INICIO
  • new(p)
  • raiz<--p
  • crear(p)
  • FIN

Clasificación

Existen cuatro tipos de árbol binario:.

  • A. B. Distinto.
  • A. B. Similares.
  • A. B. Equivalentes.
  • A. B. Completos.

A. B. distinto

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.

Ejemplo:

Extructura diferente.jpg

A. B. similares

Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.

Ejemplo:

Similar.jpg

A. B. equibalentes

Son aquellos árboles que son similares y que además los nodos contienen la misma información.

Ejemplo:

Equivalente .jpg

A. B.completos

Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.

Recorrido de un Árbol Binario

Hay tres maneras de recorrer un árbol: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

Inorden

  • Recorrer el subarbol izquierdo en inorden.
  • Examinar la raíz.
  • Recorrer el subarbol derecho en inorden.

Preorden

  • Examinar la raíz.
  • Recorrer el subarbol izquierdo en preorden.
  • recorrer el subarbol derecho en preorden.

Posorden

  • Recorrer el subarbol izquierdo en postorden.
  • Recorrer el subarbol derecho en postorden.
  • Examinar la raíz.

Ejemplo de los diferentes recorridos en un árbol binario.

Recorrido2.jpg

  • Inorden: GDBHEIACJKF
  • Preorden: ABDGEHICFJK
  • Postorden: GDHIEBKJFCA

Arboles Enhebrados

Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha.

Enhebrados.jpg

  • ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor.
  • ARBOL ENHEBRADO A LA IZQUIERDA. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden.

Árboles en Montón

Esta sección consiste en transformar un bosque en un árbol binario. Entenderemos como bosque a un conjunto normalmente ordenado de dos o más árboles generales. La serie de pasos que debemos seguir para lograr la conversión de un bosque en un árbol binario es la siguiente:

  • Enlazar horizontalmente las raíces de los distintos árboles generales.
  • Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
  • Enlazar verticalmente el nodo padre con el hijo que se encuentra más a la izquierda. Además debe eliminarse el vínculo de ese padre con el resto de sus hijos.
  • Debe rotarse el diagrama resultante aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.

Fuente

Enlaces externos