Estructura de datos: métodos de recorrido de árboles y bosques

1. La definición de recorrido de árbol: visite cada nodo del árbol de una determinada manera y solo visítelo una vez. El recorrido del árbol incluye principalmente el recorrido de la raíz primero y el recorrido posterior a la raíz.

2. (1) Recorrido de raíz primero: si el árbol no está vacío, visite primero el nodo raíz y luego recorra cada subárbol del nodo raíz en orden de izquierda a derecha. Este orden de acceso es el mismo que el orden transversal de preorden del árbol binario correspondiente a este árbol.

(2) Recorrido posterior a la raíz: si el árbol no está vacío, recorra cada subárbol del nodo raíz en orden de izquierda a derecha y luego visite el nodo raíz. El orden de acceso es el mismo que el orden transversal en orden del árbol binario correspondiente a este árbol.

Ejemplo uno:

Según la imagen de arriba, se obtienen los siguientes resultados:

Observe que no hemos definido el recorrido de la raíz media del árbol general , porque los nodos secundarios no deben definir cómo dividirlo en dos partes, por lo que solo se definen la primera y la última raíz.

Ejemplo dos:

1. Recorrido de preorden

La definición de recorrido de preorden es:

(1) Visita el primer nodo en el bosque El nodo raíz de un árbol;

(2) Preorden recorre el subárbol del nodo raíz del primer árbol;

(3) Preorden recorre elimina el primer árbol Subbosque detrás de los árboles.

2. Recorrido en orden

La definición de recorrido en orden es:

(1) Recorrido en orden del subárbol del nodo raíz del primer árbol;

(2) Visita el nodo raíz del primer árbol en el bosque;

(3) Recorrido en orden del subbosque después de eliminar el primer árbol.

Conversión entre bosque y árbol binario

Convierte el árbol en un árbol binario:

⑴ Añade una línea de puntos (o una línea continua gruesa). En cada nivel del árbol, se agregan líneas de puntos entre los nodos hermanos en orden de "izquierda a derecha".

⑵ Ir a la conexión. Excepto por el primer nodo secundario más a la izquierda (el nodo secundario más antiguo), se eliminan las conexiones entre el nodo principal y todos los demás nodos secundarios.

Convertir un bosque en un árbol binario:

Cuando un árbol general se convierte en un árbol binario, el subárbol derecho del árbol binario debe estar vacío. Si el nodo raíz del segundo árbol en el bosque (después de la conversión a un árbol binario) se usa como nodo hermano del nodo raíz del primer árbol (árbol binario), los pasos de conversión para convertir el bosque en un árbol binario pueden derivar de la siguiente manera:

(1) Convertir cada árbol en un árbol binario

(2) Según el orden de los árboles en el bosque dado, el primer árbol no se mueve , A partir del segundo árbol, a su vez, el nodo raíz del siguiente árbol se utiliza como hijo derecho del nodo raíz del árbol binario anterior y se conecta con líneas. Cuando todos los árboles binarios están conectados, el árbol binario se convierte. del bosque se obtiene.