Arbolbinario

UNIVERSIDAD NACIONAL
JOSÉ FAUSTINO SÁNCHEZ CARRIÓN

FACULTAD DE INGENIERÍA

ESCUELA ACADEMICA PROFESIONAL
DE INGENIERÍA DE SISTEMAS



CURSO
LENGUAJE DE PROGRAMACIÓN II


SEPARATA
“ARBOLES BINARIOS”
(Contiene código en C#)




DOCENTE
ING. JAVIER ALBERTO MANRIQUE QUIÑONEZ


HUACHO – PERU

2012-I
Estructura de datos

En programación, una estructura de datos es unaforma de organizar un conjunto de datos elementales con el objetivo de facilitar la manipulación de estos datos como un todo y/o individualmente.


Una estructura de datos define la organización y interrelacionamiento de estos, y un conjunto de operaciones que se pueden realizar sobre él. Las operaciones básicas son:

• Alta, adicionar un nuevo valor a la estructura.
• Baja, borrar un valor dela estructura.
• Búsqueda, encontrar un determinado valor en la estructura para se realizar una operación con este valor.

Otras operaciones que se pueden realizar son:
• Ordenamiento, de los elementos pertenecientes a la estructura.
• Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Cada estructura ofrece ventajas y desventajas en relación a lasimplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como las frecuencias y el orden en que se realiza cada operación sobre los datos.

Algunas estructuras de datos utilizadas en programación:

• Arreglos: Vectores, Matrices
• Listas Enlazadas : Listas Simples, Listas Dobles, ListasCirculares, Pilas (stack)
• Colas(queue), Colas de Prioridad
• Pilas (snack)
• Árboles: Árboles Binarios, Árboles AVL, Árboles Rojo-Negro, Árboles B.
• Grafos
• Conjuntos (set)
• Tablas Hash
• Montículos (o heaps)
Árbol
En ciencias de la computación, un árbol es una estructura de datos comúnmente usada que emula la estructura de un árbol con un conjunto de nodos conectados. Cada nodo tienecero o más nodos hijos, que están por debajo de él. El nodo del cual un nodo es hijo es llamado su nodo padre. Un hijo tiene como máximo un padre; un nodo sin padre es llamado nodo raíz (o simplemente raíz). Los nodos sin hijos son llamados hojas.

Un Árbol Binario es un tipo de árbol ordenado, en el que ningún nodo puede tener dos o más subárboles. En un árbol binario, cada nodo puede tenercero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.


Hay muchas formas diferentes de representar un árbol, representaciones comunes muestran los nodos como variables localizadas en el montículo como punteros a sus hijos, sus padres, o juntos, o como elementos de un array, con relaciones entre determinadas posicionesen el arreglo (ej., heap binario).


[pic]


[pic]


Estructura de un árbol binario

La estructura de un árbol binario se construye con nodos. Cada nodo debe contener el campo de datos (datos a almacenar que puede ser una estructura) y dos campos referencia, uno al subárbol izquierdo y otro al subárbol derecho, que se conocen como referencia izquierdo (izquierdo, Izquierdo) yreferencia derecho (derecho, Derecho) respectivamente.

Un valor NULL que índica que el nodo no tiene descendientes.


[pic]

Operaciones en árboles binarios

• Creación del árbol binario
• Insertar elementos
• Visualizar el árbol por pantalla o impresora:

❖ Con recorrido Preorden
❖ Con recorrido Inorden
❖ Con recorrido Postorden
• Eliminar u determinado elementodel árbol
• Determinar el número de elementos: hojas, nodos padres, nodos hijos, nodos con un solo hijo izquierdo/derecho, nodos a la izquierda/derecha de la raíz, etc.
• Determinar el mínimo/máximo valor
• Determinar su altura.
• Determinar el nivel del árbol binario
• Hacer copia del árbol
• Determinar si dos árboles binarios son idénticos
• Borrar (eliminar el árbol)
• Si es árbol de...