¿Cómo escribir un recorrido a priori, un recorrido intermedio y un recorrido posterior de un árbol binario?
Recorrido a priori
:
1. Visita el nodo raíz
2.
Pre -orden transversal
subárbol izquierdo
3. Preorden transversal
árbol derecho
.
II.
Recorrido intermedio
p>:
1. Recorrido intermedio del subárbol izquierdo
2. nodo raíz
3. Recorrido intermedio del subárbol derecho
Tres.
Recorrido de nivel posterior
:
1.
Recorrido de nivel posterior del subárbol izquierdo
2. Recorrido de nivel posterior del subárbol derecho
3. Visite el nodo raíz
A continuación se muestran algunos ejemplos y métodos:
1. Método de búsqueda de árbol:
El primer paso, según las características del recorrido de la etapa anterior, sabemos
El nodo raíz
es G
El segundo paso es observar el ADEFGHMZ del recorrido intermedio. Entre ellos, ADEF en el lado izquierdo del nodo raíz G debe ser el subárbol izquierdo de la raíz, y HMZ en el lado derecho de G debe ser el subárbol derecho de la raíz.
Paso 3, observe el subárbol izquierdo ADEF. El nodo raíz del subárbol izquierdo debe ser el nodo secundario izquierdo de la raíz del árbol grande. En el recorrido hacia adelante, el nodo secundario izquierdo de la raíz del árbol grande se encuentra después de la raíz, por lo que el nodo raíz del subárbol izquierdo es D.
Paso 4: utilizando el mismo método, el nodo raíz HMZ en el nodo del subárbol derecho de la raíz también se puede encontrar mediante el recorrido hacia adelante, y el nodo raíz en el nodo del subárbol derecho se puede encontrar mediante el recorrido hacia adelante. El nodo raíz HMZ en el nodo del subárbol derecho del árbol grande también se puede encontrar mediante el recorrido de secuencia directa. En el recorrido hacia adelante, primero se deben atravesar el nodo raíz y el nodo raíz, y luego se atraviesan todos los nodos del subárbol izquierdo antes de atravesar el subárbol derecho. El primer nodo atravesado en el subárbol izquierdo es el nodo raíz del subárbol izquierdo. De manera similar, el primer nodo atravesado en el subárbol derecho es el nodo raíz del subárbol derecho.
Paso 5, tenga en cuenta que el proceso anterior es recursivo. Primero busque el nodo raíz del árbol actual, luego divídalo en el subárbol izquierdo y el subárbol derecho, luego ingrese el subárbol izquierdo y repita el proceso anterior, y luego ingrese el subárbol derecho para repetir el proceso anterior. Finalmente, se puede restaurar un árbol. El proceso recursivo se puede expresar de manera sucinta de la siguiente manera:
1
Determine la raíz, determine el subárbol izquierdo y determine el subárbol derecho.
2
Recursividad en el subárbol izquierdo.
3
Recurse en el subárbol derecho.
4
Imprime la raíz actual.
Luego, podemos dibujar la forma de este
árbol binario
:
Luego, de acuerdo con las reglas de recorrido posterior al orden , podemos saber que el orden transversal del postorden es: AEFDHZMG
Alguna información introductoria sobre árboles binarios:
En informática, un árbol binario significa que cada nodo tiene como máximo dos nodos secundarios.
Estructura de árbol
. Los subárboles a menudo se denominan "subárbol
izquierdo" y "subárbol
derecho". Los árboles binarios se utilizan generalmente para implementar
árboles de búsqueda binaria
y
montones binarios
. Cada nodo de un árbol binario tiene en. La mayoría de los dos subárboles
(ningún nodo con un orden mayor que 2), el subárbol del árbol binario tiene una rama izquierda y una rama derecha, y el orden no se puede invertir. El i-ésimo nivel de un árbol binario tiene como máximo 2^{i-1} nodos; un árbol binario con profundidad k tiene como máximo 2^k-1 nodos para cualquier árbol binario T, si el número de nodos terminales es; n_0, el número de nodos de orden 2 es n_2, entonces n_0=n_2+1.
Un árbol binario con profundidad k y 2^k-1 nodos se llama
árbol binario completo
. p>; Un árbol binario con profundidad k y número de nodos se llama
árbol binario completo
si y sólo si cada uno de sus nodos corresponde a un Nodo numerado del 1 al n en un árbol binario completo de profundidad k.