En el artículo anterior, he dicho que el algoritmo de calendario de traversal recursivo (árbol binario primera raíz (primera secuencia) Traversal).
Resume el algoritmo no recursivo del primer recorrido.
1) Ingrese la pila, principalmente para ingresar al primer nodo de la pila y luego visite este nodo
2) mientras
3) El hijo correcto del nodo if es verdadero, transfiera a 1) continúe atravesando, de lo contrario, el nodo actual saldrá y se transferirá al nodo principal que atraviesa 1)
Primero mira el algoritmo que se ajusta a esta idea:
Copiar código del código de la siguiente manera:
Int preordertraversenonrcursiveEx (const bitree & t, int (*visitnode) (datos telemtype))
{{
if (t == nulo)
{{
Regreso -1;
}
Bitnode *pbinode = t;
Sqstack s;
InitStack (& s);
Push (& s, (selectype) t);
Mientras (! IsStackedy (s))
{{
While (pbinode)
{{
Visitnode (pbinode-> data);
if (pbinode! = t)
{{
Push (& s, (selectype) pbinode);
}
pbinode = pbinode-> lchild;
}
if (pbinode == null)
{{
Pop (& s, (selemtype*) y pbinode);
}
if (pbinode-> rchild == null)
{{
Pop (& s, (selemtype*) y pbinode);
}
pbinode = pbinode-> rchild;
}
Regresar 0;
}
Nota: 1) La estructura de la pila se usa aquí, y puede ver la pila almacenada en el orden de la estructura anterior
2) Al guardar el nodo aquí, lo que guardo es la dirección del puntero, es decir, la dirección del nodo, convirtiéndolo en un almacenamiento int. .
¡El algoritmo anterior es realmente incorrecto! ¿Por qué? Aquí revisé durante mucho tiempo. Porque si la pila está vacía después del POP, pero todavía hay el árbol correcto, no continuará. Cuando el árbol infantil izquierdo está vacío, como sigue: como sigue:
Copiar código del código de la siguiente manera:
Int preordertraversenonrcursive (const bitree & t, int (*visitnode) (datos telemtype))
{{
if (t == nulo)
{{
Regreso -1;
}
Bitnode *pbinode = t;
Sqstack s;
InitStack (& s);
Push (& s, (selectype) t);
Mientras (! IsStackedy (s))
{{
GetTop (s, (selectype*) y pbinode);
While (pbinode)
{{
Visitnode (pbinode-> data);
pbinode = pbinode-> lchild;
Push (& s, (selectype) pbinode);
}
if (pbinode == null)
{{
Pop (& s, (selemtype*) y pbinode);
}
if (! isStackedy (s))
{{
Pop (& s, (selemtype*) y pbinode);
pbinode = pbinode-> rchild;
Push (& s, (selectype) pbinode);
}
}
Regresar 0;
}
Este es el caso. Presione en el nodo infantil derecho y luego determine si el niño izquierdo del árbol derecho está vacío y continúa el ciclo.
Hay dos desechos aquí: uno es empujar los nodos del niño vacío para ingresar a la pila, y el otro es usar con frecuencia gettop para obtener el elemento superior de la pila
Regrese aquí para ver el algoritmo diseñado primero, donde el nodo nulo no se presiona en el puntero nulo o el niño vacío, pero no puede ser completamente salido. NULL es nulo, eso es todo, para que no haya vergüenza que no muestre el nodo del árbol subcreree correcto, como sigue: como sigue:
Copiar código del código de la siguiente manera:
// Árbol binario no recursivamente atravesado
Int PreorderTraversenonRCursiveEx (const Bitree & T,
Int (*visitnode) (datos telemtype))
{{
if (t == nulo)
{{
Regreso -1;
}
Bitnode *pbinode = t;
Sqstack s;
InitStack (& s);
Push (& s, (selectype) t);
Mientras que (! IsStackedy (s) || pbinode) // La modificación principal es esta oración
{{
While (pbinode)
{{
Visitnode (pbinode-> data);
if (pbinode! = t)
{{
Push (& s, (selectype) pbinode);
}
pbinode = pbinode-> lchild;
}
if (pbinode == null)
{{
Pop (& s, (selemtype*) y pbinode);
}
if (pbinode-> rchild == null)
{{
Pop (& s, (selemtype*) y pbinode);
}
pbinode = pbinode-> rchild;
}
Regresar 0;
}
Después del primero, se agrega bucle, es suficiente. De la siguiente manera, pruebe el árbol binario en la sección anterior:
En este momento, los datos de entrada siguen siendo 12 34 0 0 78 0 0. Los resultados de la prueba son los siguientes:
--- bitree ---
Ingrese los datos del nodo de Bitree:
12
Ingrese los datos del nodo de Bitree:
34
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
78
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
0
12 34 78
Esto no es suficiente para probar, mira el siguiente árbol binario
En este momento, los datos de entrada deben ser: 12 34 24 0 0 0 0 0 0 78 37 0 0 0. Los resultados de la prueba son los siguientes:
--- bitree ---
Ingrese los datos del nodo de Bitree:
12
Ingrese los datos del nodo de Bitree:
34
Ingrese los datos del nodo de Bitree:
veinticuatro
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
50
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
78
Ingrese los datos del nodo de Bitree:
37
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
0
Ingrese los datos del nodo de Bitree:
0
12 34 24 50 78 37
Se puede ver por el recorrido preliminar que es correcto. , y luego agréguelo para unirlo.