Arbre binari enfilat. Recorregut en preordre X39717

Donada la classe $Abin$ que permet gestionar arbres binaris enfilats usant memòria dinàmica, cal implementar el mètode

  list<T> preordre() const;

que retorna una llista amb els elements de l’arbre en preordre sense utilitzar recursivitat ni estructures de dades addicionals, aprofitant que l’arbre binari ja està enfilat.

Cal enviar a jutge.org només la implementació del mètode $preordre$. Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre d’elements $n$ de l’arbre binari.

Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe $Abin$ i un programa principal que llegeix un arbre binari, desprès crida el mètode $preordre$ i finalment imprimeix els elements de la llista.

Entrada

L’entrada consisteix en la descripció d’un arbre binari d’enters (el seu recorregut en preordre amb les fulles marcades amb un -1). Per exemple, l’arbre (mira el PDF de l’enunciat)

es descriuria amb

3 0 7 -1 4 -1 -1 2 -1 -1 5 8 -1 -1 9 6 -1 1 -1 -1 -1

Sortida

Una línia amb els elements de l’arbre en preordre i separats per un espai.

Observació

Cal enviar la solució (el fitxer $solution.cpp$) comprimida en un fitxer $.tar$:

tar cvf solution.tar solution.cpp

Només cal enviar la implementació del mètode $preordre$ i el seu cost en funció del nombre d’elements $n$ de l’arbre binari. Segueix estrictament la definició de la classe de l’enunciat.