GRUDAT, ÖVNING 4
   
Binära sökträd

1 TRÄDBYGGEN

*  Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6
   3 7 5 i denna ordning? Och hur ser det ut om man sätter in dom i
   omvänd ordning, alltså 5 7 3 6 1 4 2?  Är båda träden binära
   sökträd? Är de balanserade?

2  POSTORDERTRÄD

*  Skriv ut något av träden i inordning och bygg upp ett nytt
   träd från denna talföljd. Skriv sedan ut dom i preordning och
   bygg upp nya träd från dessa talföljder. Skriv slutligen ut
   dom i postorder och bygg upp nya träd från dessa talföljder.
   Kommentera resultaten!

3  TRÄDSTACKNING

*  Om man i en rekursiv trädutskrift ersätter print med
   push, så kommer alla talen in i en stack. Om man sedan vill bygga
   upp samma träd från talen i stacken, bör man då ha använt
   inordning, preordning eller postordning vid utskriften?

4  TRÄDSUDDNING 

*  Ett binärträd innehåller en miljon poster. Hur raderar man enklast
   hela trädet?

5  ICKEREKURSIV INPUTTNING

*  På föreläsningen tillverkades klassen Bintree med metoderna put,
   exists och write. Den rekursiva put som skrevs är inte så lätt - 
   försök därför skriva en icke-rekursiv put.

6  REKURSIV TRÄDSUMMA

*  Ge en rekursiv tanke för summan av alla talen i trädet och
   programmera den så att anropet tree.sum() ger rätt svar.

7  REKURSIVT LÖVANTAL

*  Ge en rekursiv tanke för antalet löv i trädet. (Ett löv är en nod
   utan barn.) Programmera den så att anropet leaves(root) ger rätt
   svar.

8  REKURSIV TRÄDHÖJD

*  Ge en rekursiv tanke för höjden av ett träd. (Höjden definieras
   konstigt nog som antalet nivåer - 1. Ett tomt träd får höjden -1.)