tecnico informatica

Árbol binario
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodointerno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Definición de teoría de grafos


Un árbol binario sencillo de tamaño 9, 4 niveles y altura 3 (altura = máximo nivel - 1), con un nodo raíz cuyo valor es 2.
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y nodirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.
Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiplescomponentes conectados en el grafo, llamaremos a esta última estructura un bosque.
[editar]Tipos de árboles binarios
• Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
• Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
• Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a lamisma profundidad (distancia desde la raíz, también llamada altura).
• A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodopuede tener cero, 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.
Creación de árboles a partir de los recorridos
Para poder dibujar un árbol binario en base a los recorridos, se necesitan por lo menos dos de los recorridos de profundidad (en caso de que no se repitan los nodos, ya que si se repiten los nodos esrecomendable tener los tres recorridos), ya sean inorden y preorden o inorden y postorden, la única diferencia entre usar el recorrido en preorden o postorden es que en preorden se usa el primer nodo para encontrar la raíz y en postorden se usa el último nodo.
El método consiste en ir dividiendo los recorridos del árbol en pequeños subárboles, se va encontrando la raíz con el preorden o postorden y sedivide en dos subárboles basándonos en el recorrido en inorden. En el caso de que los nodos se repitan es conveniente tener los 3 recorridos para identificar más fácilmente cuál de los nodos es la raíz actual.
Para el árbol de la figura corresponden los siguientes recorridos:

Preorden
Inorden
Postorden

Para encontrar la raíz es necesario tener el recorrido inorden o postorden, yaque la raíz es el primer nodo o el último nodo respectivamente. En este caso la raíz es el .
Una vez encontrada la raíz, es necesario saber su posición en el recorrido inorden, del paso anterior se tiene el nodo , pero existen 2 nodos con ese valor, el primero y el de en medio. Si el primer dos es la raíz, entonces no existe ninguna rama del lado izquierdo, en ese caso la siguiente raíz deacuerdo con el recorrido en postorden es y de acuerdo con preorden es , lo cual es una incongruencia, de esa forma sabemos que el otro es la raíz.
Entonces marcamos la raíz en el recorrido inorden:

Preorden
Inorden
Postorden

El recorrido inorden, es un recorrido de los arboles binarios en los que se empieza desde el nodo que se encuentra más a la izquierda de todos, sigue con la...