Utilizarea şi programarea calculatoarelor 2 - Laborator 9

Exerciţii scurte

Pentru execriţiile de mai jos puteţi folosi ca punct de plecare arborele construit la laboratorul anterior.

Scrieţi un program care numără nodurile dintr-un arbore binar.

folosind un contor global incrementat la vizitarea fiecărui nod
efectuând întâi recursiv calculul pentru fiecare subarbore

Scrieţi un program care afişează fiecare nod dintr-un arbore, împreună cu adâncimea la care se află:

folosind o variabilă globală incrementată şi decrementată corespunzător
transmiţând adâncimea curentă ca parametru suplimentar la procedura de vizitare

Scrieţi o funcţie care determină dacă un arbore binar e echilibrat sau nu. Un arbore binar se numeşte echilibrat dacă este fie vid, fie cei doi subarbori ai săi sunt echilibraţi şi diferenţa între adâncimile lor e cel mult 1.

Problemă

Tipăriţi în mod grafic arborele binar construit la laboratorul trecut, după exemplul din figura următoare (pornind în adâncime de la stânga la dreapta şi cu câte un nod pe fiecare linie).

         |-15-|
         |    |    |-21-|
         |    |    |    |    |-26
         |    |    |    |-27-|
         |    |-35-|
         |         |         |-36
         |         |    |-40-|
         |         |-49-|
         |              |    |-59
         |              |-62-|
         |                   |-63-|
         |                        |-72
    |-77-|
-83-|
    |-86-|
         |         |-90
         |    |-92-|
         |-93-

Pentru început, tipăriţi fiecare nod precedat de un număr de spaţii proporţional cu adâncimea.
Opţional, pentru a realiza legăturile (liniile verticale), ţineţi minte un tablou cu direcţia parcursă (stânga sau dreapta) pe fiecare nivel până la nodul curent. Tipăriţi un caracter | pe fiecare nivel corespunzând sfârşitului unui segment de direcţii identice (de exemplu, pe linia cu nodul 59, parcurs cu LLRRRL se trag bare după 2 nivele, apoi încă 3, apoi încă unul.

Marius Minea

Last modified: Mon Apr 26 07:40:24 EEST 2004