Arbre binari enfilat. Recorregut en inordre especular X79024
Donada la classe Abin que permet gestionar arbres binaris enfilats usant memòria dinàmica, cal implementar el mètode
que retorna una llista amb els elements de l’arbre en inordre especular 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 inordre_especular. 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 inordre_especular 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 inordre especular 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 inordre_especular 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.
Input
3 0 7 -1 4 -1 -1 2 -1 -1 5 8 -1 -1 9 6 -1 1 -1 -1 -1
Output
9 1 6 5 8 3 2 0 4 7
Input
3 0 7 -1 -1 2 -1 4 -1 6 -1 -1 5 8 9 1 -1 -1 -1 -1 -1
Output
5 8 9 1 3 6 4 2 0 7
Input
3 -1 -1
Output
3
Input
-1
Output
- Author
- Jordi Esteve
- Language
- Catalan
- Official solutions
- Make
- User solutions
- Make