Hay una distinción entre un árbol como un tipo de datos
abstracto y como una estructura concreta de datos, de forma análoga a la
distinción entre una lista y lista enlazada. Como tipo de dato, un árbol tiene
un valor e hijos, y los hijos son a su vez subárboles; el valor y los hijos de
un árbol se interpreta como el valor del nodo raíz y los subárboles de los
hijos del nodo raíz. Para permitir que los árboles finitos, hay que, o bien
permitir que la lista de los hijos pueda estar vacía, o permitir que los
árboles puedan estar vacíos, en cuyo caso la lista de los hijos pueden ser de tamaño
fijo (factor de ramificación, especialmente 2 o binario), si se desea.
Como una estructura de datos, un árbol vinculado es un grupo de nodos, donde cada nodo tiene un valor y una lista de referencias a otros nodos (sus hijos). Esta estructura de datos realmente define a un grafo dirigido,1 porque puede tener bucles o varias referencias al mismo nodo, del mismo modo que una lista enlazada. Luego también existe el requisito de que no hay dos referencias que apuntan al mismo nodo (que cada nodo tiene como máximo un solo padre, y de hecho todos lo tienen, a excepción de la raíz), y un árbol que viola esto es árbol corrupto.
Debido al uso de referencias a los árboles en la estructura de datos de un árbol enlazado, a menudo se habla de árboles en los que implícitamente están siendo representados por referencias al nodo raíz, ya que esto es, normalmente, la forma en la que se aplican realmente. Por ejemplo, en lugar de un árbol vacío, uno puede tener una referencia nula: un árbol nunca está vacío, sino que una referencia a un árbol puede ser nula.
No hay comentarios:
Publicar un comentario