Dvojiško drevo/Algoritem za risanje dvojiških dreves

Iz MaFiRaWiki

  1. Metoda vrne velikost pravokotnika, ki ga potrebujemo za risanje
  2. Vhodni podatek je levi zgornji kot pravokotnika, kjer bi radi narisali drevo

Algoritem

  • prazno drevo znamo narisati ;-) (vrnemo 0 x 0)
  • sicer pa
    • rekurzivno narišemo levo poddrevo. Levi zgornji kot ima isti x, y pa je ustrezno večji - kolikor želimo, da se vertikalno ločijo nivoji)
    • izračunamo položaj korena - y je tak, kot je za levi zg. kot, x pa izračunamo glede na dimenizijo pravokotnika, ki ga rabimo za levo poddrevo.
    • Narišemo koren (vozlišče)
    • povežemo koren levega poddrevesa (če ni bilo prazno) in koren drevesa s črto
    • rekurzivno narišemo desno poddrevo - ustrezno mu podano levi zgornji kot (ne pozabimo na nekoliko razmika med levim in desnim poddrevesom)
    • izračunamo, kako veliko pravokotnik smo potrebovali za risanje celega drevesa in ga vrnemo

Skica

Algoritem skiciran grafično (sklika je pomenjkliva - dejansko pravokotnikov ne rišemo, ampak jih le izračunamo (njihovo velikost)!)

Slika:algoritemZaRisanjeDD.jpg

Osebna orodja