recorrido de preorden

 

Arboles

Un árbol es una estructura no lineal formada por un conjunto de nodos y un conjunto de ramas.

En un árbol existe un nodo especial denominado raíz. Así mismo, un nodo del que sale alguna rama, recibe el nombre de nodo de bifurcación o nodo rama y un nodo que no tiene ramas recibe el nombre de nodo hoja. A continuación se aprecia en la siguiente figura:

Como se aprecia en la figura cada nodo de un árbol es la raíz de algún subárbol contenido en él. El número de ramas de un nodo recibe el nombre de grado del nodo.

El nivel de un nodo respecto al nodo raíz se define diciendo que la raíz tiene el nivel 0 y cualquier otro nodo tiene un nivel igual a la distancia de ese nodo al nodo raíz. El máximo de los niveles se denomina altura del árbol.

Es útil limitar los árboles en el sentido de que cada nodo sea a lo sumo de grado 2. De esta forma cabe distinguir entre subárbol izquierdo y subárbol derecho de un nodo. Los árboles así formados, se llaman árboles binarios.

Árboles binarios

Un árbol binario es un conjunto finito de nodos que consta de un nodo raíz que tiene dos subárboles binarios denominados subárbol izquierdo y subárbol derecho.

El árbol binario es una estructura de datos muy útil cuando el tamaño de la estructura no se conoce, se necesita acceder a sus elementos ordenadamente.

En sí un árbol binario es una colección de objetos, cada uno de los cuales contiene datos o una referncia a su subárbol derecho.

Básicamente se pueden utilizar tres formas para recorrer un árbol binario, preorden, inorden, postorden.

Preorden: R,I,D

Inorden: I,R,D

Postorden: I,D,R

En el orden preorden se recorre de la siguiente manera: raíz, subárbol izquierdo, subárbol derecho.

En el orden inorden se recorre de la siguiente manera: subárbol izquierdo, raíz, subárbol derecho.

En el orden postorden se recorre de la siguiente manera: subárbol izquierdo, subárbol derecho, raíz.

La definición de la clase árbol binario, analizando lo expuesto anteriormente de una variable que simboliza la raíz del árbol y cada nodo del árbol será un objeto de la clase