[es] - Kako obrisati listove u binarnom stablu

DiscoNinja
Nis

Član broj: 56118
Poruke: 9
195.252.87.*

Profil

Kako obrisati listove u binarnom stablu

^{28.12.2005. u 22:40}

Dakle imam zadatak da obrisem listove u uredjenom binarnom stablu. Pisao sam neki kod ali mi ne funkcionise kako treba. Problem bi najverovatnije trebalo resavati rekurzivno ali sam se neshto pogubio u tome. Glavna glavobolja mi je sto bi se program, kada obrise neki list, izgubi i nezna kako da se vrati ;)
Evo dela koda:

public void deleteLeaves (){
deleteLeaves (root);
}

public void deleteLeaves(Cvor p){
Cvor prev = null;
while(p!=null){
prev = p;
if((p.left == null) && (p.right == null)) prev = null;
else if (p.left == null)
p = p.right;
else if (p.right == null)
p = p.left;
else ... ???

Ako neko ima ideju, pomagajte!

Za moderatora: Mozda ovo nije za pod "Java" ali ne znam gde bih drugde postavio ovu temu.

_{[Ovu poruku je menjao DiscoNinja dana 28.12.2005. u 23:44 GMT+1]}

^{28.12.2005. u 22:40}

tiranin
Dorćol

Član broj: 37185
Poruke: 245
..taman-bg.customer.sbb.co.yu.

Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 09:11}

Na primer ovako

Code:
public void deleteLeaves (){
          deleteLeaves (root);
           root = null;
}
public void deleteLeaves(Cvor p){
            if((p.left == null) && (p.right == null))
                    return;
            if( p.left != null)
                       deleteLaves(p.left);
            if(p.right != null)
                     deleteLeaves(p.right);
}

^{29.12.2005. u 09:11}

mucky
Aleksandar Mastilović
Novi Sad - Srbija

Član broj: 237
Poruke: 411
*.leased.neobee.net.

Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 10:15}

Citat:

tiranin: Na primer ovako

Mislim da treba

Code:
public void deleteLeaves (){
          deleteLeaves (root);
           root = null;
}
public void deleteLeaves(Cvor p){
            if((p.left == null) & (p.right == null))
                    return;
            if( p.left != null) {
                       deleteLeaves(p.left);
                       p.left = null;
            }
            if(p.right != null) {
                     deleteLeaves(p.right);
                     p.right = null;
            }
}

^{29.12.2005. u 10:15}

jablan
Mladen Jablanović
Beograd

Član broj: 8286
Poruke: 3334
*.yubc.net.

Sajt: blog.radioni.ca

Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 10:16}

Citat:

tiranin: Na primer ovako

Koliko vidim, ovo ne briše listove, već samo uništava referencu na root.

Brisanje samo listova (čvorova koji nemaju dece) bi išlo otprilike ovako

Code:

public bool Brisi(cvor p) {
  if (p == null)
    return false;

  if (p.left == null && p.right == null)
    return true;

  if (Brisi(p.left))
    p.left = null;

  if (Brisi(p.right))
    p.right = null;

  return false;
}

_{[Ovu poruku je menjao jablan dana 29.12.2005. u 11:36 GMT+1]}

_{Probajte Ruby}

^{29.12.2005. u 10:16}

DiscoNinja
Nis

Član broj: 56118
Poruke: 9
195.252.87.*

Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 12:52}

Citat:

jablan: Koliko vidim, ovo ne briše listove, već samo uništava referencu na root.

Brisanje samo listova (čvorova koji nemaju dece) bi išlo otprilike ovako

Upravo je to resenje! Hvala svima na trudu, a posebno jablanu na velikoj pomoci.
Pozdrav!

^{29.12.2005. u 12:52}