Una comprensión sencilla del primer, medio y último orden de los árboles binarios
(1) Recorrido de primer orden (raíz) (raíz izquierda y derecha)
(2) Recorrido de orden medio (raíz) (izquierda raíz derecha)
p>(3) Recorrido de orden posterior (raíz) (raíces izquierda y derecha)
Por ejemplo:
Recorrido de primer orden (raíz) (raíz izquierda y derecha): A B D H E I C F J K G
Recorrido de orden medio (raíz) (raíz izquierda y derecha): D H B E I A J F K C G
Recorrido de orden inverso (raíz) (raíces izquierda y derecha): H D I E B J K F G C A
Recorrido posterior del orden (raíz). Por ejemplo, cada vez que se atraviesa primero el subárbol izquierdo del árbol, luego se atraviesa el subárbol derecho del árbol y finalmente se atraviesa el nodo raíz, y así sucesivamente hasta Se recorre todo el árbol.
Además, hay una proposición: dada cualquier tipo de secuencia transversal de un árbol binario, el árbol binario correspondiente no se puede determinar de forma única. Pero si conoce la secuencia transversal en orden del árbol binario y cualquier otra secuencia transversal, puede determinar de forma única el árbol binario.
Ejemplo 1: Se sabe que la secuencia transversal de posorden de un árbol binario es dabec, la secuencia transversal de orden es debac y su secuencia transversal de preorden es (cedba).
(1) Recorrido en orden: debac
Recorrido posterior al orden: dabec
El último nodo de la secuencia transversal posterior al orden es el nodo raíz , por lo que se puede ver que c es el nodo raíz.
El nodo raíz de la secuencia transversal en orden está en el medio, con el subárbol izquierdo a la izquierda y el subárbol derecho a la derecha. Por lo tanto, se puede ver en la secuencia transversal de orden medio que el nodo raíz c solo tiene un subárbol izquierdo y ningún subárbol derecho.
(2) Recorrido en orden: deba
Recorrido posterior al orden: dabe
El último nodo de la secuencia transversal posterior al orden es el nodo raíz , por lo que se puede ver que e es el nodo raíz del subárbol izquierdo de c.
El nodo raíz de la secuencia transversal en orden está en el medio, con el subárbol izquierdo a la izquierda y el subárbol derecho a la derecha. Por lo tanto, se puede ver en la secuencia transversal de orden medio que el subnodo izquierdo del nodo raíz e es d y el subárbol derecho es ba.
(3) Recorrido en orden: ba
Recorrido posterior al orden: ab
A partir de la secuencia transversal posterior al orden, podemos saber que b es el nodo raíz del subárbol derecho del punto e. Se puede ver en la secuencia transversal en orden que a es el nodo hijo derecho del nodo raíz b.
La estructura del árbol es la siguiente:
Ejemplo 2: Se sabe que la secuencia transversal de preorden del árbol binario es abdgcefh, la secuencia transversal de orden es dgbaechf, y su secuencia transversal de preorden es (gdbehfca).
(1) Recorrido de preorden: abdgcefh
Recorrido de preorden: dgbaechf
El primer nodo de la secuencia transversal de preorden es el nodo raíz, por lo que se puede ver ese a es el nodo raíz.
El nodo raíz de la secuencia transversal en orden está en el medio, con el subárbol izquierdo a la izquierda y el subárbol derecho a la derecha. Por lo tanto, se puede ver en la secuencia transversal de orden medio que el subárbol izquierdo del nodo raíz a es dgb y el subárbol derecho es echf.
El subárbol izquierdo de a:
(2) Recorrido en orden anticipado: bdg
Recorrido en orden: dgb
Pre -recorrido de orden El primer nodo de la secuencia es el nodo raíz, por lo que sabemos que b es el nodo raíz del subárbol izquierdo de a.
El nodo raíz de la secuencia transversal en orden está en el medio, con el subárbol izquierdo a la izquierda y el subárbol derecho a la derecha. Por lo tanto, se puede ver en la secuencia transversal de orden medio que el subárbol izquierdo del nodo raíz b es dg y no tiene subárbol derecho.
El subárbol izquierdo de b:
(3) Recorrido en preorden: dg
Recorrido en orden: dg
Por preorden Atravesando la secuencia muestra que d es el nodo raíz del subárbol izquierdo de b.
El nodo raíz de la secuencia transversal en orden está en el medio, con el subárbol izquierdo a la izquierda y el subárbol derecho a la derecha. Por lo tanto, se puede ver en la secuencia transversal de orden medio que el nodo hijo derecho del nodo raíz d es g.
El subárbol derecho de a:
(4) Recorrido en preorden: cefh
Recorrido en orden: echf
Por preorden Atravesando la secuencia muestra que c es el nodo raíz del subárbol derecho de a.
Se puede ver en la secuencia transversal de orden medio que el subnodo izquierdo del nodo raíz c es e y el subárbol derecho es hf.
El subárbol derecho de c:
(5) Recorrido en preorden: fh
Recorrido en orden: hf
Por preorden Atravesando la secuencia muestra que f es el nodo raíz del subárbol derecho de c.
Se puede ver en la secuencia transversal de orden medio que el nodo secundario izquierdo del nodo raíz f es hy no hay un subárbol derecho.
La estructura del árbol es la siguiente: