Árboles en Python

Al igual que las listas enlazadas, los árboles 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 subárboles izquierdo y derecho. Como los nodos de las listas, los nodos de los árboles también contienen una carga. Así sería un diagrama de estado de un árbol:

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 más 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 árboles. 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 árboles, pero ahı́ están.

Igual que las listas enlazadas, los árboles 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 árboles.