Dvojiško drevo/Risanje/Implementacija (Java)

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Algoritem Naj bo drevo predstavljeno kot tabelo. Vemo, da se vrednosti vozlišč začnejo z indeksom 1 in ne 0 (ga ne upoštevamo). Vemo, da je vrednost glavnega korena na indeksu 1. Vrednost levega sina dobimo na indeksu, ki je enak 2*index_očeta, vrednost desnega sina pa dobimo na indeksu, ki je enak 2*index_očeta+1. Vemo tudi, da število nivojev dobimo tako, da izračunamo log2(število vozlišč).

Najprej izračunamo koliko nivojev ima drevo. Potem se rekurzivno sprehodimo čez tabelo, ki predstavlja vrednosti v vozliščih. Preverimo, če je na trenutnem indeksu podatek, ki predstavlja vrednost vozlišča. V primeru, da je podatek na trenutnem indeksu različen od -1 oz. izrišemo krog in v njem izpišemo vrednost ter vozlišče povežemo z očetom. Nato si zapomnimo pozicijo, kjer smo narisali krog (spodnjo sredinsko točko). Izračunamo, kakšen bo moral biti odmik levo oz. desno na naslednjem nivoju (ko bomo risali levega in desnega sina). Na koncu rekurzivno kličemo metodo na levem oz desnem sinu.

Algoritem za risanje dvojiškega drevesa na konkretnem primeru:

Recimo, da imamo podano tabelo z elementi -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, 11, -1, 13, 14, -1, -1, 17. Vrednost -1 pomeni, da vozlišče na tem mestu ne obstaja.

Najprej izračunamo število vseh nivojev. st_nivojev = log_2(17) = 4, vrednost smo zaokrožili navzdol, ker nivoje v nadaljevanju štejemo od 0. Nato kličemo rekurzivno metodo z indeksom glavnega vozlišča. To je torej z indeksom 1. Hkrati pa metodi tudi povemo na kateri poziciji mora začeti risati glavni koren, da se bodo lahko izrisali vsi nivoji. Odmik v y smeri ni pomemben v x smeri pa ga izračunamo po formuli (2^st_nivojev)*širina_vozlišča. Rekurzivna metoda v danem primeru izrisuje vozlišča na sledeč način.


Preverimo, če vozlišče na indeksu 1 obstaja:

V podanem primeru obstaja in ima vrednost 1. Zato narišemo krog z vredenostjo 1.

Slika:korak1.jpg

Če nismo v korenu drevesa (indeks = 1) izrišemo, črto do očeta.

Ker je indeks = 1 ne narišemo črte do očeta, ker vozlišče nima očeta.


Zapomnimo si spodnjo srednjo točko vozlišča.

V danem primeru si zapomnimo točko (320+20/2, 20+20) = (330, 40).


Nato izračunamo na katerem nivoju smo.

V danem primeru je za indeks 1 nivo 0 (ker nivoje štejemo od 0 naprej).


Izračunamo odmik na naslednjem nivoju.

V danem primeru je to 2^(4-0-1)*20 = 160.


Rekurzivno kličemo metodo z indeksom levega sina (2*oče), s pozicijo (x_očeta - odmik; y_očeta + 2*visina_vozlišča) ter spodnjo sredinsko pozicijo očeta, ki smo si jo zapomnili.

V našem primeru je indeks enak 2*1=2, pozicija = (320-160, 20+2*20), pozicija očeta = (330, 40).


Preverimo, če vozlišče na indeksu 2 obstaja.

Ker vozličše na indeksu 2 obstaja in ima vrednost 2 ga izrišemo.

Slika:korak2.jpg

Preverimo, če smo na nivoju večjem od 0 (index > 1).

V našem primeru smo na nivuoju 1 zato izrišemo črto do očeta.

Slika:korak3.jpg

Izračunamo odmik na naslednjem nivoju in rekurzivno kličemo metodo na levem poddrevesu.

V našem primeru je odmik 160-80 in indeks levega sina 4.


Preverimo, če vozlišče na indeksu 4 obstaja.

Ker vozlišče na indeksu 4 obstaja in ima vrednost 4 ga izrišemo.

Slika:korak4.jpg

Preverimo, če smo na nivoju večjem od 0 (index > 1)

V našem primeru smo na nivoju 2 zato izrišemo črto do očeta.

Slika:korak5.jpg

Izračunamo odmik na naslednjem nivoju in rekurzivno kličemo metodo na levem poddrevesu.

V našem primeru je odmik 80-40 in indeks levega sina 8.


Preverimo, če vozlišče na indeksu 8 obstaja.

Ker vozlišče na indeksu 8 obstaja in ima vrednost 8 ga izrišemo.

Slika:korak6.jpg

Preverimo, če smo na nivoju večjem od 0. (index > 1)

V našem primeru smo na nivoju 3, zato izrišemo črto do očeta.

Slika:korak7.jpg

Izračunamo odmik na naslednjem nivoju in rekurzivno kličemo metodo na levem poddrevesu.

V našem primeru je odmik 40-20 in indeks levega sina 16.


Preverimo, če vozlišče na indeksu 16 obstaja.

Ker vozlišče na indeksu 16 NE obstaja ne izrišemo nič in se vrnemo v prejšni rekorzivni klic.


Na prejšnjem rekurzivnem klicu kličemo rekurzivno metodo na desnem sinu.

V našem primeru kličemo rekurzivno metodo z indeksom 17 in odmikom 40+20.


Preverimo, če vozlišče na indeksu 17 obstaja.

Ker vozlišče na indeksu 17 obstaja in ima vrednost 17 ga izrišemo.

Slika:korak8.jpg

Preverimo, če smo na nivoju večjem od 0 (index > 1)

V našem primeru smo na nivoju 4, zato izrišemo črto do očeta.

Slika:korak9.jpg

Izračunamo odmik na naslednjem nivoju in rekurzivno kličemo metodo na levem poddrevesu.

V našem primeru je odmik 20-20 in indeks levega sina 34.


Preverimo, če vozlišče na indeksu 34 obstaja.

Ker vozlišče na indeksu 34 NE obstaja, se vrnemo na prejšnji rekurzivni klic.

....


Celotno drevo za dani primer:

Slika:drevo.jpg

Program za risanje dvojiškega drevesa:

 
import java.awt.*;
import java.applet.*;
 
public class NarisiDrevo extends Applet
{
      final static int sirina = 20; // širina vozlišča
      final static int visina = 20; // višina vozlišča
      static int st_nivojev;
 
      public void paint(Graphics g)
      {
              // drevo podano kot tabela -> levi_sin = 2*oče; desni_sin = 2*oče+1
              int[] drevo = new int[]{-1,1,2,3,4,5,6,7,8,9,-1,11,-1,13,14,-1,-1,17};
              // izračunamo koliko nivojem ima drevo
              st_nivojev = (int)Math.ceil(Math.log(drevo.length - 1)/Math.log(2)) - 1;
              Narisi(g, drevo, 1, (int)Math.pow(2, st_nivojev) * sirina, visina, 0, 0);
      }
 
      // p ... drevo podano kot tabela
      // index ... indeks vozlišča na katerem se nahajamo
      // x ... odmik od levega roba
      // y ... odmik od desnega roba
      // x_pred; y_pred ... spodnja sredinska točka očeta (pozicija začetka črte)
      public static void Narisi(Graphics g, int[] p, int index, int x, int y, int x_prej, int y_prej)
      {
              // preverimo, če vozlišče obstaja
              if(index < p.length && p[index] != -1)
              {
                      // nariše krog
                      g.drawOval(x, y, sirina, visina);
                      // izpiše vrednost
                      g.drawString(Integer.toString(p[index]), x + 5, y + 15);
                      if (x_prej != 0)
                              // nariše črto ce smo na nivoju > 1
                              g.drawLine(x_prej, y_prej, x + sirina/2, y);
                      x_prej = x + sirina/2;
                      y_prej = y + visina;
 
                      int nivo = (int)Math.floor(Math.log(index)/Math.log(2));
                      // izračuna kolikšen mora biti odmik na naslednjem nivoju
                      int odmik = (int)(Math.pow(2, st_nivojev - nivo - 1)) * sirina;
 
                      // rekurziven klic na levem poddrevesu
                      Narisi(g, p, index * 2, x - odmik, y + 2 * visina, x_prej, y_prej);
                      // rekurziven klic na desnem poddrevesu
                      Narisi(g, p, index * 2 + 1, x + odmik, y + 2 * visina, x_prej, y_prej);
              }
      }
}
Osebna orodja