Arboles

Instituto Universitario Politécnico “Santiago mariño”
Extensión Maturín
Escuela: Ing. De Sistemas

[pic]

[pic]

| |Realizado por: |
| |Caraballo Deivys|
| |U.C: ESTRUCTURA DISCRET A Y GRAFOS |
| |Secc : “g” |
| ||
| | |
| | |
|| |

Maturín JUNIO de 2010

INTRODUCCIÓN

El siguiente trabajo trata sobre la estructura de datos no lineales llamada árbol. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, ytablas de contenidos. Vamos a profundizar en un tipo especial de árbol llamado árbol binario, la cual puede ser implementada fácilmente en la computadora; aunque en un árbol puede parecer muy restrictivo.

Definición de Arboles

Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que seconstruye 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 b 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. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.Formalmente, podemos definir un árbol de la siguiente forma:

▪ Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
▪ Un nuevo árbol a partir de un nodo nr y k árboles [pic]de raíces [pic]con [pic]elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces de los k árboles. El árbol resultante de [pic]nodos tiene como raíz elnodo nr, los nodos [pic]son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.

PROPIEDADES de los arboles

▪ Dos árboles binarios son similares si tienen la misma estructura, y son equivalentes si son similares y contienen la misma información.
▪ Un árbolbinario está equilibrado si el valor absoluto de las alturas de los subárboles izquierdo y derecho se diferencian en una unidad como máximo.

CARACTERISTICAS de los arboles

▪ Cada nodo puede tener como máximo 2 subárboles.
▪ Cada subárbol se identifica como el subárbol izquierdo o el subárbol derecho de su padre.
▪ Puede ser vacío.
▪ Acerca de la raíz del árbol. Todos losárboles que no están vacíos tienen un único nodo raíz y los demás elementos o nodos se derivan o descienden de él.
▪ El nodo raíz no tiene padre, es decir, no es el hijo de ningún elemento.
▪ Acerca de los nodos: Los nodos son los vértices o elementos del árbol.
▪ Acerca de los nodos terminales u hojas (Leaf node): Son aquellos nodos que no contienen ningún subárbol
▪ A cada...