Catedrático: Ricardo Woolery

Alumno: Jorge Geovanny Martínez

Benítez

Asignatura: Tarea 6 Estructura de Datos

Cuenta: 201510060235

Fecha: 2019

Ingeniería en computación
 INTRODUCCION

Un árbol es una estructura de datos ampliamente usada que emula la forma de

un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que
se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se
dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b
(en ese caso, también decimos que es hijo de a). Sólo puede haber un único
nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce
como hoja.

El árbol También se define como una estructura de datos no lineal. Esta

estructura se usa principalmente para representar datos con una relación
jerárquica entre sus elementos, como por ejemplo registros, árboles
genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de
árbol que es, llamado árbol binario, que puede ser implementado fácilmente en
la computadora.

Una estructura de datos es una forma de organizar un conjunto de datos

elementales (un dato elemental es la mínima información que se tiene en el
sistema) con el objetivo de facilitar la manipulación de estos datos como un
todo o individualmente.
 LISTA MINIMA DE PALABRAS CLAVE

ÁRBOL: un árbol es un tipo abstracto de datos (TAD) ampliamente usado que

imita la estructura jerárquica de un árbol, con un valor en la raíz

ÁRBOLES BINARIOS: Los árboles binarios son estructuras de datos muy

similares a las listas doblemente enlazadas, en el sentido que tienen dos
punteros que apuntan a otros elementos, pero no tienen una estructura lógica
de tipo lineal o secuencial como aquellas, sino ramificada.  Tienen aspecto de
árbol, de ahí su nombre.
Un árbol binario es una estructura de datos no lineal en la que cada nodo
puede apuntar a uno o máximo a dos nodos. También se suele dar una
definición recursiva que indica que es una estructura compuesta por un dato y
dos árboles. Esto son definiciones simples. Este tipo de árbol se caracteriza
porque tienen un vértice principal y de él se desprende dos ramas. La rama
izquierda y la rama derecha a las que también se les conoce como subárboles.

NODOS: De forma muy general, un nodo es un punto de intersección o unión

de varios elementos que confluyen en el mismo lugar El término nodo puede
referirse a otros conceptos: En términos generales, un nodo es un espacio real
o abstracto en el que confluyen parte de las conexiones de otros espacios
reales o abstractos que comparten sus mismas características y que a su vez
también son nodos. Todos se interrelacionan de una manera no jerárquica y
conforman lo que en términos Sociológicos o Matemáticos se llama Red. Un
nodo, en electricidad, es un punto de conexión entre dos o más elementos de
un circuito. En Astronomía, un nodo es cualquiera de los dos puntos en que
una Órbita corta a un plano de referencia, que puede ser la Eclíptica o el
[[ecuador celeste. Hay dos nodos: nodo ascendente, cuando el cuerpo, al
seguir la órbita, pasa del sur al norte, y nodo descendente, cuando pasa del
norte al sur. Ambos nodos están diametralmente opuestos.
TIPOS DE NODOS:
Los nodos asimétricos hacen que su línea de intersección adopte la forma de
una esquina o un punto cuando se ajusta la posición de los puntos de control
del nodo.
Los nodos uniformes hacen que su línea de intersección adopte la forma de
una curva. Cada punto de control se puede alargar o acortar por separado, lo
que permite ángulos más pequeños o grandes.
Los nodos simétricos hacen que su línea de intersección adopte la forma de
una curva, además de cruzar el nodo exactamente con el mismo ángulo.
Los nodos de línea permiten dar forma a los objetos cambiando la forma de
sus segmentos. Puede hacer que un segmento curvo sea recto o que un
segmento recto sea curvo.

SUBÁRBOL: Sub-Árbol: Conocemos como Sub-Árbol a todo Árbol generado a

partir de una sección determinada del Árbol, Por lo que podemos decir que un
Árbol es un nodo Raíz con N Sub-Árboles.
TIPOS DE SUBÁRBOL:
Existen escenarios donde podemos sacar un Sub-Árboles del Árbol para
procesarlo de forma separada, de esta forma el Sub-Árboles pasa a ser un
Árbol independiente, También podemos eliminar Sub-Árboles completos,
Agregarlos, entre otras operaciones.

Árbol n-ario
los arboles n-arios son aquellos arboles donde el número máximo de hijos por
nodo es de N, en la figura 7 podemos apreciar dos árboles con grado 2 y grado
3, estos dos árboles también los podemos definir como Árbol n-ario con n = 2 y
n=3 respectivamente.

Árboles binarios
Árbol binario lleno: Es aquel que el que todos los nodos tiene cero o 2 hijos con
excepción de la Raíz.
Árbol binario perfecto: Es un Árbol lleno en donde todos las Hojas están en el
mismo Nivel.

ARISTA: La arista corresponde a una relación entre dos vértices de un grafo.

Para caracterizar un grafo G son suficientes únicamente el conjunto de todas
sus aristas, comúnmente denotado con la letra E (del término en inglés edge),
junto con el conjunto de sus vértices, denotado por V. Así, dicho grafo se puede
representar como G(V,E), o bien G = (V,E).
En un grafo, dos vértices son adyacentes si están conectados por una arista.
En tal caso, cada uno de estos vértices es incidente a dicha arista.

Gráficamente las aristas se representan, para el caso de los grafos no dirigidos,

como una línea que une a los dos vértices. Si el grafo es dirigido, entonces la
arista se representa como una flecha, que parte del nodo origen y apunta al
nodo destino.
Algebraicamente, dados dos vértices a y b pertenecientes al conjunto V, una
arista se define, para un grafo no dirigido, como el conjunto e = {a,b} (o {b,a}),
en tanto que para un grafo dirigido, como el par ordenado e = (a,b) (donde (b,a)
representaría una arista diferente, con el nodo origen y destino cambiados). En
ambos casos, e ∈ E.

AMINO: Radical monovalente formado por un átomo de nitrógeno y dos de

hidrógeno, que constituye el grupo funcional de las aminas y otros compuestos
orgánicos: denota la presencia de un radical =NH 2 unido a un radical no ácido.

PROFUNDIDAD: profundidad, del latín profunditas, es la cualidad de

profundo (algo que resulta más hondo que lo regular, que se encuentra
extendido a lo largo o que penetra mucho)

NIVEL: instrumento de nivelación, la posición relativa de determinados

conjuntos de elementos en su disposición en diferentes planos de organización
de un sistema; se sugiere, de este modo, una disposición según una jerarquía;
a su vez, una jerarquía o nivel determinado, puede ser considerado como
sistema, dentro del sistema más general

ÁRBOL BINARIO COMPLETO:

Es un árbol binario de profundidad K que tiene todos los nodos posibles hasta 
el penúltimonivel (profundidad K-1), y donde los elementos del último nivel está
n colocados de izquierda a derecha sin dejarhuecos entre ellos.

ÁRBOL COMPLETO: Un árbol completo se caracteriza porque todos sus

nodos terminales tienen la misma altura.

Un árbol binario se dice que es completo, si todos los nodos del árbol, excepto
los del ultimo nivel tienen dos hijos: Sub árbol izquierdo y sub árbol derecho.

ÁRBOL BINARIO EXTENDIDO: es un árbol binario al que se le han agregado

nodos terminales donde existían enlaces nulos.

REPRESENTACIONES DE ÁRBOLES:
Hay muchas maneras diferentes para representar árboles; las representaciones
más comunes representan a los nodos dinámicamente como registros con
punteros a sus hijos, a sus padres, o a ambos, o como elementos de un vector,
con relaciones entre ellos determinadas por sus posiciones en este (por
ejemplo, un montículo binario).
De hecho, un árbol binario puede ser implementado como una lista de listas
(una lista donde los valores son listas): la cabeza de una lista (el valor del
primer término) es el hijo izquierdo, mientras que la cola (la lista de los
términos segundo y siguientes) es el hijo derecho. Esto puede ser modificado
para permitir que los valores, como en las listas de expresión simbólica
(expresión S), en donde la cabeza (valor de primer término) es el valor del
nodo, la cabeza de la cola (valor de segundo término) sea el hijo izquierdo, y la
cola de la cola (lista de términos sucesorios) sea el hijo derecho.
En general un nodo en un árbol no tendrá punteros a sus padres, pero esta
información puede ser incluida (ampliando la estructura de datos para incluir
también un puntero al vector) o almacenarse por separado. Alternativamente,
los enlaces ascendentes pueden ser incluidos en los datos del nodo hijo, como
en un árbol binario enlazado.
RECORRIDO:
Comparado a las estructuras de datos lineales como las listas
enlazadas y arreglos unidimensionales, que tienen un método canónico de
recorrido, las estructuras arborescentes pueden ser recorridas de muchas
maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres pasos
principales que pueden ser realizados y el orden en la cual son realizados
define el tipo de recorrido. Estos pasos (en ningún orden particular) son:
ejecución de una acción en el nodo actual (referido como “visitando” el nodo),
recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la
derecha. Así el proceso más fácilmente descrito a través de la recursión.
Los nombres dados para un estilo particular de recorrido vienen de la posición
del elemento de raíz con respecto a los nodos izquierdo y derecho. Imagine
que los nodos izquierdo y derecho son constantes en espacio, entonces el
nodo raíz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre
el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-
orden).
Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre
prioridad sobre los nodos derechos. Este ordenamiento puede ser invertido
mientras el mismo orden sea asumido para todos los métodos de recorrido.

TIPOS DE RECORRIDO:
Recorrido en profundidad-primero
Recorrido en anchura-primero
Recorrido en orden por nivel basado en cola
Recorrer el subárbol izquierdo en postorden.
Recorrer el subárbol derecho en postorden.
Examinar la raíz.

ÁRBOL BINARIO DE BÚSQUEDA: La búsqueda en árboles binarios es un

método de búsqueda simple, dinámico y eficiente considerado como uno de los
fundamentales en Ciencia de la Computación. De toda la terminología sobre
árboles, tan sólo recordar que la propiedad que define un árbol binario es que
cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha. Para
construir los algoritmos consideraremos que cada nodo contiene un registro
con un valor clave a través del cual efectuaremos las búsquedas. En las
implementaciones que presentaremos sólo se considerará en cada nodo del
árbol un valor del tipo t Elemento aunque en un caso general ese tipo estará
compuesto por dos: una clave indicando el campo por el cual se realiza la
ordenación y una información asociada a dicha clave o visto de otra forma, una
información que puede ser compuesta en la cual existe definido un orden.
Un árbol binario de búsqueda(ABB) es un árbol binario con la propiedad de que
todos los elementos almacenados en el subárbol izquierdo de cualquier
nodo x son menores que el elemento almacenado en x,y todos los elementos
almacenados en el subárbol derecho de x son mayores que el elemento
almacenado en x.

OPERACIONES DE ÁRBOLES BINARIOS DE BÚSQUEDA: El procedimiento

de inserción en un árbol binario de búsqueda es muy sencillo, únicamente hay
que tener cuidado de no romper la estructura ni el orden del árbol.
Cuando se inserta un nuevo nodo en el árbol hay que tener en cuenta que cada
nodo no puede tener más de dos hijos, por esta razón si un nodo ya tiene 2
hijos, el nuevo nodo nunca se podrá insertar como su hijo. Con esta restricción
nos aseguramos mantener la estructura del árbol, pero aún nos falta mantener
el orden.
Para localizar el lugar adecuado del árbol donde insertar el nuevo nodo se
realizan comparaciones entre los nodos del árbol y el elemento a insertar. El
primer nodo que se compara es la raíz, si el nuevo nodo es menor que la raíz,
la búsqueda prosigue por el nodo izquierdo de éste. Si el nuevo nodo fuese
mayor, la búsqueda seguiría por el hijo derecho de la raíz.
Este procedimiento es recursivo, y su condición de parada es llegar a un nodo
que no tenga hijo en la rama por la que la búsqueda debería seguir. En este
caso el nuevo nodo se inserta en ese hueco, como su nuevo hijo.
El borrado en árboles binarios de búsqueda es otra operación bastante sencilla
excepto en un caso. Vamos a ir estudiando los distintos casos.
Tras realizar la búsqueda del nodo a eliminar observamos que el nodo no tiene
hijos. Este es el caso más sencillo, únicamente habrá que borrar el elemento y
ya habremos concluido la operación.
Si tras realizar la búsqueda nos encontramos con que tiene un sólo hijo. Este
caso también es sencillo, para borrar el nodo deseado, hacemos una especie
de puente, el padre del nodo a borrar pasa a apuntar al hijo del nodo borrado.

LISTA ADICIONAL DE PALABRAS CLAVE DE LA UNIDAD

GRAFOS:
Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de
arcos o aristas A. Los vértice se denominan también nodos o puntos.
Un arco, es un par ordenado de vértices (V,W) donde V es el vértice inicial y W
es el vértice terminal del arco. Un arco se expresa como: V–>W y se
representa de la siguiente manera:
711.jpg
Los vértice de un grafo pueden usarse para representar objetos. Los arcos se
utilizan para representar relaciones entre estos objetos.
Las aplicaciones más importantes de los grafos son las siguientes:
Rutas entre ciudades.
Determinar tiempos máximos y mínimos en un proceso.
Flujo y control en un programa.
Operaciones Sobre Grafos:
En esta sección analizaremos algunas de las operaciones sobre grafos, como :
Creación.
Inserción.
Búsqueda.
Eliminación.
En esta sección, continuaremos utilizando los apuntadores que se usaron en
las secciones anteriores. TOP para hacer referencia al primer nodo, LD para
indicar liga derecha y LA para indicar liga abajo, por último usaremos los
 apuntadores P y Q para hacer referencia a los nuevos nodos que vayan a ser
usados.

BALANCEO ARBOLES BINARIOS

En ciencias de la computación, un árbol binario de búsqueda auto-

balanceable o equilibrado es un árbol binario de búsqueda que intenta
mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños
como sea posible en todo momento, automáticamente. Esto es importante, ya
que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo
proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios
pueden tomar alturas muy grandes en situaciones normales, como cuando las
claves son insertadas en orden. Mantener baja la altura se consigue
habitualmente realizando transformaciones en el árbol, como la rotación de
árboles, en momentos clave.
Tiempos para varias operaciones en términos del número de nodos en el
árbol n:
Para algunas implementaciones estos tiempos son el peor caso, mientras que
para otras están amortizados.
Estructuras de datos populares que implementan este tipo de árbol:
 Árbol AVL
 Árbol rojo-negro
Operación Tiempo en cota superior asintótica
Búsqueda O(log n)
Inserción O(log n)
Eliminación O(log n)
Iteración en orden O(n)

CLASES PARA IMPLEMENTACION DE ARBOLES

 Dado que los árboles binarios son de estructura fundamental en la teoría
de los árboles, será preciso disponer de algún mecanismo que permita la
conversión de un árbol general en árbol binario.
“Los árboles binarios son más fáciles de programar que los generales”. En esto
es imprescindible deducir cuántas ramas o caminos se desprenden de un nodo
en un momento dado. Por ello, y dado que de los árboles binarios siempre se
cuelgan como máximo dos subárboles, su programación será más sencilla.
Afortunadamente, existe una técnica para convertir un árbol general a formato
de un árbol binario.
LISTAS ENLAZADAS CIRCULARES
En una lista enlazada circular, el primer y el último nodo están unidos juntos.
Esto se puede hacer tanto para listas enlazadas simples como para las
doblemente enlazadas. Para recorrer un lista enlazada circular podemos
empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se
regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas
circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas
es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los
nodos de una lista a partir de uno dado.

PILAS
Las pilas son otro tipo de estructura de datos lineales, las cuales presentan
restricciones en cuanto a la posición en la cual pueden realizarse las
inserciones y las extracciones de elementos.
Una pila es una lista de elementos en la que se pueden insertar y eliminar
elementos sólo por uno de los extremos. Como consecuencia, los elementos
de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el
último elemento que se metió a la pila será el primero en salir de ella.
En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en
una alacena, una pila de latas en un supermercado, una pila de papeles sobre
un escritorio, etc.
Debido al orden en que se insertan y eliminan los elementos en una pila,
también se le conoce como estructura LIFO (Last In, First Out: último en entrar,
primero en salir). 
TIPOS DE DATOS 

Simples:
Son todos aquellos que abarcan una sola casilla de memoria como los
boléanos, enteros, flotantes, etc.
Estructurales:
Arreglos de cadenas, pilas o estructuras, abarcan más de una casilla de
memoria.
 MAPA
MAPA CONCEPTUAL
CONCEPTUAL

ÁRBOLES BINARIOS: Los

ÁRBOLES BINARIOS: Los árboles
árboles
binarios NODOS:
NODOS: De De forma
forma muymuy general,
general, unun
ÁRBOL: binarios son estructuras de
son estructuras de datos muy
datos muy
ÁRBOL: un árbol es
un árbol es un tipo
un tipo abstracto
abstracto similares nodo
nodo es
es un
un punto
punto de de intersección
intersección oo
de similares aa las
las listas
listas doblemente
doblemente
de datos
datos (TAD) ampliamente
(TAD) ampliamente usado
usado enlazadas, en el sentido que tienen unión
unión de
de varios
varios elementos
elementos que que
que imita la estructura jerárquica de enlazadas, en el sentido que tienen confluyen en el
que imita la estructura jerárquica de dos
dos punteros
punteros que
que apuntan
apuntan aa otros
otros confluyen en el mismo
mismo lugar
lugar ElEl
un
un árbol, con un valor en la raíz
árbol, con un valor en la término
raíz elementos,
elementos, pero
pero nono tienen
tienen una
una término nodo
nodo puede
puede referirse
referirse aa otros
otros
estructura conceptos:
conceptos: En términos generales, un
En términos generales, un
estructura lógica
lógica dede tipo lineal oo
tipo lineal nodo es un
un espacio
secuencial como aquellas,
secuencial como aquellas, sino
sino nodo es espacio real
real oo abstracto
abstracto
ramificada.  Tienen aspecto en
en el
el que
que confluyen
confluyen parte
parte de
de las
las
ramificada.  Tienen aspecto dede árbol,
árbol, conexiones
de ahí su nombre.
de ahí su nombre. conexiones dede otros
otros espacios
espacios reales
reales oo
abstractos
abstractos que
que comparten
comparten sus sus mismas
mismas
características y que a su vez también
características y que a su vez también
son nodos.
son nodos.

TIPOS AMINO:
AMINO: Radical
Radical monovalente
monovalente formado
formado
TIPOS DE
DE NODOS:
NODOS: SUBÁRBOL:
SUBÁRBOL: Sub-Árbol: Conocemos
Sub-Árbol: Conocemos por
como Sub-Árbol por un
un átomo
átomo dede nitrógeno
nitrógeno yy dos
dos de
de
Los nodos
Los nodos de
de línea 
línea  como Sub-Árbol aa todo Árbol generado
todo Árbol generado hidrógeno,
hidrógeno, que
que constituye
constituye el
el grupo
grupo
aa partir de RECORRIDO:
Los nodos uniformes 
uniformes  partir de una
una sección
sección determinada
determinada funcional de las aminas y otros
funcional de las aminas y otros
RECORRIDO:
Los nodos del TIPOS
TIPOS DESUBARBOLES
del Árbol, Por lo que podemos decir
Árbol, Por lo que podemos decir compuestos
compuestos orgánicos: denota la
orgánicos: denota la DESUBARBOLES Comparado
Comparado aa las
las estructuras
estructuras dede datos
datos
PROFUNDIDAD:
PROFUNDIDAD: profundidad, del
profundidad, del
Los nodos
Los nodos simétricos  que
simétricos  que un
un Árbol
Árbol es
es un
un nodo Raíz con
nodo Raíz con NN
presencia Árbol
Árbol n-ario lineales
lineales como
como las listas
las listas
latín profunditas,
latín profunditas, es
es la cualidad
la cualidad de
de
Sub-Árboles. presencia de
de un
un radical
radical =NH
=NH22 unido
 unido aa n-ario
profundo (algo
Los nodos
Los nodos asimétricos 
asimétricos  Sub-Árboles. un Árboles binarios enlazadas y arreglos unidimensionales,
enlazadas y arreglos unidimensionales, profundo (algo que
que resulta
resulta más
más hondo
hondo
un radical
radical no
no ácido.
ácido. Árboles binarios que que
que lo
lo regular,
regular, que
que se
se encuentra
ÁRBOL
ÁRBOL BINARIO
BINARIO COMPLETO:
COMPLETO:
Árbol que tienen
tienen un
un método
método canónico
canónico dede encuentra NIVEL:
NIVEL: instrumento
instrumento de de nivelación, la
Árbol binario
binario lleno: 
lleno:  recorrido, las estructuras
recorrido, las estructuras
extendido
extendido aa lo
lo largo
largo oo que
que penetra
penetra posición
nivelación, la Es un árbol binario de profundidad K q
Es un árbol binario de profundidad K q
Árbol binario
binario perfecto arborescentes mucho) posición relativa
relativa de
de determinados
determinados ue tiene todos los nodos posibles hasta
Árbol perfecto arborescentes pueden
pueden ser
ser recorridas
recorridas mucho) conjuntos de elementos
conjuntos de elementos en su en su ue tiene todos los nodos posibles hasta
de  el penúltimonivel (profundidad K-
de muchas
muchas maneras
maneras diferentes.
diferentes. disposición
disposición en
en diferentes
diferentes planos
planos dede
 el penúltimonivel (profundidad K-
1), y donde los elementos del último ni
1), y donde los elementos del último ni
organización
organización de de un
un sistema;
sistema; sese vel están colocados de izquierda a dere
sugiere, vel están colocados de izquierda a dere
sugiere, de
de este
este modo,
modo, unauna cha sin dejarhuecos entre ellos.
cha sin dejarhuecos entre ellos.
disposición
disposición según
según una
una jerarquía;
jerarquía; aa su
su
vez,
vez, una
una jerarquía
jerarquía oo nivel
nivel
ÁRBOL
ÁRBOL COMPLETO:
COMPLETO: Un Un árbol
árbol REPRESENTACIONES
REPRESENTACIONES DE DE ÁRBOLES:
ÁRBOLES: determinado, puede ser considerado
completo determinado, puede ser considerado
completo se
se caracteriza
caracteriza porque
porque todos
todos ÁRBOL
ÁRBOL BINARIO
BINARIO EXTENDIDO:
EXTENDIDO: es es un
un
Hay muchas
Hay muchas maneras
maneras diferentes
diferentes para
para como
como sistema,
sistema, dentro
dentro del
del sistema
sistema
sus
sus nodos terminales tienen la
nodos terminales tienen la misma representar
altura.
misma árbol
árbol binario
binario al
al que
que se
se le han agregado
le han agregado representar árboles;
árboles; las
las más
más general
general
altura. nodos representaciones más comunes
nodos terminales
terminales donde
donde existían
existían representaciones más comunes OPERACIONES
OPERACIONES DE DE ÁRBOLES
ÁRBOLES BINARIOS
BINARIOS
enlaces nulos. representan
representan aa los
los nodos DE
Un
Un árbol
árbol binario
binario se
se dice
dice que
que eses enlaces nulos. nodos
TIPOS DE BÚSQUEDA:
BÚSQUEDA: El El procedimiento
procedimiento dede
completo,
dinámicamente
dinámicamente como registros con
como registros con TIPOS DE DE RECORRIDO:
RECORRIDO: inserción
inserción en un árbol binario de
en un árbol binario de
completo, sisi todos
todos los
los nodos
nodos del
del árbol,
árbol, punteros
punteros aa sus
sus hijos,
hijos, aa sus
sus padres,
padres, oo aa Recorrido búsqueda es muy sencillo, únicamente
excepto
excepto los
los del
del ultimo
ultimo nivel
nivel tienen
tienen dos
dos ambos, Recorrido en
en profundidad-primero
profundidad-primero búsqueda es muy sencillo, únicamente
hijos: ambos, oo como
como elementos
elementos de de
Recorrido en
en anchura-primero
anchura-primero ÁRBOL
ÁRBOL BINARIO
BINARIO DE DE BÚSQUEDA:
BÚSQUEDA: La hay
hay que
que tener
tener cuidado
cuidado dede no
no romper
romper lala
hijos: Sub
Sub árbol
árbol izquierdo
izquierdo yy sub
sub árbol
árbol un vector,
un vector, con relaciones entre ellos
con relaciones entre Recorrido La
estructura
derecho. ellos
Recorrido
búsqueda
búsqueda en árboles binarios
en árboles binarios es un
es un estructura ni
ni el
el orden
orden del árbol.
del árbol.
derecho. determinadas
determinadas por sus posiciones en
por sus posiciones en Recorrido en
en orden
orden por
por nivel
nivel basado
basado método
método dede búsqueda
búsqueda simple,
simple,
este (por ejemplo, un montículo en
en cola
cola dinámico
este (por ejemplo, un montículo
binario). dinámico yy eficiente considerado
eficiente considerado
binario). Recorrer
Recorrer el subárbol izquierdo en
el subárbol izquierdo en como
como uno de los
uno de fundamentales en
los fundamentales en
postorden.
postorden. Ciencia
Ciencia de la Computación
de la Computación
Recorrer el subárbol derecho
Recorrer el subárbol derecho en en
postorden.
postorden.
Examinar
Examinar lala raíz.
raíz.
 ENSAYO
Aplicaciones del TDA Árbol en la actualidad informática
Primeramente es importante definir que referirse a TDA es hablar de tipos de
datos abstractos Un Tipo de dato abstracto (en adelante TDA) es un conjunto de
datos u objetos al cual se le asocian operaciones. El TDA provee de una interfaz con
la cual es posible realizar las operaciones permitidas, abstrayéndose de la manera
en como estén implementadas dichas operaciones. Esto quiere decir que un mismo
TDA puede ser implementado utilizando distintas estructuras de datos y proveer la
misma funcionalidad.
El paradigma de orientación a objetos permite el encapsulamiento de los datos y las
operaciones mediante la definición de clases e interfaces, lo cual permite ocultar la
manera en cómo ha sido implementado el TDA y solo permite el acceso a los datos
a través de las operaciones provistas por la interfaz.
Por lo cual considero que La ingeniería de sistemas de información ha progresado
gracias a la introducción de nuevas técnicas para construir programas. El primer
gran avance lo constituye la programación modular, que complementa a la
programación estructurada. Otros logros lo constituyen los llamados lenguajes de
cuarta generación, que permiten desarrollar sistemas de información en un lenguaje
muy especializado.
      Pero conforme avanza la tecnología de computadores es necesario crear
programas cada vez más sofisticados. En la última década ha tomado gran auge el
uso de la programación por objetos, que tiene como requisito la abstracción de
datos, y que implica una nueva manera de diseñar programas. El lenguaje
Smalltalk [GR-83] ha causado gran revuelo, hasta tal punto que existen
compiladores para lenguajes como C++ [Str-86], que han sacado la programación
por objetos de los laboratorios de investigación, para ser utilizados en el quehacer
diario de las empresas. (Una excelente discusión de los alcances de la
programación por objetos puede encontrarse en [Str-88]).
  La programación que utiliza abstracción de datos se basa en el hecho de que en un
programa se deben integrar y combinar los tipos básicos de datos, como números y
caracteres, para formar estructuras de datos más complejas y así representar
información dentro del computador. En general existe una fuerte relación entre todos
los datos manipulados por un programa, por lo que es conveniente que esa relación
esté claramente especificada y controlada, de forma que cada parte del programa
"vea" sólo lo que necesita [LG-86].
      Esto último es muy importante para separar el programa en partes
independientes, o módulos, evitando así que cambios en una parte produzcan
errores en otras partes del programa. Por ejemplo, en un programa que usa varios
arreglos y matrices para almacenar información, es frecuente que al aumentar el
tamaño de una dimensión se olvide aumentar la de los demás arreglos, por lo que el
mantenimiento del programa es más difícil. El objetivo perseguido al usar
abstracción de datos es lograr aislar todas estas dependencias, de forma que los
cambios puedan ser hechos con un mínimo de esfuerzo y en una forma localizada.
En nada ayuda tener que buscar por todo el programa en qué lugar debe hacerse
cada cambio.
      También es importante especificar mediante la abstracción de datos qué es cada
estructura de datos. Una lista, por ejemplo, es una estructura de datos que tiene un
comportamiento muy bien definido: pueden insertársele nuevos elementos,
recorrérsela, encontrar el primer y último elemento, etc. Un programador que use el
tipo de datos Lista no debe necesitar descubrir de nuevo ese concepto: simplemente
debe poderlo importar de una biblioteca.

Por ejemplo: dentro de las aplicaciones de TDA se pueden mencionar La interfaz de

este TDA provee las siguientes operaciones:
 apilar(x): inserta el elemento x en el tope de la pila (push en inglés).
 desapilar(): retorna el elemento que se encuentre en el tope de la pila y lo
elimina de ésta (pop en inglés).
 tope(): retorna el elemento que se encuentre en el tope de la pila, pero sin
eliminarlo de ésta (top en inglés).
 Esta Vacia(): retorna verdadero si la pila no contiene elementos, falso en caso
contrario (isEmpty en inglés).

Implementación del TDA pila

A continuación se muestran dos maneras de implementar una pila: utilizando un
arreglo y utilizando una lista enlazada. En ambos casos el costo de las operaciones
es de O(1).
Implementación utilizando arreglos
Para implementar una pila utilizando un arreglo, basta con definir el arreglo del tipo
de dato que se almacenará en la pila. Una variable de instancia indicará la posición
del tope de la pila, lo cual permitirá realizar las operaciones de inserción y borrado, y
también permitirá saber si la pila esta vacía, definiendo que dicha variable vale -
1 cuando no hay elementos en el arreglo.
class PilaArreglo
{
private Object[] arreglo;
private int tope;
private int MAX_ELEM=100; // máximo numero de elementos en la pila

public PilaArreglo()
{
arreglo=new Object[MAX_ELEM];
tope=-1; // inicialmente la pila esta vacía
}

public void apilar(Object x)

{
if (tope+1<MAX_ELEM) // si esta llena se produce OVERFLOW
{
 tope++;
arreglo[tope]=x;
}
El inconveniente de esta implementación es que es necesario fijar de antemano el
número máximo de elementos que puede contener la pila, MAX_ELEM, y por lo
tanto al apilar un elemento es necesario controlar que no se inserte un elemento si la
pila esta llena. Sin embargo, en Java es posible solucionar este problema creando
un nuevo arreglo más grande que el anterior, el doble por ejemplo, y copiando los
elementos de un arreglo a otro:
public void apilar(Object x)
{
if (tope+1<MAX_ELEM) // si esta llena se produce OVERFLOW
{
tope++;
arreglo[tope]=x;
}
else
{
MAX_ELEM=MAX_ELEM*2;
Object[] nuevo_arreglo=new Object[MAX_ELEM];
for (int i=0; i<arreglo.length; i++)
{
nuevo_arreglo[i]=arreglo[i];
}
tope++;
nuevo_arreglo[tope]=x;
arreglo=nuevo_arreglo;

Implementación utilizando listas enlazadas

En este caso no existe el problema de tener que fijar el tamaño máximo de la pila
(aunque siempre se está acotado por la cantidad de memoria disponible!). La
implementación es bastante simple: los elementos siempre se insertan al principio
de la lista (apilar) y siempre se extrae el primer elemento de la lista (desapilar y
tope), por lo que basta con tener una referencia al principio de la lista enlazada. Si
dicha referencia es null, entonces la pila esta vacía.
class PilaLista
{
private NodoLista lista;

public PilaLista()
{
lista=null;
}

public void apilar(Object x)

Dependiendo de la aplicación que se le de a la pila es necesario definir que acción

realizar en caso de que ocurra overflow (rebalse de la pila) o underflow (intentar
desapilar cuando la pila esta vacía). Java posee un mecanismo
denominado excepciones, que permite realizar acciones cuando se producen ciertos
eventos específicos (como por ejemplo overflow o underflowen una pila).
En ambas implementaciones el costo de las operaciones que provee el TDA tienen
costo O(1).
Ejemplo de uso: eliminación de recursividad
Suponga que una función F realiza un llamado recursivo dentro de su código, lo que
se ilustra en la siguiente figura:
Si la llamada recursiva es lo último que hace la función F, entonces dicha llamada se
puede substituir por un ciclo while. Este caso es conocido como tail recursion y en lo
posible hay que evitarlo en la programación, ya que cada llamada recursiva ocupa
espacio en la memoria del computador, y en el caso del tail recursion es muy simple
eliminarla. Por ejemplo:
void imprimir(int[] a, int j) // versión recursiva
{
if (j<a.length)
{
System.out.println(a[j]);
imprimir(a, j+1); // tail recursión
}
}

En el caso general, cuando el llamado recursivo se realiza en medio de la función F,

la recursión se puede eliminar utilizando una pila.
Por ejemplo: recorrido en pre orden de un árbol binario.
// "raiz" es la referencia a la raíz del árbol
// llamado inicial: preorden(raiz)

// versión recursiva

void preorden(Nodo nodo)

{
if (nodo!=null)
{
System.out.print(nodo.elemento);
preorden(nodo.izq);
preorden(nodo.der);

}
 Si bien los programas no recursivos son más eficientes que los recursivos, la
eliminación de recursividad (excepto en el caso de tal recursión) le quita claridad al
código del programa. Por lo tanto:
 A menudo es conveniente eliminar el tal recursión.
 Un método recursivo es menos eficiente que uno no recursivo, pero sólo en
pocas oportunidades vale la pena eliminar la recursión.
TDA cola
Una cola (queue en inglés) es una lista de elementos en donde siempre se insertan
nuevos elementos al final de la lista y se extraen elementos desde el inicio de la
lista. También se conoce a las colas como listas FIFO (FIRST IN - FIRST OUT: el
primero que entra es el primero que sale).

Las operaciones básicas en una cola son:

 encolar(x): inserta el elemento x al final de la cola (enqueue en inglés).
 sacar(): retorna el elemento que se ubica al inicio de la cola (dequeue en
inglés).
 estaVacia(): retorna verdadero si la cola esta vacía, falso en caso contrario.
Al igual que con el TDA pila, una cola se puede implementar tanto con arreglos
como con listas enlazadas. A continuación se verá la implementación usando un
arreglo.
Las variables de instancia necesarias en la implementación son:
 primero: indica el índice de la posición del primer elemento de la cola, es
decir, la posición el elemento a retornar cuando se invoque sacar.
 ultimo: indica el índice de la posición de último elemento de la cola. Si se
invoca encolar, el elemento debe ser insertado en el casillero siguiente al que indica
la variable.
 numElem: indica cuántos elementos posee la cola.
Definiendo MAX_ELEM como el tamaño máximo del arreglo, y por lo tanto de la
cola, entonces la cola esta vacía si numElem==0y está llena
si numElem==MAX_ELEM.

Un detalle faltante es el siguiente: ¿qué pasa si la variable ultimo sobrepasa el rango

de índices del arreglo? Esto se soluciona definiendo que si después de insertar un
elemento el índice ultimo == MAX_ELEM, entonces se asigna ultimo = 0 , y los
siguientes elementos serán insertados al comienzo del arreglo. Esto no produce
ningún efecto en la lógica de las operaciones del TDA, pues siempre se saca el
elemento referenciado por el índice primero, aunque en valor absoluto primero >
ultimo. Este enfoque es conocido como implementación con arreglo circular, y la
forma más fácil de implementarlo es haciendo la aritmética de subíndices
módulo MAX_ELEM.

class ColaArreglo
{
private Object[] arreglo;
private int primero, ultimo, numElem;
private int MAX_ELEM=100; // maximo número de elementos en la cola
 Nuevamente en este caso, dependiendo de la aplicación, se debe definir qué hacer
en caso de producirse OVERFLOW o UNDERFLOW.
Con esta implementación, todas las operaciones del TDA cola tienen costo O(1).
TDA Cola de Prioridad
Una cola de prioridad es un tipo de datos abstracto que almacena un conjunto de
datos que poseen una llave perteneciente a algún conjunto ordenado, y
permite insertar nuevos elementos y extraer el máximo (o el mínimo, en caso de que
la estructura se organice con un criterio de orden inverso).
Es frecuente interpretar los valores de las llaves como prioridades, con lo cual la
estructura permite insertar elementos de prioridad cualquiera, y extraer el de mejor
prioridad.
Dos formas simples de implementar colas de prioridad son:
 Una lista ordenada:
o Inserción: O(n)
o Extracción de máximo: O(1)
 Una lista desordenada:
o Inserción: O(1)
o Extracción de máximo: O(n)

Por lo cual en base a las aplicaciones del TDA Árbol en la actualidad informática.
cuyo código fuente esté disponible, de forma que permita diseñar una aplicación
capaz de mostrar animaciones con explicaciones claras sobre los pasos que se
están llevando a cabo cuando se realiza cualquier tipo de operaciones, todo esto con
un enfoque pedagógico, gracias a el cual se garantiza el aprendizaje. En Internet
existen una serie de sitios con animaciones del TDA ABB, para árboles AVL,
Rojo/Negro, y Biselado, pero la mayoría no explica el proceso que se muestra de
manera gráfica y en ocasiones son tan rápidas que no se percibe el concepto del
algoritmo que se está utilizando. Las opciones para los estudiantes se ven reducidas
además por la barrera del idioma, y aunque en este tipo de carreras se debe tener la
habilidad al menos de leer inglés, no todos han adquirido el conocimiento en esta
etapa de la carrera. Desde el punto de vista de programación se pretende acotar dos
problemas: La programación de los algoritmos para el TDA, sin perder de vista que
muchos de estos algoritmos están ya definidos, pero intentando buscar variantes
suficientemente claras para que sean entendidos con mayor facilidad por los
estudiantes. La representación gráfica de árboles, tomando como referencia la teoría
existente para la representación de grafos.

CONCLUSIONES
Como podemos ver, el uso de grafos y árboles es de mucha importancia y no
sólo en la rama de la informática, sino en el estudio de diferentes ciencias e
incluso en la vida cotidiana como es el sistema de transporte o hasta en los
deportes.

He observado que los árboles son estructuras bastante complejas, tiene una
gran aplicación en la ciencia y en la programación convencional. En los
últimos años este tipo de estructuras ha sido utilizado con mucha frecuencia
en la Inteligencia artificial.
En esta asignación se han valorado factores como ser los puntos vas
relevantes a en cuenta a lo que son los árboles y los principales métodos de
búsqueda, sin embargo estamos lejos de cubrir este tema en profundidad ya
que existen muchísimos tipos de operaciones y algoritmos que se pueden
realizar sobre estas estructuras de datos.

REFERENCIAS BIBLIOGRAFICAS
Vázquez, A. (2012) Recorrido inorden. Video de youtube.
http://brd.unid.edu.mx/recorrido-inorden/