Un arbore binar poate avea 12 tipuri de noduri, în funcţie de poziţia tatălui şi a fiilor ca în tabelul următor:

TIPUL NODULUI	ESTE FRUNZĂ (Nu are fii)	ARE NUMAI FIU STÂNGA	ARE NUMAI FIU DREAPTA	ARE DOI FII
ESTE RADACINA (Nu are tată)
ESTE FIU STÂNGA
ESTE FIU DREAPTA

Fie un arbore binar cu n noduri. Etichetăm nodurile arborelui , în funcţie de tip, folosind următoarele etichete:

ETICHETA NODULUI	ESTE FRUNZĂ (Nu are fii)	ARE NUMAI FIU STÂNGA	ARE NUMAI FIU DREAPTA	ARE DOI FII
ESTE RADACINA (Nu are tată)	A	B	C	D
ESTE FIU STÂNGA	E	F	G	H
ESTE FIU DREAPTA	I	J	K	L

Folosind această etichetare definim 3 tipuri de codificări ale arborelui. Fiecare codificare este formată din n+3 caractere litere mari, neseparate prin spaţii.

• RSD: Primele 3 caractere sunt RSD; urmează n caractere din mulţimea {A, B, C, D, E, F, G, H, I, J, K, L} reprezentând etichetele nodurilor în ordinea vizitării folosind parcurgerea în preordine.
  
• SRD: Primele 3 caractere sunt SRD; urmează n caractere din mulţimea {A, B, C, D, E, F, G, H, I, J, K, L} reprezentând etichetele nodurilor în ordinea vizitării folosind parcurgerea în inordine.
  
• SDR: Primele 3 caractere sunt SDR; urmează n caractere din mulţimea {A, B, C, D, E, F, G, H, I, J, K, L} reprezentând etichetele nodurilor în ordinea vizitării folosind parcurgerea în postordine.
  

Cerinţă

Cunoscând una dintre cele trei codificări să se determine celelalte două şi să se afişeze toate cele trei codificări în ordinea RSD, SRD, SDR.

Date de intrare

Fişierul de intrare codarb.in conţine pe prima linie un şir de litere mari neseparate prin spaţii reprezentând una dintre cele trei codificări.

Date de ieşire

Fişierul de ieşire codarb.out va conţine trei linii, fiecare conţinând câte un şir de litere mari neseparate prin spaţii. Prima linie va conţine codificarea RSD, a doua linie codificarea SRD, iar a treia codificarea SDR a arborelui.

Restricţii şi precizări

• 5 ≤ numărul de noduri ≤ 10000
• Parcurgerile RSD (preordine), SRD (inordine) şi SDR (postordine) încep din rădăcina arborelui şi traversează recursiv nodurile după următoarele reguli:
• Parcurgerea RSD : 1. Vizitează nodul curent 2. Parcurge subarborele stânga 3. Parcurge subarborele dreapta
• Parcurgerea SRD : 1. Parcurge subarborele stânga 2. Vizitează nodul curent 3. Parcurge subarborele dreapta
• Parcurgerea SDR : 1. Parcurge subarborele stânga 2. Parcurge subarborele dreapta 3. Vizitează nodul curent

Exemplu

codarb.in	codarb.out	Explicaţii
RSDDFEKI	RSDDFEKI SRDEFDKI SDREFIKD	Pentru arborele etichetat cu 5 noduri : se cunoaşte codificarea RSDDFEKI obţinută parcurgând nodurile în preordine. Prin parcurgerea nodurilor în inordine se obţine codificarea SRDEFDKI. Prin parcurgerea nodurilor în postordine se obţine codificarea SDREFIKD.

prof. Adrian Panaete

Colegiul National „A. T. Laurian” Botoşani

acpanaete@yahoo.com