Enlaces




Frase

"Aquel que pregunta una vez es tonto una vez, aquel que no pregunta nunca es tonto siempre".

Libros de Interes

Libros interesantes

Online Demos

Árboles Binarios

Un árbol binario es una estructura de datos en la cual cada nodo:
* No tiene hijos (hoja).
* Tiene un hijo izquierdo y un hijo derecho.
* Tiene un hijo izquierdo.
* Tiene un hijo derecho.



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.
  • Balance—Un árbol binario está balanceado si existen el mismo número de nodos hijos derechos como nodos hijos izquierdos



  • Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma 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 nodo puede 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.

Recorridos sobre árboles binarios
El arbol binario puede ser recorrido mediante los recorridos: Preorden, Postorden e implenta el Inorder.
Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

Preorden( nodo )
procesan nodo )
Preorden( nodo.izquierdo )
Preorden( nodo.derecho )
Fin Preorden

Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

Postorden( nodo )
Postorden nodo.izquierdo )
Postorden( nodo.derecho )
procesar( nodo )
Fin Postorden

Recorrido en inorden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un árbol de búsqueda binaria este recorrido daría los valores de clave ordenados de menor a mayor. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.

Inorden nodo )
Inorden( nodo.izquierdo)
procesar( nodo )
Inorden( nodo.derecho)
Fin Inorden

[+/-]Recorridos de un árbol binario...
 
Subir a Inicio