Árbol (estructura de datos)
En informática , un árbol es un tipo de datos abstracto ampliamente utilizado que simula una estructura de árbol jerárquica , con un valor raíz y subárboles de hijos con un nodo padre , representado como un conjunto de nodos vinculados .
Una estructura de datos de árbol se puede definir de forma recursiva como una colección de nodos, donde cada nodo es una estructura de datos que consta de un valor y una lista de referencias a nodos. El inicio del árbol es el "nodo raíz" y los nodos de referencia son los "hijos". No se duplica ninguna referencia y ninguna apunta a la raíz.
Alternativamente, un árbol se puede definir de manera abstracta como un todo (globalmente) como un árbol ordenado , con un valor asignado a cada nodo. Ambas perspectivas son útiles: si bien un árbol se puede analizar matemáticamente como un todo, cuando en realidad se representa como una estructura de datos, generalmente se representa y se trabaja con él por separado por nodo (en lugar de como un conjunto de nodos y una lista de adyacencia de bordes entre nodos). , como se puede representar un dígrafo , por ejemplo). Por ejemplo, mirando un árbol como un todo, se puede hablar del "nodo padre" de un nodo dado, pero en general, como estructura de datos, un nodo dado solo contiene la lista de sus hijos pero no contiene una referencia. a su padre (si lo hay).
Un nodo es una estructura que puede contener un valor o condición, o representar una estructura de datos separada (que podría ser un árbol propio). Cada nodo de un árbol tiene cero o más nodos secundarios , que están debajo de él en el árbol (por convención, los árboles se dibujan creciendo hacia abajo). Un nodo que tiene un hijo se llama nodo padre del hijo (o superior ). Un nodo tiene como máximo un padre, pero posiblemente muchos nodos ancestros , como el padre del padre. Los nodos secundarios con el mismo padre son nodos hermanos .
Un nodo interno (también conocido como nodo interno , inodo para abreviar o nodo de rama ) es cualquier nodo de un árbol que tiene nodos secundarios. De manera similar, un nodo externo (también conocido como nodo externo , nodo hoja o nodo terminal ) es cualquier nodo que no tiene nodos secundarios.
El nodo superior de un árbol se llama nodo raíz . Dependiendo de la definición, se puede requerir que un árbol tenga un nodo raíz (en cuyo caso todos los árboles no están vacíos), o se puede permitir que esté vacío, en cuyo caso no necesariamente tiene un nodo raíz. Siendo el nodo superior, el nodo raíz no tendrá un padre. Es el nodo en el que comienzan los algoritmos del árbol, ya que, como estructura de datos, solo se puede pasar de padres a hijos. Tenga en cuenta que algunos algoritmos (como la búsqueda en profundidad posterior al pedido) comienzan en la raíz, pero primero visitan los nodos hoja (acceden al valor de los nodos hoja), solo para visitar la raíz en último lugar (es decir, primero acceden a los hijos del root, pero solo acceda al valor de la raíz en último lugar). Se puede llegar a todos los demás nodos desde él siguiendo bordes o enlaces. (En la definición formal, cada una de estas rutas también es única). En los diagramas, el nodo raíz se dibuja convencionalmente en la parte superior. En algunos árboles, como los montones , el nodo raíz tiene propiedades especiales. Cada nodo de un árbol puede verse como el nodo raíz del subárbol enraizado en ese nodo.
.svg)
