Cómo convertir un árbol almacenado en una base de datos en una lista de árboles

Hay dos métodos comunes para almacenar datos estructurados en árbol en bases de datos:

1. Lista de adyacencia (modo de lista de adyacencia)

2. Algoritmo de recorrido de árbol preordenado (recorrido de árbol preordenado modificado). algoritmo) Algoritmo de recorrido de árbol ordenado)

Discute las diferencias entre estos dos métodos con el siguiente ejemplo:

La estructura de árbol existente es la siguiente:

Lista de adyacencia modo:

Este modo se utiliza con frecuencia y se presenta en muchos tutoriales y libros. Describimos toda la estructura del árbol como una tabla plana y agregamos un atributo principal a cada nodo para representar el nodo principal del nodo. De acuerdo con este principio, los datos del ejemplo se pueden convertir en la siguiente tabla:

Vemos que la pera es un nodo hijo de verde y el verde es un nodo hijo de fruta. El nodo raíz "Alimentos" no tiene ningún nodo principal. En pocas palabras, en este ejemplo solo se utilizan nombres para representar registros. En una base de datos real, debe etiquetar cada nodo con una identificación numérica. La estructura de la tabla de la base de datos puede ser así: identificación, identificación_padre, nombre, descripción.

El siguiente es el código:

// $parent es el padre del niño que queremos ver

/ / $nivel es el valor que aumenta cuando profundizamos en el árbol,

// Se utiliza para mostrar un bonito árbol sangrado

función display_children($parent, $level)

{

// Obtiene todos los hijos del padre $parent

$result = mysql_query('SELECT name FROM tree '.

' WHERE parent="'. $parent.'";');

// Muestra cada nodo secundario

while ($row = mysql_fetch_array($resultado))

{

// Sangra el nombre del nodo

echo str_repeat(' ',$ nivel).$row['name']." n";

// Llame a esta función nuevamente para mostrar los nodos secundarios del nodo secundario

display_children($row['name'], $level+1);

}

}

Usando esta función en el nodo raíz (Alimentos) de toda la estructura, puede imprimir toda la estructura de árbol de varios niveles. Dado que Food es el nodo raíz y su nodo padre está vacío, se puede llamar así: display_children('',0). Se mostrará toda la estructura del árbol:

Alimento

Fruta

Rojo

Cereza

Amarillo

p>

Plátano

Carne

Vacuno

Cerdo

Si solo desea mostrar parte de toda la estructura, como como parte de la fruta, se puede llamar así: display_children('Fruit',0);

Usando casi el mismo método, podemos conocer la ruta desde el nodo raíz a cualquier nodo. Por ejemplo, la ruta para las cerezas es "Comida >; Fruta >; Roja".

Para obtener dicha ruta, debemos comenzar desde la capa inferior "Cherry", consultar su nodo principal "Red" y agregarlo a la ruta, luego consultar el nodo principal de Red y agregarlo a la ruta, y así sucesivamente, hasta que nivel superior "Comida"

El siguiente es el código:

// $nodo es el nodo más profundo

function get_path ($node)

{

// Consulta el nodo padre de este nodo

$result = mysql_query('SELECT parent FROM tree '.

'WHERE name="'. $nodo.'";');

$row = mysql_fetch_array($resultado);

// Guarda la ruta a la matriz

$path = array();

// Si no es el nodo raíz, continúa consultando hacia arriba

// (La raíz nodo no tiene nodo padre)

p>

if ($row['parent']!='')

{

// La última parte de la ruta de $nodo es el nodo padre de $nombre de nodo

//

$path[] = $row['parent'];

/ / Deberíamos ser la ruta del nodo padre de este nodo

p>

// Agregar a la ruta

$path = array_merge(get_path($row['parent']), $path );

}

// Ruta de retorno

return $ruta;

}

>> p>

Si usa esta función para "Cherry":print_r(get_path('Cherry')), obtendrá la siguiente matriz:

Array

Array

Matriz

Matriz

Matriz

Matriz

Matriz

Matriz

(

[0] => Comida

[1] => Fruta

[2] => Rojo

)

El siguiente paso es Depende de usted cómo imprimirlo en el formato que desee.

Desventajas:

Este método es simple, fácil de entender y fácil de usar. Pero hay algunas desventajas. Principalmente porque se ejecuta más lento y porque obtener cada nodo requiere consultar la base de datos, se necesitan muchas consultas para completar un árbol cuando la cantidad de datos es grande. Además, dado que es una operación recursiva, cada nivel de recursividad requiere una cierta cantidad de memoria, por lo que la eficiencia en la utilización del espacio también es baja.

Algoritmo de recorrido de árbol preordenado

Ahora veamos otro método que no utiliza cálculos recursivos y es más rápido. Este es el algoritmo de recorrido de árbol preordenado (algoritmo de recorrido de árbol preordenado modificado). El método puede estar expuesto a relativamente pocas personas y no es tan fácil de entender como el método anterior cuando se usa por primera vez. Sin embargo, dado que este método no utiliza recursividad, no es tan fácil de entender como el método anterior. Comprenda, pero dado que este método no utiliza un algoritmo de consulta recursivo, tiene una mayor eficiencia de consulta.

Primero, dibujamos datos de múltiples capas en una hoja de papel de la siguiente manera, escribimos un 1 a la izquierda del nodo raíz Comida, luego continuamos hacia abajo en el árbol, escribimos un 2 a la izquierda de Fruta, y luego, a lo largo de todo el borde del árbol, etiquete cada nodo con un número en los lados izquierdo y derecho. El último número es 18, etiquetado a la derecha de "Comida". Puede ver la estructura de múltiples capas de la leyenda completa en la imagen a continuación. (¿No puedes ver con claridad? Señala los números con el dedo y cuenta del 1 al 18 y lo entenderás.

Si aún no entiendes, vuelve a contar y mueve los dedos con cuidado).

Estos números representan las relaciones entre nodos. Los números rojos son 3 y 6, que son los nodos secundarios de "Comida" 1-18. De manera similar, podemos ver que todos los nodos con un valor izquierdo mayor que 2 y un valor derecho menor que 11 son "Fruta" 2- 11 Los nodos secundarios de

De esta manera, toda la estructura del árbol se puede almacenar en la base de datos usando lvalues ​​y rvalues. Antes de continuar, echemos un vistazo a la siguiente tabla de datos ordenados. p>

Nota: Dado que "izquierda" y "derecha" tienen significados especiales en SQL, necesitamos usar "lft" y "rgt" para representar los campos izquierdo y derecho. Además, en esta estructura, no necesitamos ". parent". "campo para representar la estructura de árbol, es decir, la siguiente estructura de tabla es suficiente.

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

Mira, una consulta puede obtener todos estos nodos. Para poder mostrar la estructura de árbol completa como la función recursiva anterior, también necesitamos ordenar por el valor l de los nodos de esta manera:

SELECT * FROM tree WHERE. lft ENTRE 2. Y 11 ORDEN POR lft ASC