Arbolesbinarios

ARBOLES BINARIOS
DEFINICION:
Los árboles binarios son de los tipos particulares más importantes de árboles con raíz.
Cada vértice de un árbol binario tiene a lo más dos hijos cada hijo se designa como hijo izquierdo o hijo derecho. Al trazar un árbol binario, un hijo izquierdo se dibuja a la izquierda y un hijo derecho se dibuja a la derecha.
Un árbol binario es un árbol con raíz en el cualcada vértice tiene cero, uno o dos hijos.
Si un vértice tiene un hijo, ese hijo se designa como un hijo izquierdo o un hijo derecho (pero no ambos). Si un vértice tiene dos hijos, uno de ellos de designa como un hijo izquierdo y el otro se designa como un hijo derecho.
En el árbol binario el vértice b es el hijo izquierdo del vértice a y el vértice c es el hijo derecho del vértice a. El vérticed es el hijo derecho del vértice b; el vértice b no tiene un hijo izquierdo. El vértice e es el hijo izquierdo del vértice c; el vértice c no tieneun hijo derecho.
Un árbol que define un código de Huffman es un árbol binario. Por ejemplo, en el árbol del código de el paso de un vértice a un hijo izquierdo corresponde a
utilizar el bit I Yel paso de un vértice a un hijo derecho corresponde aluso del bit O. OUn árbol binario completo es un árbol binario en el cual cada vértice tiene dos o cerohijos. Un resultado fundamenta! acerca de los árboles binarios completos es el siguienteteorema.
El árbol binario de la figura tiene altura h = 3 Yel número de vértices terminales es
t = 8. Para este árbol, la desigualdad (7.5.1) se convierte en una igualdad.

Suponga que tenemos un conjuntoScuyos elementos se pueden ordenar. Por ejemplo,si S consta de números, podemos utilizar el orden común definido sobre los números, y si S consta de cadenas de caracteres alfabéticos, podemos utilizar el orden lexicográfico. Los árboles binarios se utilizan ampliamente en las ciencias de la computación para guardar los elementos de un conjunto ordenado, como un conjunto de número o un conjunto decadenas.
Si el elemento dato d (v) se guarda en el vértice v y el elemento de dato d (w) se guarda en el vérticew, entonces, si v es un hijo izquierdo (o un hijo derecho) de w, se puede garantizar que existe cierta relación de orden entre d(v) y d(w). Un ejemplo es un árbol de búsqueda binaria..
Un árbol de búsqueda binaria es un árbol binario Ten el cual se asocian ciertos datos con los vértices.Los datos están ordenados de modo que, para cada vértice v en T, cada elemento de dato en el subárbol izquierdo de v sea menor que el elemento de dato en v y cada elemento de dato en el subárbol derecho de v es mayor que el elemento de dato en v.

(Los viejos programadores nunca mueren; sólo pierden su memoria) se pueden colocar en un árbol de búsqueda binaria, como muestra la figura 7.5.4.Observe que para cualquier vértice v, cada elemento de dato en el subárbol izquierdo de v es menor (es decir, precede' alfabéticamente) que el elemento de dato en v y cada elemento de dato en el subárbol derecho de v es mayor que el elemento de dato en v.
En general, habrá muchas formas de colocar datos en un árbol de búsqueda binaria

El árbol de búsqueda binaria T se construyó de la siguienteforma.
Comenzamos con un árbol vacío, es decir, un árbol sin vértices ni aristas. Luego inspeccionamoscada una de las palabras en el orden en que aparecen, comenzando cono.Juego con PROGRAMMERs,luego NEVER, y así sucesivamente. Para comenzar, creamos un vértice y colocamos la primera palabra OLD en este vértice. Designamos este vértice como la raíz. A partir de este punto, dada una palabra en lalista agregamos un vértice v y una arista al árbol y colocamos la palabra en el vértice v. Para decidir dónde agregar el vértice y la arista, comenzamos en la raíz. Si la palabra por agregar es menor que la Palabra de la raíz (en el orden lexicográfico), pasamos al hijo izquierdo y si la palabra por agregar es mayor que la palabra de la raíz. pasamos al hijo derecho. Si no existe tal hijo,...