Árboles

Al igual que las listas enlazadas, los arboles están hechos de nodos. Un tipo
común de árbol es un árbol binario, en el que cada nodo contiene una referencia
a otros dos nodos (posiblemente nula). Nombramos a estas referencias como
subarboles izquierdo y derecho. Como los nodos de las listas, los nodos de los
arboles también contienen una carga. Un diagrama de estado de un árbol es así:

                           

 

Para evitar apelotonar las cosas en la figura, solemos omitir los Nones.

La parte superior del árbol (el nodo al que apunta tree) se llama raíz. Siguiendo con la metáfora del árbol, los otros nodos se llaman ramas y los nodos de los extremos con referencias nulas se llaman hojas. Puede parecer extraño que
dibujemos la figura con la raíz arriba y las hojas abajo, pero eso no es lo mas raro.

Para empeorar las cosas, los científicos informáticos añaden a la mezcla otra metáfora: el árbol genealógico. El nodo superior se llama a veces padre y los nodos a los que se refiere son sus hijos. Los nodos con el mismo padre se llaman hermanos.

Para terminar, tenemos un vocabulario geométrico para hablar sobre los arboles.

Ya hemos mencionado izquierda y derecha, pero también están arriba" (hacia el padre/raíz) y \abajo" (hacia los hijos/hojas). También, todos los nodos que están a la misma distancia de la raíz forman un nivel del árbol.

Probablemente no sean necesarias las metáforas arbóreas para hablar de arboles, pero ahí están.

Igual que las listas enlazadas, los arboles son estructuras de datos recursivas

porque se definen recursivamente.
Un árbol es:

• el árbol vacío, representado por None, o
• un nodo que contiene una referencia a un objeto y dos referencias a arboles.