Inicialmente, colocamos o nó raiz na pilha. Enquanto a pilha não está vazia, nós a colocamos e empurramos seu filho direito e esquerdo para dentro da pilha. Quando colocamos o nó raiz, imediatamente o colocamos em nossa lista de resultados. Assim, o primeiro elemento na lista de resultados é a raiz (daí o nome, Pré-encomenda)….