void setInorderPointers (TreeNode * root)
{
if (root == NULL) return;
std :: stack s;
s.push (raíz);
TreeNode * temp = root-> left;
TreeNode * last_pop = NULL;
while (s.size ()! = 0)
{
while (temp! = NULL)
{
s.push (temp);
temp = temp-> izquierda;
}
temp = (TreeNode *) s.pop ();
if (last_pop! = NULL)
{
last_pop-> inorder_successor = temp;
}
last_pop = temp;
temp = temp-> right;
}
}
El algoritmo es:
- Comience a hacer el recorrido iterativo en orden del árbol. Esto se hace a través de la estructura de datos de la pila.
- Cada vez que sacamos un nodo de la pila, básicamente estamos haciendo estallar el nodo que viene en la posición n en el recorrido en orden del árbol. n puede ser cualquier cosa entre 1 y max donde max es el número de nodos en el árbol.
- Llevamos un registro del último nodo reventado.
- Cada vez que hacemos estallar un nodo, establecemos el puntero inorder_successor del último nodo emergente en el nodo emergente actual, apuntando el sucesor de orden del enésimo nodo al nodo (N + 1).